Implementation of Rainbow table

Question

I'm trying to implement the online phase of a rainbow table attack on the GSM networks KASUMI cipher.

I'm not using the full 128 bit keyspace only 32 bit. Below is my implementation. I have generated a single rainbow table with 2²⁵ rows and 2^7.88 chains links for each row this should give a success ratio on 73%.

To save space we only save the endpoints. Table is saved as a binary file. I can find a startpoint by checking what position the endpoint is in the table. So the third endpoint has a start point that is md5 of 3, fourth has md5 of 4 and so on.

So the issue is when testing with random keys I get a success ratio on 10-15%. To check that we generate the right chains I have used startpoints as keys and here I get 100% success which is expected.

I fear that it might have something to do with endianness but I'm not sure.

#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

Ok, after much fiddeling I found that the endpoints i created was done wrong, and my reduction function was wrong. The online phase should create t points that will be checked with the table first one will be the last used reduction function on the Ciphertext, the second the last reduction function the encryption and then the second to last reduction function and so on untill we reach t different points. This has been edited in the code which is added below.

The reduction function was changed to

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

and the OnlinePhase function was changed to

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