彩虹 table 的实施

Question

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

我没有使用完整的 128 位密钥space只有 32 位。下面是我的实现。我已经生成了一个彩虹 table，其中包含 2²⁵ 行和每行的 2^7.88 链链接，这应该给出成功率73%。

为了保存 space 我们只保存端点。 Table 保存为二进制文件。我可以通过检查端点在 table 中的位置来找到起点。所以第三个端点的起点是 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;
}

Answer 1

好吧，折腾了很久发现我创建的端点做错了，我的reduction函数也错了。在线阶段应该创建 t 个点，这些点将用 table 检查，第一个是密文上最后使用的缩减函数，第二个是最后一个加密的缩减函数，然后是倒数第二个缩减函数，依此类推直到我们到达不同的点。这已在下面添加的代码中进行了编辑。

减少功能更改为

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;
}

彩虹 table 的实施

Implementation of Rainbow table

c

cryptography

rainbowtable