Внедрение таблицы Rainbow

Question

Я пытаюсь реализовать онлайн-фазу атаки радужного стола в сетях GSM KASUMI.

Я не использую полное 128-битное пространство ключей только 32 бит. Ниже приводится моя реализация. Я создал один радужный стол с 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; 
} 

Answer 1

Хорошо, после многого поворота я обнаружил, что конечные точки, которые я создал, были сделаны неправильно, и моя функция сокращения была неправильной. Онлайновая фаза должна создать t точек, которые будут проверяться с помощью таблицы. Первая из них будет последней используемой функцией сокращения в Ciphertext, вторая - последней функцией сокращения, а затем второй - последней функцией сокращения и так далее, пока мы не достигнем 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; 
}