/**************************************************************************** * This program finds near-collisions for the FORK-256 compression function. * For algorithm description and the whole theory behind it, please see * IACR e-print archive, report 2006/317, http://eprint.iacr.org/2006/317 . * (C) Scott Contini, Krystian Matusiewicz, 2006-2007 ****************************************************************************/ #include #include #include #include #include /* define this option to use variant of derive1() with the hash tables, * otherwise an optimized variant of derive1() without the hash table is used*/ #define USEHASHTABLE typedef unsigned int WRD; WRD delta[16] = { 0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174 }; /* n-bit left rotation */ #define ROL(x,n) (((x) << (n)) | ((x) >> (32-(n)))) #define f(x) ( (x) + (ROL((x),7) ^ ROL((x),22)) ) #define g(x) ( (x) ^ (ROL((x),13) + ROL((x),27)) ) /*using different size of the hash table affects efficiency of the program. The bigger the hash table, the better properties of the table lookup, but on the other hand, accessing memory outside cache is much slower on Pentium processors. HASH_SIZE is the number of elements in the hash table (different from the size in memory!) */ #if 0 const int HASH_SIZE = 8388593; #else const int HASH_SIZE = ( 1 << 25 ); #endif /* this variable stores the amount of memory reserved for the hash table*/ int HASH_MEM; /* step transformation */ #define step(A,B,C,D,E,F,G,H,M1,M2,D1,D2) \ temp = (H + ROL(g(E+M2),21)) ^ ROL(f(E+M2+D2),17); \ H = (G + ROL(g(E+M2),9)) ^ ROL(f(E+M2+D2),5); \ G = (F + g(E+M2)) ^ f(E+M2+D2); \ F = E + M2 + D2; \ E = (D + ROL(f(A+M1),17)) ^ ROL(g(A+M1+D1),21); \ D = (C + ROL(f(A+M1),5)) ^ ROL(g(A+M1+D1),9); \ C = (B + f(A+M1)) ^ g(A+M1+D1); \ B = A + M1 + D1; \ A = temp; /* inverse of step transformation (step backwards) */ #define back(A,B,C,D,E,F,G,H,M1,M2,D1,D2) \ temp = A; \ temp2 = B; \ A = B - M1 - D1; \ B = (C ^ g(B)) - f(B-D1); \ C = (D ^ ROL(g(temp2),9)) - ROL(f(temp2-D1),5); \ D = (E ^ ROL(g(temp2),21)) - ROL(f(temp2-D1),17); \ E = F - M2 - D2; \ temp2 = G; \ G = (H ^ ROL(f(F),5)) - ROL(g(F-D2),9); \ H = (temp ^ ROL(f(F),17)) - ROL(g(F-D2),21); \ F = (temp2 ^ f(F)) - g(F-D2); \ /* 32-bit pseudorandom word, even for RNGs that return only 16 bits */ #define RANDOM_WORD (((WRD) rand() & 0xffff)<<16) | (rand() & 0xffff); /** returns Hamming weight of x*/ int hammingWeight(WRD x) { x -= (x >> 1) & 0x55555555; x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x + (x >> 4)) & 0x0f0f0f0f; x += x >> 8; x += x >> 16; return x & 0x3f; }/*hammingWeight()*/ /** This function returns 1 if the additive difference y1-y2 * can be transformed by adding a constant so that it "fits" * into XOR difference dz ie. when a "microcollision" can happen */ int micro_possible( WRD y1, WRD y2, WRD dz) { WRD tmp, delta_y; WRD sum; /* make y1 > y2 : */ if (y2 > y1) { tmp = y2; y2 = y1; y1 = tmp; } delta_y = y1 - y2; sum = delta_y; sum += dz; if (sum < delta_y) { /* overflow */ if ((dz>>31)==0) /* no solution! */ return 0; } dz <<= 1; return ( (dz|sum) == dz ); }/*micro_possible()*/ /** determine which bits of "u" must have 1's and which must have 0's */ void get_ones_and_zeros(WRD y1, WRD y2, WRD z1, WRD z2, WRD *ones, WRD *zeros){ WRD tmp, delta_y; WRD sum; /* make y1 > y2 : */ if (y2 > y1) { tmp = y2; y2 = y1; y1 = tmp; tmp = z2; z2 = z1; z1 = tmp; } tmp = z1 ^ z2; delta_y = y1 - y2; sum = delta_y; sum += tmp; tmp <<= 1; *ones = (tmp&sum) >> 1; *zeros = ((tmp&sum) ^ tmp) >> 1; }/*get_ones_and_zeros()*/ /** Compression function of FORK-256 that based on the value of * chaining variables CV and message M updates the state of * chaining variables CV */ void FORK256_compression_function(WRD CV[8],WRD M[16]) { WRD A1,B1,C1,D1,E1,F1,G1,H1; WRD A2,B2,C2,D2,E2,F2,G2,H2; WRD A3,B3,C3,D3,E3,F3,G3,H3; WRD A4,B4,C4,D4,E4,F4,G4,H4; WRD temp; A1 = A2 = A3 = A4 = CV[0]; B1 = B2 = B3 = B4 = CV[1]; C1 = C2 = C3 = C4 = CV[2]; D1 = D2 = D3 = D4 = CV[3]; E1 = E2 = E3 = E4 = CV[4]; F1 = F2 = F3 = F4 = CV[5]; G1 = G2 = G3 = G4 = CV[6]; H1 = H2 = H3 = H4 = CV[7]; /* BRANCH1(CV,M) */ step(A1,B1,C1,D1,E1,F1,G1,H1,M[0],M[1],delta[0],delta[1]); step(A1,B1,C1,D1,E1,F1,G1,H1,M[2],M[3],delta[2],delta[3]); step(A1,B1,C1,D1,E1,F1,G1,H1,M[4],M[5],delta[4],delta[5]); step(A1,B1,C1,D1,E1,F1,G1,H1,M[6],M[7],delta[6],delta[7]); step(A1,B1,C1,D1,E1,F1,G1,H1,M[8],M[9],delta[8],delta[9]); step(A1,B1,C1,D1,E1,F1,G1,H1,M[10],M[11],delta[10],delta[11]); step(A1,B1,C1,D1,E1,F1,G1,H1,M[12],M[13],delta[12],delta[13]); step(A1,B1,C1,D1,E1,F1,G1,H1,M[14],M[15],delta[14],delta[15]); /* BRANCH2(CV,M) */ step(A2,B2,C2,D2,E2,F2,G2,H2,M[14],M[15],delta[15],delta[14]); step(A2,B2,C2,D2,E2,F2,G2,H2,M[11],M[9],delta[13],delta[12]); step(A2,B2,C2,D2,E2,F2,G2,H2,M[8],M[10],delta[11],delta[10]); step(A2,B2,C2,D2,E2,F2,G2,H2,M[3],M[4],delta[9],delta[8]); step(A2,B2,C2,D2,E2,F2,G2,H2,M[2],M[13],delta[7],delta[6]); step(A2,B2,C2,D2,E2,F2,G2,H2,M[0],M[5],delta[5],delta[4]); step(A2,B2,C2,D2,E2,F2,G2,H2,M[6],M[7],delta[3],delta[2]); step(A2,B2,C2,D2,E2,F2,G2,H2,M[12],M[1],delta[1],delta[0]); /* BRANCH3(CV,M) */ step(A3,B3,C3,D3,E3,F3,G3,H3,M[7],M[6],delta[1],delta[0]); step(A3,B3,C3,D3,E3,F3,G3,H3,M[10],M[14],delta[3],delta[2]); step(A3,B3,C3,D3,E3,F3,G3,H3,M[13],M[2],delta[5],delta[4]); step(A3,B3,C3,D3,E3,F3,G3,H3,M[9],M[12],delta[7],delta[6]); step(A3,B3,C3,D3,E3,F3,G3,H3,M[11],M[4],delta[9],delta[8]); step(A3,B3,C3,D3,E3,F3,G3,H3,M[15],M[8],delta[11],delta[10]); step(A3,B3,C3,D3,E3,F3,G3,H3,M[5],M[0],delta[13],delta[12]); step(A3,B3,C3,D3,E3,F3,G3,H3,M[1],M[3],delta[15],delta[14]); /* BRANCH4(CV,M) */ step(A4,B4,C4,D4,E4,F4,G4,H4,M[5],M[12],delta[14],delta[15]); step(A4,B4,C4,D4,E4,F4,G4,H4,M[1],M[8],delta[12],delta[13]); step(A4,B4,C4,D4,E4,F4,G4,H4,M[15],M[0],delta[10],delta[11]); step(A4,B4,C4,D4,E4,F4,G4,H4,M[13],M[11],delta[8],delta[9]); step(A4,B4,C4,D4,E4,F4,G4,H4,M[3],M[10],delta[6],delta[7]); step(A4,B4,C4,D4,E4,F4,G4,H4,M[9],M[2],delta[4],delta[5]); step(A4,B4,C4,D4,E4,F4,G4,H4,M[7],M[14],delta[2],delta[3]); step(A4,B4,C4,D4,E4,F4,G4,H4,M[4],M[6],delta[0],delta[1]); /* output : applying feed-forward */ CV[0] = CV[0] + ((A1 + A2) ^ (A3 + A4)); CV[1] = CV[1] + ((B1 + B2) ^ (B3 + B4)); CV[2] = CV[2] + ((C1 + C2) ^ (C3 + C4)); CV[3] = CV[3] + ((D1 + D2) ^ (D3 + D4)); CV[4] = CV[4] + ((E1 + E2) ^ (E3 + E4)); CV[5] = CV[5] + ((F1 + F2) ^ (F3 + F4)); CV[6] = CV[6] + ((G1 + G2) ^ (G3 + G4)); CV[7] = CV[7] + ((H1 + H2) ^ (H3 + H4)); }/* FORK256_compression_function() */ #ifdef USEHASHTABLE /************************ HASH TABLE STUFF ******************************/ /************************ HASH TABLE STUFF ******************************/ /************************ HASH TABLE STUFF ******************************/ /** * Given modular difference diff , determine the set of values for * strand A in step 7 of branch 1 that can posibly cause a microcollision * in strand D. */ void get_allowable_values( WRD diff, WRD allowable[], int * count ) { WRD x1, y1; WRD x2, y2; WRD dz; FILE * fp; char fileName[20] = {0}; long fileSize; /*test if we already have a file with precomputed values * its name should be allowable-hexdiff.dat * where hexdiff is 8 hex digits representing the difference diff*/ sprintf(fileName,"allowable-%08x.dat",diff); fp = fopen(fileName,"r"); if ( fp ) { /*determine file size*/ printf("Using precomputed file %s. ",fileName); fseek(fp,0,SEEK_END); fileSize = ftell(fp); printf("Size: %ld B (%ld values)\n",fileSize, fileSize/sizeof(WRD)); fseek(fp,0,SEEK_SET); /*read the data into table */ fread(allowable,fileSize / sizeof(WRD), sizeof(WRD),fp); fclose(fp); (*count) = fileSize/sizeof(WRD); } else { printf("Precomputing allowable values... Please be patient!\n"); printf("| 0 %% | 50 %% | 100 %%\n"); x1 = 0; do { x2 = x1 + diff; y1 = f(x1); y2 = f(x2); dz = g(x1 + delta[12]) ^ g(x2 + delta[12]); if ( micro_possible(ROL(y1,17),ROL(y2,17),ROL(dz,21)) ) { allowable[*count] = x1; ++*count; } ++x1; if ( (x1 & 0x3ffffff)==0 ) { printf("*"); fflush(stdout); } } while (x1 != 0); printf("\nnumber of allowable values is %d\n\n",*count); fflush(stdout); /*write precomputed allowable values to the file "allowable-hexdiff.dat" * where hexdiff is a hexadecimal representation of the difference*/ sprintf(fileName,"allowable-%08x.dat",diff); fp = fopen(fileName,"w"); fwrite(allowable,(*count),sizeof(WRD),fp); fclose(fp); } }/* get_allowable_values() */ /** Inserts value H into hash table pointed by hash_table */ void insert_into_hash_table( WRD H, unsigned char hash_table[] ) { int i; i = H % HASH_SIZE; hash_table[i>>3] |= 1 << (i&7); }/* insert_into_hash_table() */ /** returns non-zero if the value H is in the hash table hash_table, * zero if not */ int is_in_hash_table( WRD H, unsigned char hash_table[] ) { int i = H % HASH_SIZE; return (hash_table[i>>3] >> (i&7))&1; } /* is_in_hash_table() */ /** We want to determine all allowable outputs to the G strand of * step 5 of branch 1 (note output of G_5 = input to H_6), and store * these in a hash table. */ void prepare_hash_table(WRD IV[8], WRD M[16], WRD M12prime, WRD allowable[], int count, unsigned char hash_table[]) { WRD A1,B1,C1,D1,E1,F1,G1,H1; WRD temp, temp2; WRD A1_1,B1_1,C1_1,D1_1,E1_1,F1_1,G1_1,H1_1; int i; printf("\nBuilding hash table..."); memset( hash_table, 0, HASH_MEM ); A1 = IV[0]; B1 = IV[1]; C1 = IV[2]; D1 = IV[3]; E1 = IV[4]; F1 = IV[5]; G1 = IV[6]; H1 = IV[7]; step(A1,B1,C1,D1,E1,F1,G1,H1,M[0],M[1],delta[0],delta[1]); step(A1,B1,C1,D1,E1,F1,G1,H1,M[2],M[3],delta[2],delta[3]); step(A1,B1,C1,D1,E1,F1,G1,H1,M[4],M[5],delta[4],delta[5]); step(A1,B1,C1,D1,E1,F1,G1,H1,M[6],M[7],delta[6],delta[7]); step(A1,B1,C1,D1,E1,F1,G1,H1,M[8],M[9],delta[8],delta[9]); step(A1,B1,C1,D1,E1,F1,G1,H1,M[10],M[11],delta[10],delta[11]); A1_1 = A1; B1_1 = B1; C1_1 = C1; D1_1 = D1; E1_1 = E1; F1_1 = F1; G1_1 = G1; H1_1 = H1; for (i=0; i < count; ++i) { A1 = allowable[i] - M[12]; B1 = B1_1; C1 = C1_1; D1 = D1_1; E1 = E1_1; F1 = F1_1; G1 = G1_1; H1 = H1_1; back(A1,B1,C1,D1,E1,F1,G1,H1,M[10],M[11],delta[10],delta[11]); insert_into_hash_table( H1, hash_table ); } printf(" done!\n\n"); fflush(stdout); }/* prepare_hash_table() */ void advance_M4( WRD IV[8], WRD M[16], WRD M12prime, WRD allowable[], int count, unsigned char hash_table[] ) { ++M[4]; prepare_hash_table( IV, M, M12prime, allowable, count, hash_table ); }/* advance_M4() */ /** This is a version of derive1 using hash tables. The procedure * looks for such values of M[4] and M[9] that the difference * in A6 of branch 1 does not propagate to E7 (single microcollision * in the third line of the left Q-structure in step 7 of branch 1*/ void derive1hash(WRD CV[8],WRD M[16], WRD M12p, WRD allowable[], WRD a_count, unsigned char hash_table[] ) { WRD A,B,C,D,E,F,G,H; WRD A5,C5,D5,E5,H5; WRD A6,D6, E7_1=0, E7_2=1; WRD const1, const2; WRD temp; int i; printf("\nsolving for branch 1...\n"); do { A = CV[0]; B = CV[1]; C = CV[2]; D = CV[3]; E = CV[4]; F = CV[5]; G = CV[6]; H = CV[7]; step(A,B,C,D,E,F,G,H,M[0],M[1],delta[0],delta[1]); /* step 1 */ step(A,B,C,D,E,F,G,H,M[2],M[3],delta[2],delta[3]); /* step 2 */ step(A,B,C,D,E,F,G,H,M[4],M[5],delta[4],delta[5]); /* step 3 */ step(A,B,C,D,E,F,G,H,M[6],M[7],delta[6],delta[7]); /* step 4 */ /*precompute necessary registers of step 5 beforehand */ C5 = (B + f(A+M[8])) ^ g(A+M[8]+delta[8]); D5 = (C + ROL(f(A+M[8]),5)) ^ ROL(g(A+M[8]+delta[8]),9); E5 = (D + ROL(f(A+M[8]),17)) ^ ROL(g(A+M[8]+delta[8]),21); const1 = ROL(g(E5+M[11]),21); const2 = ROL(f(E5+M[11]+delta[11]),17); do { H5 = (G + ROL(g(E+M[9]),9)) ^ ROL(f(E+M[9]+delta[9]),5); /*check hash table */ i = H5 % HASH_SIZE; if ((hash_table[i>>3] >> (i&7))&1) { /*H_5 is in a hash table: it corresponds to one of the * allowable values -- so now we need to test it */ A5 = (H + ROL(g(E+M[9]),21)) ^ ROL(f(E+M[9]+delta[9]),17); A6 = (H5 + const1) ^ const2; D6 = (C5 + ROL(f(A5+M[10]),5)) ^ ROL(g(A5+M[10]+delta[10]),9); E7_1 = (D6 + ROL(f(A6+M[12]),17))^ROL(g(A6+M[12]+delta[12]),21); E7_2 = (D6 + ROL(f(A6+M12p ),17))^ROL(g(A6+ M12p+delta[12]),21); if (E7_1 == E7_2) { printf("M[4] = 0x%.8x; M[9] = 0x%.8x;\n",M[4], M[9]); break; /*break out of the inner while loop (modifying M[9])*/ } } ++M[9]; } while( M[9] != 0 ); if ( E7_1 != E7_2 ) { advance_M4( CV, M, M12p, allowable, a_count, hash_table ); } } while (E7_1 != E7_2); }/* derive1hash() */ /************ END OF HASH TABLE SPECIFIC CODE ****************************/ /************ END OF HASH TABLE SPECIFIC CODE ****************************/ /************ END OF HASH TABLE SPECIFIC CODE ****************************/ #endif /* end of code for variant using hash tables */ /*** This function advances values of M[4] and M[9] until * it finds a value that yields zero difference in register * E after step 7 in branch 1 * * Optimized version without hash tables */ void derive1opt(WRD CV[8],WRD M[16], WRD M12p) { WRD A,B,C,D,E,F,G,H; WRD E7_1, E7_2; WRD A5, C5, D5, E5, H5; WRD A6, D6; WRD const1, const2; WRD temp; printf("\nsolving for branch 1...\n"); do { A = CV[0]; B = CV[1]; C = CV[2]; D = CV[3]; E = CV[4]; F = CV[5]; G = CV[6]; H = CV[7]; step(A,B,C,D,E,F,G,H,M[0],M[1],delta[0],delta[1]); /* step 1*/ step(A,B,C,D,E,F,G,H,M[2],M[3],delta[2],delta[3]); /* step 2*/ step(A,B,C,D,E,F,G,H,M[4],M[5],delta[4],delta[5]); /* step 3*/ step(A,B,C,D,E,F,G,H,M[6],M[7],delta[6],delta[7]); /* step 4*/ C5 = (B + f(A+M[8])) ^ g(A+M[8]+delta[8]); D5 = (C + ROL(f(A+M[8]),5)) ^ ROL(g(A+M[8]+delta[8]),9); E5 = (D + ROL(f(A+M[8]),17)) ^ ROL(g(A+M[8]+delta[8]),21); const1 = ROL(g(E5+M[11]),21); const2 = ROL(f(E5+M[11]+delta[11]),17); do { H5 = (G + ROL(g(E+M[9]), 9)) ^ ROL(f(E+M[9]+delta[9]),5); A5 = (H + ROL(g(E+M[9]),21)) ^ ROL(f(E+M[9]+delta[9]),17); A6 = (H5 + const1) ^ const2; D6 = (C5 + ROL(f(A5+M[10]),5)) ^ ROL(g(A5+M[10]+delta[10]),9); E7_1 = (D6 + ROL(f(A6+M[12]),17)) ^ ROL(g(A6+M[12]+delta[12]),21); E7_2 = (D6 + ROL(f(A6+M12p ),17)) ^ ROL(g(A6+ M12p+delta[12]),21); if (E7_1 == E7_2) { printf("M[4] = 0x%.8x; M[9] = 0x%.8x;\n",M[4], M[9]); break; }/*if E7_1 == E7_2 */ ++M[9]; } while( M[9] != 0 ); if (E7_1 != E7_2) { ++M[4]; } } while (E7_1 != E7_2); }/* derive1opt() */ /*** This function solves for branch 3 */ int derive3(WRD CV[8],WRD M[16], WRD M12p ) { WRD A3,B3,C3,D3,E3,F3,G3,H3; WRD A,B,C,D,E,F,G,H; WRD holdF; WRD temp, temp2; WRD origE3; WRD y1, y2, z1, z2, dz; WRD ones, zeros; WRD mem1; printf("\nsolving for branch 3...\n"); A3 = CV[0]; B3 = CV[1]; C3 = CV[2]; D3 = CV[3]; E3 = CV[4]; F3 = CV[5]; G3 = CV[6]; H3 = CV[7]; step(A3,B3,C3,D3,E3,F3,G3,H3,M[7],M[6],delta[1],delta[0]); mem1 = A3 + M[10]; step(A3,B3,C3,D3,E3,F3,G3,H3,M[10],M[14],delta[3],delta[2]); step(A3,B3,C3,D3,E3,F3,G3,H3,M[13],M[2],delta[5],delta[4]); origE3 = E3; do { y1 = g(E3 + M[12]); y2 = g(E3 + M12p); z1 = f(E3 + M[12] + delta[6]); z2 = f(E3 + M12p + delta[6]); dz = z1 ^ z2; if (micro_possible( y1, y2, dz) && micro_possible(ROL(y1,9),ROL(y2,9),ROL(dz,5)) && micro_possible(ROL(y1,21),ROL(y2,21),ROL(dz,17)) ) { break; } ++E3; } while (E3 != origE3); if (!( micro_possible( y1, y2, dz) && micro_possible(ROL(y1,9),ROL(y2,9),ROL(dz,5)) && micro_possible(ROL(y1,21),ROL(y2,21),ROL(dz,17)) )) { printf("no solution for branch 3!\n"); return 1; } A = A3; B = B3; C = C3; D = D3; E = E3; get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros ); if (y1 > y2) F = F3 = ones - y1; else F = F3 = ones - y2; y1 = ROL(y1,9); y2 = ROL(y2,9); z1 = ROL(z1,5); z2 = ROL(z2,5); get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros ); if (y1 > y2) G = G3 = ones - y1; else G = G3 = ones - y2; y1 = ROL(y1,12); y2 = ROL(y2,12); z1 = ROL(z1,12); z2 = ROL(z2,12); get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros ); if (y1 > y2) H = H3 = ones - y1; else H = H3 = ones - y2; /* These are the values we want at the beginning of step 3: */ A3 = A; B3 = B; C3 = C; D3 = D; E3 = E; F3 = F; G3 = G; H3 = H; back(A3,B3,C3,D3,E3,F3,G3,H3,M[13],M[2],delta[5],delta[4]); back(A3,B3,C3,D3,E3,F3,G3,H3,M[10],M[14],delta[3],delta[2]); M[6] = F3 - delta[0] - CV[4]; printf("M[6] = 0x%.8x;\n",M[6]); A3 = CV[0]; B3 = CV[1]; C3 = CV[2]; D3 = CV[3]; E3 = CV[4]; F3 = CV[5]; G3 = CV[6]; H3 = CV[7]; step(A3,B3,C3,D3,E3,F3,G3,H3,M[7],M[6],delta[1],delta[0]); M[10] = mem1 - A3; printf("M[10] = 0x%.8x;\n",M[10]); /* These are the values we want at the beginning of step 3: */ A3 = A; B3 = B; C3 = C; D3 = D; E3 = E; F3 = F; G3 = G; H3 = H; back(A3,B3,C3,D3,E3,F3,G3,H3,M[13],M[2],delta[5],delta[4]); holdF = F3; A3 = CV[0]; B3 = CV[1]; C3 = CV[2]; D3 = CV[3]; E3 = CV[4]; F3 = CV[5]; G3 = CV[6]; H3 = CV[7]; step(A3,B3,C3,D3,E3,F3,G3,H3,M[7],M[6],delta[1],delta[0]); M[14] = holdF - E3 - delta[2]; printf("M[14] = 0x%.8x;\n",M[14]); A3 = CV[0]; B3 = CV[1]; C3 = CV[2]; D3 = CV[3]; E3 = CV[4]; F3 = CV[5]; G3 = CV[6]; H3 = CV[7]; step(A3,B3,C3,D3,E3,F3,G3,H3,M[7],M[6],delta[1],delta[0]); step(A3,B3,C3,D3,E3,F3,G3,H3,M[10],M[14],delta[3],delta[2]); M[2] = F - E3 - delta[4]; printf("M[2] = 0x%.8x;\n",M[2]); /* These are the values we want at the beginning of step 3: */ A3 = CV[0]; B3 = CV[1]; C3 = CV[2]; D3 = CV[3]; E3 = CV[4]; F3 = CV[5]; G3 = CV[6]; H3 = CV[7]; step(A3,B3,C3,D3,E3,F3,G3,H3,M[7],M[6],delta[1],delta[0]); step(A3,B3,C3,D3,E3,F3,G3,H3,M[10],M[14],delta[3],delta[2]); step(A3,B3,C3,D3,E3,F3,G3,H3,M[13],M[2],delta[5],delta[4]); E3 = E; back(A3,B3,C3,D3,E3,F3,G3,H3,M[13],M[2],delta[5],delta[4]); back(A3,B3,C3,D3,E3,F3,G3,H3,M[10],M[14],delta[3],delta[2]); back(A3,B3,C3,D3,E3,F3,G3,H3,M[7],M[6],delta[1],delta[0]); CV[1] = B3; printf("IV[1] = 0x%.8x;\n",CV[1]); return 0; }/* derive3() */ /*** This function solves for branch4 */ int derive4(WRD CV[8], WRD M[16], WRD M12p, WRD * origE4step3plusM11) { WRD A4,B4,C4,D4,E4,F4,G4,H4; WRD A4p,B4p,C4p,D4p,E4p,F4p,G4p,H4p; WRD temp, temp2; WRD M3 = 0; WRD ones, zeros; WRD B, C, D; WRD A, E, F, G, H; WRD z1, z2, dz, y1, y2; WRD holdB, mem1, mem2; printf("\nsolving for branch 4...\n"); A4 = A4p = CV[0]; B4 = B4p = CV[1]; C4 = C4p = CV[2]; D4 = D4p = CV[3]; E4 = E4p = CV[4]; F4 = F4p = CV[5]; G4 = G4p = CV[6]; H4 = H4p = CV[7]; step(A4,B4,C4,D4,E4,F4,G4,H4,M[5],M[12],delta[14],delta[15]); step(A4,B4,C4,D4,E4,F4,G4,H4,M[1],M[8],delta[12],delta[13]); mem1 = E4 + M[0]; step(A4,B4,C4,D4,E4,F4,G4,H4,M[15],M[0],delta[10],delta[11]); mem2 = E4 + M[11]; step(A4,B4,C4,D4,E4,F4,G4,H4,M[13],M[11],delta[8],delta[9]); step(A4p,B4p,C4p,D4p,E4p,F4p,G4p,H4p,M[5],M12p,delta[14],delta[15]); step(A4p,B4p,C4p,D4p,E4p,F4p,G4p,H4p,M[1],M[8],delta[12],delta[13]); step(A4p,B4p,C4p,D4p,E4p,F4p,G4p,H4p,M[15],M[0],delta[10],delta[11]); step(A4p,B4p,C4p,D4p,E4p,F4p,G4p,H4p,M[13],M[11],delta[8],delta[9]); do { y1 = f( A4 + M3 ); y2 = f( A4p + M3 ); z1 = g( A4 + M3 + delta[6] ); z2 = g( A4p + M3 + delta[6] ); dz = z1 ^ z2; if (micro_possible( y1, y2, dz) && micro_possible(ROL(y1,5),ROL(y2,5),ROL(dz,9)) && micro_possible(ROL(y1,17),ROL(y2,17),ROL(dz,21)) ) break; ++M3; } while (M3 != 0); if (!(micro_possible( y1, y2, dz) && micro_possible(ROL(y1,5),ROL(y2,5),ROL(dz,9)) && micro_possible(ROL(y1,17),ROL(y2,17),ROL(dz,21)) )) { printf("no solution for branch 4!\n"); return 1; } /* now we want to set up B, C, and D to be what we want by choosing * the right values for M[8], M[0], and M[11]. */ M[3] = M3; printf("M[3] = 0x%.8x\n",M[3]); get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros ); if (y1 > y2) B = B4 = B4p = ones - y1; else B = B4 = B4p = ones - y2; y1 = ROL(y1,5); y2 = ROL(y2,5); z1 = ROL(z1,9); z2 = ROL(z2,9); get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros ); if (y1 > y2) C = C4 = C4p = ones - y1; else C = C4 = C4p = ones - y2; y1 = ROL(y1,12); y2 = ROL(y2,12); z1 = ROL(z1,12); z2 = ROL(z2,12); get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros ); if (y1 > y2) D = D4 = D4p = ones - y1; else D = D4 = D4p = ones - y2; A = A4; E = E4; F = F4; G = G4; H = H4; back(A4,B4,C4,D4,E4,F4,G4,H4,M[13],M[11],delta[8],delta[9]); back(A4,B4,C4,D4,E4,F4,G4,H4,M[15],M[0],delta[10],delta[11]); holdB = B4; A4 = CV[0]; B4 = CV[1]; C4 = CV[2]; D4 = CV[3]; E4 = CV[4]; F4 = CV[5]; G4 = CV[6]; H4 = CV[7]; step(A4,B4,C4,D4,E4,F4,G4,H4,M[5],M[12],delta[14],delta[15]); /* compute the new M[1]: */ M[1]=holdB-delta[12]-A4; printf("M[1] = 0x%.8x;\n",M[1]); /* compute the new M[0]: */ y2 = ROL( f(A4 + M[1]), 17 ); z2 = ROL( g(A4 + M[1] + delta[12]), 21 ); M[0] = mem1 - ((D4 + y2) ^ z2); printf("M[0] = 0x%.8x;\n",M[0]); /* now we go back to the 5th step again and set our variables * accordingly. then we will step back to determine the new * m[15], m[11]. */ A4 = A; B4 = B; C4 = C; D4 = D; E4 = E; F4 = F; G4 = G; H4 = H; back(A4,B4,C4,D4,E4,F4,G4,H4,M[13],M[11],delta[8],delta[9]); holdB = B4; A4 = CV[0]; B4 = CV[1]; C4 = CV[2]; D4 = CV[3]; E4 = CV[4]; F4 = CV[5]; G4 = CV[6]; H4 = CV[7]; step(A4,B4,C4,D4,E4,F4,G4,H4,M[5],M[12],delta[14],delta[15]); step(A4,B4,C4,D4,E4,F4,G4,H4,M[1],M[8],delta[12],delta[13]); /* compute the new M[15]: */ M[15]=holdB-delta[10]-A4; printf("M[15] = 0x%.8x;\n",M[15]); /* compute the new M[11]: */ y2 = ROL( f(A4 + M[15]), 17 ); z2 = ROL( g(A4 + M[15] + delta[10]), 21 ); M[11] = mem2 - ((D4 + y2) ^ z2); printf("M[11] = 0x%.8x;\n",M[11]); /* Finally we determine new M[13] */ holdB = B; A4 = CV[0]; B4 = CV[1]; C4 = CV[2]; D4 = CV[3]; E4 = CV[4]; F4 = CV[5]; G4 = CV[6]; H4 = CV[7]; step(A4,B4,C4,D4,E4,F4,G4,H4,M[5],M[12],delta[14],delta[15]); step(A4,B4,C4,D4,E4,F4,G4,H4,M[1],M[8],delta[12],delta[13]); step(A4,B4,C4,D4,E4,F4,G4,H4,M[15],M[0],delta[10],delta[11]); /* compute the new M[13]: */ M[13]=holdB-delta[8]-A4; printf("M[13] = 0x%.8x;\n",M[13]); A4 = CV[0]; B4 = CV[1]; C4 = CV[2]; D4 = CV[3]; E4 = CV[4]; F4 = CV[5]; G4 = CV[6]; H4 = CV[7]; step(A4,B4,C4,D4,E4,F4,G4,H4,M[5],M[12],delta[14],delta[15]); step(A4,B4,C4,D4,E4,F4,G4,H4,M[1],M[8],delta[12],delta[13]); step(A4,B4,C4,D4,E4,F4,G4,H4,M[15],M[0],delta[10],delta[11]); *origE4step3plusM11 = E4 + M[11]; return 0; }/* derive4() */ /** Corrects the value of M11 after solving for branch 3 */ void fixM11( WRD CV[8],WRD M[16], WRD origE4step3plusM11 ) { WRD A4,B4,C4,D4,E4,F4,G4,H4; WRD temp; printf("\nfixing M[11]...\n"); A4 = CV[0]; B4 = CV[1]; C4 = CV[2]; D4 = CV[3]; E4 = CV[4]; F4 = CV[5]; G4 = CV[6]; H4 = CV[7]; step(A4,B4,C4,D4,E4,F4,G4,H4,M[5],M[12],delta[14],delta[15]); step(A4,B4,C4,D4,E4,F4,G4,H4,M[1],M[8],delta[12],delta[13]); step(A4,B4,C4,D4,E4,F4,G4,H4,M[15],M[0],delta[10],delta[11]); M[11] = origE4step3plusM11 - E4; printf("M[11] = 0x%.8x;\n",M[11]); }/* fixM11() */ /** Picks randomly M[12] and necessary constants in IV[5,6,7] */ void choose_M12_and_IV( WRD IV[8], WRD diff, WRD * M12, WRD * M12prime ) { WRD E; WRD x1, x2; WRD y1, y2; WRD z1, z2, dz; WRD F, G, H, ones, zeros; WRD startWith; printf("\nsolving for IV[5,6,7] and M[12]...\n"); fflush(stdout); E = IV[4]; /* *M12 = 0x1811f2d9; */ /*choosing a random value from the set of candidates for M12 */ startWith = RANDOM_WORD; *M12 = startWith; do { x1 = E + *M12; x2 = E + *M12 + diff; y1 = g(x1); y2 = g(x2); z1 = f((x1+delta[15])); z2 = f((x2+delta[15])); dz = z1 ^ z2; if (micro_possible( y1, y2, dz) && micro_possible(ROL(y1,9),ROL(y2,9),ROL(dz,5)) & micro_possible(ROL(y1,21),ROL(y2,21),ROL(dz,17)) ) { get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros ); if (y1 > y2) F = ones - y1; else F = ones - y2; y1 = ROL(y1,9); y2 = ROL(y2,9); z1 = ROL(z1,5); z2 = ROL(z2,5); get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros ); if (y1 > y2) G = ones - y1; else G = ones - y2; y1 = ROL(y1,12); y2 = ROL(y2,12); z1 = ROL(z1,12); z2 = ROL(z2,12); get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros ); if (y1 > y2) H = ones - y1; else H = ones - y2; *M12prime = *M12 + diff; printf("M[12] = 0x%.8x;\n M12p = 0x%.8x;\n",*M12,*M12prime); printf("IV[5] = 0x%.8x\n",F); IV[5] = F; printf("IV[6] = 0x%.8x\n",G); IV[6] = G; printf("IV[7] = 0x%.8x\n",H); IV[7] = H; return; } (*M12)++; } while ( (*M12) != startWith ); /* If we are here, no microcollision could be found for this additive * difference, something is wrong! */ printf("Illegal input difference!\n"); exit(1); }/* choose_M12_and_IV() */ int main(int argc, char * argv[]) { int i,hmwt; WRD IV[8] = { 0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x70852362, 0x923cf4a3, 0x4f4a3124 }; WRD M[16], CV1[8], CV2[8], M12prime, M12; WRD origE4step3plusM11; WRD out_diff[8]; int seed = 0; FILE *fp; WRD diff = 0x22f80000; /*WRD diff = 0xdd080000;*/ /*WRD diff = 0x5a100000;*/ int num_sols = 0; double count = 0.0; WRD startM4 = 0xfeefffff; /* to store the initial value of M4 we start with */ const int MAXWT = 38; /* maximum weight of output diffs we want to output */ double globalCPUtimederive1 = 0; /*total CPU time spent in derive1() */ clock_t clockStart, clockEnd; char filename[1024]; #ifdef USEHASHTABLE WRD * allowable = malloc( (1<<22)*sizeof(WRD) ); int a_count = 0; unsigned char * hash_table = malloc( (HASH_SIZE + 7)/8 ); HASH_MEM = (HASH_SIZE + 7)/8; #endif /* pseudorandom numbers are used in * - choose_M12_and_IV() to pick a random value of M12 from the * set of potentially producing microcollision * - before derive1() to initialize some message words */ /* if possible, read the seed from first command-line parameter */ if ((argc > 1) && (sscanf(argv[1],"%d",&seed)>0) ) { printf("Using seed : %d \n",seed); } else { /*if not, read the seed from the input*/ printf("\n\n\nEnter seed: "); fflush(stdout); scanf("%d",&seed); } srand(seed); sprintf(filename,"solutions%d.txt",seed); #ifdef USEHASHTABLE get_allowable_values( diff, allowable, &a_count ); #endif choose_M12_and_IV( IV, diff, &M12, &M12prime ); /* set up first message */ for (i=0; i < 16; ++i) { M[i] = 0; } M[12] = M12; M[4] = startM4; /* start is possible from arbitrary value of M[4] */ do { M[1] = RANDOM_WORD; M[15] = RANDOM_WORD; M[13] = RANDOM_WORD; M[8] = RANDOM_WORD; M[0] = RANDOM_WORD; M[11] = RANDOM_WORD; /* pick random words until it is possible to solve for * branches 4 and 3 */ } while(derive4(IV, M, M12prime, &origE4step3plusM11 ) || derive3(IV, M, M12prime ) ); fixM11( IV, M, origE4step3plusM11 ); #ifdef USEHASHTABLE prepare_hash_table( IV, M, M12prime, allowable, a_count, hash_table ); #endif do { /* main loop that goes through M[4] and M[9] and find near-colls */ clockStart = clock(); /* find near-collision */ #ifdef USEHASHTABLE derive1hash( IV, M, M12prime, allowable, a_count, hash_table ); #else derive1opt( IV, M, M12prime ); #endif clockEnd = clock(); globalCPUtimederive1 += ((double) (clockEnd-clockStart))/CLOCKS_PER_SEC; /* compute the first hash */ for (i=0; i < 8; ++i){ CV1[i] = IV[i]; } FORK256_compression_function( CV1, M ); /* compute the second hash */ M[12] = M12prime; for (i=0; i < 8; ++i){ CV2[i] = IV[i]; } FORK256_compression_function( CV2, M ); /* compute the difference of hashes and its Hamming weight */ hmwt = 0; for (i=0; i < 8; ++i) { out_diff[i] = CV1[i] ^ CV2[i]; hmwt += hammingWeight(out_diff[i]); } /* print to the solutions file hashes with weight less than MAXWT only */ if ( hmwt < MAXWT ) { fp = fopen(filename,"a"); /* print IV */ fprintf(fp, " IV: "); for (i=0; i < 8; ++i) { fprintf(fp,"%.8x ",IV[i]); } fprintf(fp,"\n"); /* print the first message */ fprintf(fp, " M: "); for (i=0; i < 16; ++i) { fprintf(fp,"%.8x ",M[i]); } fprintf(fp,"\n"); /* print M[12] of the second message */ fprintf(fp, "M12': %.8x\n",M12prime); /* print the first hash */ fprintf(fp, " H1: "); for (i=0; i < 8; ++i) { fprintf(fp,"%.8x ",CV1[i]); } fprintf(fp,"\n"); /* print the second hash */ fprintf(fp, " H2: "); for (i=0; i < 8; ++i) { fprintf(fp,"%.8x ",CV2[i]); } fprintf(fp,"\n"); /* print the difference */ fprintf(fp,"diff: "); for (i=0; i < 8; ++i) { fprintf(fp,"%.8x ",out_diff[i]); } fprintf(fp,"\n"); fprintf(fp,"\nHamming weight of difference is %d\n\n",hmwt); fclose(fp); }/*end of printing to solutions file */ ++num_sols; count = 4294967296.0 * (M[4]-startM4) + (double) M[9]; printf("\nSOLUTION NO %d FOUND!!! time %.2f \n\n",num_sols, ((double) (clockEnd-clockStart))/CLOCKS_PER_SEC); printf("Hamming weight of difference is %d\n\n",hmwt); printf("observed probability of passing branch1 is about 2^%.4f\n", (log(num_sols/count)/log(2)) ); fflush(stdout); if ((++M[9]) == 0) ++M[4]; M[12] = M12; } while ( num_sols < 50 ); /* change "while ( num_sols<50 )" to "while ( 1 )" for an infinite loop */ #ifdef USEHASHTABLE free( allowable ); free( hash_table ); #endif printf ("\nTotal time spent in derive1() : %.2f s\n",globalCPUtimederive1); printf ("Average time for a single derive1(): %.3f s\n",globalCPUtimederive1/num_sols); return 0; }/*main()*/