彩虹表的实现

Question

我正在尝试实现GSM网络KASUMI密码的彩虹表攻击的在线阶段。

我仅使用32位密钥空间而不是完整的128位。以下是我的实现。我生成了一个包含2²⁵行和每行2^7.88链路的单个彩虹表，这应该给出73%的成功率。

为了节省空间，我们只保存端点。表以二进制文件形式保存。我可以通过检查端点在表中的位置来找到起始点。因此，第三个端点具有md5值为3的起始点，第四个端点具有md5值为4的起始点，依此类推。

问题在于，当使用随机密钥进行测试时，我获得10-15%的成功率。为了检查我们是否生成了正确的链路，我使用起始点作为密钥，并且获得了100%的成功率，这是预期的。

我担心这可能与字节顺序有关，但我不确定。

#include <stdio.h>
#include <stdint.h>
#include <pthread.h>
#include <time.h>
#include <openssl/md5.h>
#include <stdlib.h>
#include "cipher/kasumi.h"
#include "misc.h"

uint16_t * reduction(uint32_t m){
    static uint16_t data[8];
    data[0]=m>>16;
    data[1]=m;
    return data;
} 

int inTable(uint32_t key,uint32_t * ciphertext, uint32_t * text){
    uint16_t buffer[10000],*temp2,keys[8];
    uint32_t endpoint, ep;
    uint32_t cipher[2];
    int cntr = 0,i,j,y,k;
    FILE *ptr;

    ptr = fopen("test32.bin","rb");  // r for read, b for binary */
    for(;;){
        size_t n=fread(buffer,sizeof(buffer),1,ptr);
        k=0;
        for(i=0;i<5000;i++){
            endpoint = buffer[k] <<16 | buffer[k+1];
            k=k+2;
            if(endpoint==key){
                temp2 = keyGen(cntr);
                for (y = 0; y < 8; y++){
                    keys[y] = temp2[y%2];
                }
                for (j = 0; j < 236; j++){
                    keyschedule(keys);
                    temp2 = kasumi_enc(text);
                    cipher[0] = temp2[0]<<16 | temp2[1];
                    cipher[1] = temp2[2]<<16 | temp2[3];
                    ep = keys[0] << 16 | keys[1];
                    if(cipher[0]==ciphertext[0]&&cipher[1]==ciphertext[1]){
                        printf("Key found %i steps into chain \n", j);
                        printf("Key is the following: %04x \n",ep);
                        fclose(ptr);
                        return 1;
                    }
                    for (y = 0; y < 8; y++){
                        keys[y] = temp2[y % 2];
                    }
                }
            }
        cntr = cntr+1;
        }
        if(n==0){
            fclose(ptr);
            return -1;
        }
    }
}

int onlinePhase(uint32_t * ciphertext, uint32_t * text){
    int t, i;
    uint16_t * temp;
    uint32_t ep;
    uint16_t key[8];

    inTable(ciphertext[0],ciphertext,text);
    temp = reduction(ciphertext[0]);
    //reduciton function
    for (i = 0; i < 8; i++){
        key[i] = temp[i%2];
    }

    for (t = 0; t < 236; t++){
        keyschedule(key);

    temp = kasumi_enc(text);
    //reduction function
    for (i = 0; i < 8; i++){
        key[i] = temp[i % 2];
        }

    ep = key[0]<<16 | key[1];
    i=inTable(ep,ciphertext,text);
    if (i>0)
        return 1;
    }
return 0;
}


uint16_t * randomme(){

    int byte_count = 4;
    static uint16_t data[8];
    FILE *fp;
    fp = fopen("/dev/urandom", "r");
    fread(&data, 1, byte_count, fp);
    fclose(fp);
    return data;
}

int main(){
    int i, j = 0, cntr = 0;
    uint16_t key[8], * temp;
    uint32_t text[2] = {
        0xFEDCBA09, 0x87654321
    };

    uint32_t ciphertext[2];
    while(j < 100){
        temp = randomme();
        for(i=0;i<8;i++){
            *(key+i)=temp[i%2];
        }
        keyschedule(key);
        temp = kasumi_enc(text);
        ciphertext[0] = temp[0]<<16 | temp[1];
        ciphertext[1] = temp[2]<<16 | temp[3];
        printf("ciphertext %08x %08x \n",ciphertext[0],ciphertext[1]);
        printf("key  %04x %04x \n",key[0],key[1]);
        cntr=cntr+onlinePhase(ciphertext, text);
        j++;
    }
    printf("%i\n",cntr);
    printf("%i\n",(cntr/j *100));
    return 0;
}

- Becktor

Answer 1

好的，在经过多次尝试后，我发现我创建的端点是错误的，我的缩减函数也是错误的。在线阶段应该创建t个点，首先将使用表格检查第一个点上最后使用的缩减函数，然后是加密和倒数第二个缩减函数，以此类推，直到达到t个不同的点。这已在下面添加的代码中进行了编辑。

缩减函数已更改为

uint32_t reduction32(int n, uint16_t * tempkey){
    uint32_t key;
    key = (tempkey[0]+n)<<16 | (tempkey[1]+n);
    return key;
}

并且 OnlinePhase 函数被更改为

int onlinePhase(uint16_t * ciphertext, uint32_t * text){
    int t,i,j;
    int chainLength=236;
    uint32_t tp;
    uint16_t *temp,temp2[4], key[8];
    uint32_t ep[chainLength];
    ep[0] = reduction32((chainLength-1), ciphertext);
    temp = ciphertext;
    for (t = (chainLength-2); t >= 0; t--){
        for(i=0;i<4;i++)
            temp2[i] = ciphertext[i];
        temp=temp2;
        for(j = t; j < chainLength; j++){
            if(j == (chainLength-1)){
                ep[chainLength-1-t] = reduction32(j, temp);
            } else{
                tp = reduction32(j,temp);
                temp[0] = tp >> 16;
                temp[1] = tp;
                for(i = 0; i < 8; i++){
                    key[i] = temp[i%2];
                }
                keyschedule(key);
                temp = kasumi_enc(text);
            }
        }
    }

    for(t=0;t<chainLength;t++){
        i = inTable(ep[t],ciphertext,text);
        if (i>0){return 1;}
    } 

    return 0;
}

- Becktor