1. /****************************************************************************
  2.  * This program finds near-collisions for the FORK-256 compression function.
  3.  * For algorithm description and the whole theory behind it, please see
  4.  * IACR e-print archive, report 2006/317, http://eprint.iacr.org/2006/317 .
  5.  * (C) Scott Contini, Krystian Matusiewicz, 2006-2007
  6.  ****************************************************************************/ 
  7.  
  8. #include <stdio.h>
  9. #include <math.h>
  10. #include <stdlib.h>
  11. #include <time.h>
  12. #include <string.h>
  13.  
  14. /* define this option to use variant of derive1() with the hash tables,
  15.  * otherwise an optimized variant of derive1() without the hash table is used*/
  16. #define USEHASHTABLE 
  17.  
  18. typedef unsigned int WRD;
  19.  
  20. WRD delta[16] = {
  21. 	0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
  22. 	0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
  23. 	0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
  24. 	0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174
  25. };
  26.  
  27. /* n-bit left rotation */
  28. #define ROL(x,n) (((x) << (n)) | ((x) >> (32-(n))))
  29. #define f(x) ( (x) + (ROL((x),7) ^ ROL((x),22)) )
  30. #define g(x) ( (x) ^ (ROL((x),13) + ROL((x),27)) )
  31.  
  32. /*using different size of the hash table affects efficiency of the
  33.   program. The bigger the hash table, the better properties of the
  34.   table lookup, but on the other hand, accessing memory outside cache 
  35.   is much slower on Pentium processors.
  36.   HASH_SIZE is the number of elements in the hash table (different from
  37.   the size in memory!) */
  38. #if 0
  39. const int HASH_SIZE = 8388593;
  40. #else
  41. const int HASH_SIZE = ( 1 << 25 );
  42. #endif
  43.  
  44. /* this variable stores the amount of memory reserved for the hash table*/
  45. int HASH_MEM; 
  46.  
  47. /* step transformation */
  48. #define step(A,B,C,D,E,F,G,H,M1,M2,D1,D2) \
  49. 	temp = (H + ROL(g(E+M2),21)) ^ ROL(f(E+M2+D2),17); \
  50. 	H = (G + ROL(g(E+M2),9)) ^ ROL(f(E+M2+D2),5); \
  51. 	G = (F + g(E+M2)) ^ f(E+M2+D2); \
  52. 	F = E + M2 + D2; \
  53. 	E = (D + ROL(f(A+M1),17)) ^ ROL(g(A+M1+D1),21); \
  54. 	D = (C + ROL(f(A+M1),5)) ^ ROL(g(A+M1+D1),9); \
  55. 	C = (B + f(A+M1)) ^ g(A+M1+D1); \
  56. 	B = A + M1 + D1; \
  57. 	A = temp;
  58.  
  59. /* inverse of step transformation (step backwards) */
  60. #define back(A,B,C,D,E,F,G,H,M1,M2,D1,D2) \
  61. 	temp = A; \
  62. 	temp2 = B; \
  63. 	A = B - M1 - D1; \
  64. 	B = (C ^ g(B)) - f(B-D1); \
  65. 	C = (D ^ ROL(g(temp2),9)) - ROL(f(temp2-D1),5); \
  66. 	D = (E ^ ROL(g(temp2),21)) - ROL(f(temp2-D1),17); \
  67. 	E = F - M2 - D2; \
  68. 	temp2 = G; \
  69. 	G = (H ^ ROL(f(F),5)) - ROL(g(F-D2),9); \
  70. 	H = (temp ^ ROL(f(F),17)) - ROL(g(F-D2),21); \
  71. 	F = (temp2 ^ f(F)) - g(F-D2); \
  72.  
  73.  
  74. /* 32-bit pseudorandom word, even for RNGs that return only 16 bits */
  75. #define RANDOM_WORD (((WRD) rand() & 0xffff)<<16) | (rand() & 0xffff);
  76.  
  77. /** returns Hamming weight of x*/
  78. int hammingWeight(WRD x) {
  79. 	x -= (x >> 1) & 0x55555555;
  80. 	x = (x & 0x33333333) + ((x >> 2) & 0x33333333); 
  81. 	x = (x + (x >> 4)) & 0x0f0f0f0f;
  82. 	x += x >>  8;  
  83. 	x += x >> 16;  
  84. 	return x & 0x3f;
  85. }/*hammingWeight()*/
  86.  
  87.  
  88. /** This function returns 1 if the additive difference y1-y2
  89.  * can be transformed by adding a constant so that it "fits"
  90.  * into XOR difference dz ie. when a "microcollision" can happen */
  91. int micro_possible( WRD y1, WRD y2, WRD dz) {
  92. 	WRD tmp, delta_y;
  93. 	WRD sum;
  94. 	
  95. 	/* make  y1 > y2 : */
  96. 	if (y2 > y1) {
  97. 		tmp = y2; y2 = y1; y1 = tmp;
  98. 	}
  99. 	
  100. 	delta_y = y1 - y2;
  101. 	sum = delta_y;
  102. 	sum += dz;
  103. 	if (sum < delta_y) {
  104. 		/* overflow */
  105. 		if ((dz>>31)==0)
  106. 			/* no solution! */
  107. 			return 0;
  108. 	}
  109. 	dz <<= 1;
  110. 	return ( (dz|sum) == dz );
  111. }/*micro_possible()*/
  112.  
  113.  
  114. /** determine which bits of  "u"  must have 1's and which must have 0's */
  115. void get_ones_and_zeros(WRD y1, WRD y2, WRD z1, WRD z2, WRD *ones, WRD *zeros){
  116. 	WRD tmp, delta_y;
  117. 	WRD sum;
  118. 	
  119. 	/* make  y1 > y2 : */
  120. 	if (y2 > y1) {
  121. 		tmp = y2; y2 = y1; y1 = tmp;
  122. 		tmp = z2; z2 = z1; z1 = tmp;
  123. 	}
  124. 	
  125. 	tmp = z1 ^ z2;
  126. 	delta_y = y1 - y2;
  127. 	sum = delta_y;
  128. 	sum += tmp;
  129. 	
  130. 	tmp <<= 1;
  131. 	
  132. 	*ones = (tmp&sum) >> 1;
  133. 	*zeros = ((tmp&sum) ^ tmp) >> 1;
  134. }/*get_ones_and_zeros()*/
  135.  
  136. /** Compression function of FORK-256 that based on the value of
  137.  * chaining variables CV and message M updates the state of
  138.  * chaining variables CV */
  139. void FORK256_compression_function(WRD CV[8],WRD M[16]) {
  140. 	WRD A1,B1,C1,D1,E1,F1,G1,H1;
  141. 	WRD A2,B2,C2,D2,E2,F2,G2,H2;
  142. 	WRD A3,B3,C3,D3,E3,F3,G3,H3;
  143. 	WRD A4,B4,C4,D4,E4,F4,G4,H4;
  144. 	WRD temp;
  145. 	
  146. 	A1 = A2 = A3 = A4 = CV[0]; B1 = B2 = B3 = B4 = CV[1];
  147. 	C1 = C2 = C3 = C4 = CV[2]; D1 = D2 = D3 = D4 = CV[3];
  148. 	E1 = E2 = E3 = E4 = CV[4]; F1 = F2 = F3 = F4 = CV[5];
  149. 	G1 = G2 = G3 = G4 = CV[6]; H1 = H2 = H3 = H4 = CV[7];
  150. 	
  151. 	/* BRANCH1(CV,M) */
  152. 	step(A1,B1,C1,D1,E1,F1,G1,H1,M[0],M[1],delta[0],delta[1]);
  153. 	step(A1,B1,C1,D1,E1,F1,G1,H1,M[2],M[3],delta[2],delta[3]);
  154. 	step(A1,B1,C1,D1,E1,F1,G1,H1,M[4],M[5],delta[4],delta[5]);
  155. 	step(A1,B1,C1,D1,E1,F1,G1,H1,M[6],M[7],delta[6],delta[7]);
  156. 	step(A1,B1,C1,D1,E1,F1,G1,H1,M[8],M[9],delta[8],delta[9]);
  157. 	step(A1,B1,C1,D1,E1,F1,G1,H1,M[10],M[11],delta[10],delta[11]);
  158. 	step(A1,B1,C1,D1,E1,F1,G1,H1,M[12],M[13],delta[12],delta[13]);
  159. 	step(A1,B1,C1,D1,E1,F1,G1,H1,M[14],M[15],delta[14],delta[15]);
  160. 	/* BRANCH2(CV,M) */
  161. 	step(A2,B2,C2,D2,E2,F2,G2,H2,M[14],M[15],delta[15],delta[14]);
  162. 	step(A2,B2,C2,D2,E2,F2,G2,H2,M[11],M[9],delta[13],delta[12]);
  163. 	step(A2,B2,C2,D2,E2,F2,G2,H2,M[8],M[10],delta[11],delta[10]);
  164. 	step(A2,B2,C2,D2,E2,F2,G2,H2,M[3],M[4],delta[9],delta[8]);
  165. 	step(A2,B2,C2,D2,E2,F2,G2,H2,M[2],M[13],delta[7],delta[6]);
  166. 	step(A2,B2,C2,D2,E2,F2,G2,H2,M[0],M[5],delta[5],delta[4]);
  167. 	step(A2,B2,C2,D2,E2,F2,G2,H2,M[6],M[7],delta[3],delta[2]);
  168. 	step(A2,B2,C2,D2,E2,F2,G2,H2,M[12],M[1],delta[1],delta[0]);
  169. 	/* BRANCH3(CV,M) */
  170. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[7],M[6],delta[1],delta[0]);
  171. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[10],M[14],delta[3],delta[2]);
  172. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[13],M[2],delta[5],delta[4]);
  173. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[9],M[12],delta[7],delta[6]);
  174. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[11],M[4],delta[9],delta[8]);
  175. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[15],M[8],delta[11],delta[10]);
  176. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[5],M[0],delta[13],delta[12]);
  177. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[1],M[3],delta[15],delta[14]);
  178. 	/* BRANCH4(CV,M) */
  179. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[5],M[12],delta[14],delta[15]);
  180. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[1],M[8],delta[12],delta[13]);
  181. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[15],M[0],delta[10],delta[11]);
  182. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[13],M[11],delta[8],delta[9]);
  183. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[3],M[10],delta[6],delta[7]);
  184. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[9],M[2],delta[4],delta[5]);
  185. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[7],M[14],delta[2],delta[3]);
  186. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[4],M[6],delta[0],delta[1]);
  187. 	/* output : applying feed-forward */
  188. 	CV[0] = CV[0] + ((A1 + A2) ^ (A3 + A4));
  189. 	CV[1] = CV[1] + ((B1 + B2) ^ (B3 + B4));
  190. 	CV[2] = CV[2] + ((C1 + C2) ^ (C3 + C4));
  191. 	CV[3] = CV[3] + ((D1 + D2) ^ (D3 + D4));
  192. 	CV[4] = CV[4] + ((E1 + E2) ^ (E3 + E4));
  193. 	CV[5] = CV[5] + ((F1 + F2) ^ (F3 + F4));
  194. 	CV[6] = CV[6] + ((G1 + G2) ^ (G3 + G4));
  195. 	CV[7] = CV[7] + ((H1 + H2) ^ (H3 + H4));
  196. }/* FORK256_compression_function() */
  197.  
  198.  
  199. #ifdef USEHASHTABLE
  200. /************************ HASH TABLE STUFF ******************************/
  201. /************************ HASH TABLE STUFF ******************************/
  202. /************************ HASH TABLE STUFF ******************************/
  203.  
  204. /**
  205.  * Given modular difference  diff , determine the set of values for
  206.  * strand A in step 7 of branch 1 that can posibly cause a microcollision
  207.  * in strand D.
  208.  */
  209. void get_allowable_values( WRD diff, WRD allowable[], int * count ) {
  210. 	WRD x1, y1;
  211. 	WRD x2, y2;
  212. 	WRD dz;
  213. 	FILE * fp;
  214. 	char fileName[20] = {0};
  215. 	long fileSize;
  216.     
  217. 	/*test if we already have a file with precomputed values
  218. 	* its name should be allowable-hexdiff.dat
  219. 	* where hexdiff is 8 hex digits representing the difference diff*/
  220. 	sprintf(fileName,"allowable-%08x.dat",diff); 
  221. 	fp = fopen(fileName,"r");
  222. 	if ( fp ) {
  223. 		/*determine file size*/
  224. 		printf("Using precomputed file %s. ",fileName);
  225. 		fseek(fp,0,SEEK_END);
  226. 		fileSize = ftell(fp);
  227. 		printf("Size: %ld B (%ld values)\n",fileSize, fileSize/sizeof(WRD));
  228. 		fseek(fp,0,SEEK_SET);
  229. 		/*read the data into table */
  230. 		fread(allowable,fileSize / sizeof(WRD), sizeof(WRD),fp);
  231. 		fclose(fp);
  232. 		(*count) = fileSize/sizeof(WRD);
  233. 	} else {
  234. 		printf("Precomputing allowable values...  Please be patient!\n");
  235. 		printf("| 0 %%                           | 50 %%                           | 100 %%\n");
  236. 		x1 = 0;
  237. 		do {
  238. 			x2 = x1 + diff;
  239. 			y1 = f(x1);
  240. 			y2 = f(x2);
  241. 			dz = g(x1 + delta[12]) ^ g(x2 + delta[12]);
  242.  
  243. 			if ( micro_possible(ROL(y1,17),ROL(y2,17),ROL(dz,21)) ) {
  244. 				allowable[*count] = x1;
  245. 				++*count;
  246. 			}
  247. 			++x1;
  248. 			if ( (x1 & 0x3ffffff)==0 ) {
  249. 				printf("*");
  250. 				fflush(stdout);
  251. 			}
  252. 		} while (x1 != 0);
  253. 		printf("\nnumber of allowable values is %d\n\n",*count); 
  254. 		fflush(stdout);
  255. 		/*write precomputed allowable values to the file "allowable-hexdiff.dat"
  256. 		* where hexdiff is a hexadecimal representation of the difference*/
  257. 		sprintf(fileName,"allowable-%08x.dat",diff); 
  258. 		fp = fopen(fileName,"w");
  259. 		fwrite(allowable,(*count),sizeof(WRD),fp);
  260. 		fclose(fp);
  261. 	}
  262. }/* get_allowable_values() */
  263.  
  264.  
  265. /** Inserts value H into hash table pointed by hash_table */
  266. void insert_into_hash_table( WRD H, unsigned char hash_table[] ) {
  267. 	int i;
  268. 	
  269. 	i = H % HASH_SIZE;
  270. 	hash_table[i>>3] |= 1 << (i&7);
  271. }/* insert_into_hash_table() */
  272.  
  273.  
  274. /** returns non-zero if the value H is in the hash table hash_table,
  275.  * zero if not */
  276. int is_in_hash_table( WRD H, unsigned char hash_table[] ) {
  277. 	int i = H % HASH_SIZE;
  278. 	return (hash_table[i>>3] >> (i&7))&1;
  279. } /* is_in_hash_table() */
  280.  
  281.  
  282. /** We want to determine all allowable outputs to the G strand of
  283.  * step 5 of branch 1 (note output of G_5 = input to H_6), and store
  284.  * these in a hash table.
  285.  */
  286. void prepare_hash_table(WRD IV[8], WRD M[16], WRD M12prime, WRD allowable[],
  287. 							int count, unsigned char hash_table[]) {
  288. 	WRD A1,B1,C1,D1,E1,F1,G1,H1;
  289. 	WRD temp, temp2;
  290. 	WRD A1_1,B1_1,C1_1,D1_1,E1_1,F1_1,G1_1,H1_1;
  291. 	int i;
  292.  
  293. 	printf("\nBuilding hash table...");
  294. 	
  295. 	memset( hash_table, 0, HASH_MEM );
  296.  
  297. 	A1 = IV[0]; B1 = IV[1]; C1 = IV[2]; D1 = IV[3];
  298. 	E1 = IV[4]; F1 = IV[5]; G1 = IV[6]; H1 = IV[7];
  299. 	
  300. 	step(A1,B1,C1,D1,E1,F1,G1,H1,M[0],M[1],delta[0],delta[1]);
  301. 	step(A1,B1,C1,D1,E1,F1,G1,H1,M[2],M[3],delta[2],delta[3]);
  302. 	step(A1,B1,C1,D1,E1,F1,G1,H1,M[4],M[5],delta[4],delta[5]);
  303. 	step(A1,B1,C1,D1,E1,F1,G1,H1,M[6],M[7],delta[6],delta[7]);
  304. 	step(A1,B1,C1,D1,E1,F1,G1,H1,M[8],M[9],delta[8],delta[9]);
  305. 	step(A1,B1,C1,D1,E1,F1,G1,H1,M[10],M[11],delta[10],delta[11]);
  306. 	A1_1 = A1; B1_1 = B1; C1_1 = C1; D1_1 = D1;
  307. 	E1_1 = E1; F1_1 = F1; G1_1 = G1; H1_1 = H1;
  308. 	for (i=0; i < count; ++i) {
  309. 		A1 = allowable[i] - M[12];
  310. 		B1 = B1_1; C1 = C1_1; D1 = D1_1;
  311. 		E1 = E1_1; F1 = F1_1; G1 = G1_1; H1 = H1_1;
  312. 		back(A1,B1,C1,D1,E1,F1,G1,H1,M[10],M[11],delta[10],delta[11]);
  313. 		insert_into_hash_table( H1, hash_table );
  314. 	}
  315. 	
  316. 	printf(" done!\n\n");
  317. 	fflush(stdout);
  318. }/* prepare_hash_table() */
  319.  
  320.  
  321. void advance_M4( WRD IV[8], WRD M[16], WRD M12prime, WRD allowable[],
  322. 					int count, unsigned char hash_table[] ) {
  323. 	++M[4];
  324. 	prepare_hash_table( IV, M, M12prime, allowable, count, hash_table );
  325. }/* advance_M4() */
  326.  
  327.  
  328. /** This is a version of derive1 using hash tables. The procedure
  329.  * looks for such values of M[4] and M[9] that the difference
  330.  * in A6 of branch 1 does not propagate to E7 (single microcollision
  331.  * in the third line of the left Q-structure in step 7 of branch 1*/
  332. void derive1hash(WRD CV[8],WRD M[16], WRD M12p, WRD allowable[], 
  333. 					WRD a_count, unsigned char hash_table[] ) {
  334. 	WRD A,B,C,D,E,F,G,H;
  335. 	WRD A5,C5,D5,E5,H5;
  336. 	WRD A6,D6, E7_1=0, E7_2=1;
  337. 	WRD const1, const2;
  338. 	WRD temp;
  339. 	int i;
  340.  
  341. 	printf("\nsolving for branch 1...\n");
  342.  
  343. 	do {
  344. 		A = CV[0]; B = CV[1]; C = CV[2]; D = CV[3]; 
  345. 		E = CV[4]; F = CV[5]; G = CV[6]; H = CV[7]; 
  346. 		    
  347. 		step(A,B,C,D,E,F,G,H,M[0],M[1],delta[0],delta[1]); /* step 1 */
  348. 		step(A,B,C,D,E,F,G,H,M[2],M[3],delta[2],delta[3]); /* step 2 */
  349. 		step(A,B,C,D,E,F,G,H,M[4],M[5],delta[4],delta[5]); /* step 3 */
  350. 		step(A,B,C,D,E,F,G,H,M[6],M[7],delta[6],delta[7]); /* step 4 */
  351. 		
  352. 		/*precompute necessary registers of step 5 beforehand */
  353. 		C5 = (B + f(A+M[8])) ^ g(A+M[8]+delta[8]);
  354. 		D5 = (C + ROL(f(A+M[8]),5)) ^ ROL(g(A+M[8]+delta[8]),9);
  355. 		E5 = (D + ROL(f(A+M[8]),17)) ^ ROL(g(A+M[8]+delta[8]),21);
  356. 		const1 = ROL(g(E5+M[11]),21);
  357. 		const2 = ROL(f(E5+M[11]+delta[11]),17);
  358. 		
  359. 		do {
  360. 			H5 = (G + ROL(g(E+M[9]),9)) ^ ROL(f(E+M[9]+delta[9]),5);
  361. 			
  362. 			/*check hash table */
  363. 			i = H5 % HASH_SIZE;
  364.  
  365. 			if ((hash_table[i>>3] >> (i&7))&1) {
  366. 				/*H_5 is in a hash table: it corresponds to one of the
  367. 				 * allowable values -- so now we need to test it */
  368. 				A5 = (H + ROL(g(E+M[9]),21)) ^ ROL(f(E+M[9]+delta[9]),17);	
  369.  
  370. 				A6 = (H5 + const1) ^ const2;
  371. 				D6 = (C5 + ROL(f(A5+M[10]),5)) ^ ROL(g(A5+M[10]+delta[10]),9);
  372.  
  373. 				E7_1 = (D6 + ROL(f(A6+M[12]),17))^ROL(g(A6+M[12]+delta[12]),21);
  374. 				E7_2 = (D6 + ROL(f(A6+M12p ),17))^ROL(g(A6+ M12p+delta[12]),21);
  375. 				if (E7_1 == E7_2) {
  376. 					printf("M[4] = 0x%.8x;  M[9] = 0x%.8x;\n",M[4], M[9]);
  377. 					break;
  378. 					/*break out of the inner while loop (modifying M[9])*/
  379. 				}
  380. 			}
  381. 			++M[9];
  382. 		} while( M[9] != 0 );
  383. 	
  384. 		if ( E7_1 != E7_2 ) {
  385. 			advance_M4( CV, M, M12p, allowable, a_count, hash_table );
  386. 		}
  387. 	} while (E7_1 != E7_2);
  388. }/* derive1hash() */
  389.  
  390. /************ END OF HASH TABLE SPECIFIC CODE ****************************/
  391. /************ END OF HASH TABLE SPECIFIC CODE ****************************/
  392. /************ END OF HASH TABLE SPECIFIC CODE ****************************/
  393. #endif   /* end of code for variant using hash tables */
  394.  
  395.  
  396. /*** This function advances values of M[4] and M[9] until
  397.  * it finds a value that yields zero difference in register
  398.  * E after step 7 in branch 1 
  399.  * 
  400.  * Optimized version without hash tables */
  401. void derive1opt(WRD CV[8],WRD M[16], WRD M12p) {
  402. 	WRD A,B,C,D,E,F,G,H;
  403. 	WRD E7_1, E7_2;
  404. 	WRD A5, C5, D5, E5, H5;
  405. 	WRD A6, D6;
  406. 	WRD const1, const2;	
  407. 	WRD temp;
  408. 	
  409. 	printf("\nsolving for branch 1...\n");
  410. 	
  411. 	do {
  412. 		A = CV[0]; B = CV[1]; C = CV[2]; D = CV[3];
  413. 		E = CV[4]; F = CV[5]; G = CV[6]; H = CV[7];
  414. 		
  415. 		step(A,B,C,D,E,F,G,H,M[0],M[1],delta[0],delta[1]); /* step 1*/
  416. 		step(A,B,C,D,E,F,G,H,M[2],M[3],delta[2],delta[3]); /* step 2*/
  417. 		step(A,B,C,D,E,F,G,H,M[4],M[5],delta[4],delta[5]); /* step 3*/
  418. 		step(A,B,C,D,E,F,G,H,M[6],M[7],delta[6],delta[7]); /* step 4*/
  419. 			
  420. 		C5 = (B + f(A+M[8])) ^ g(A+M[8]+delta[8]);
  421. 		D5 = (C + ROL(f(A+M[8]),5)) ^ ROL(g(A+M[8]+delta[8]),9);
  422. 		E5 = (D + ROL(f(A+M[8]),17)) ^ ROL(g(A+M[8]+delta[8]),21);
  423. 		
  424. 		const1 = ROL(g(E5+M[11]),21);
  425. 		const2 = ROL(f(E5+M[11]+delta[11]),17);
  426. 		do {
  427. 			H5 = (G + ROL(g(E+M[9]), 9)) ^ ROL(f(E+M[9]+delta[9]),5);
  428. 			A5 = (H + ROL(g(E+M[9]),21)) ^ ROL(f(E+M[9]+delta[9]),17);	
  429.  
  430. 			A6 = (H5 + const1) ^ const2;
  431. 			D6 = (C5 + ROL(f(A5+M[10]),5)) ^ ROL(g(A5+M[10]+delta[10]),9);
  432.  
  433. 			E7_1 = (D6 + ROL(f(A6+M[12]),17)) ^ ROL(g(A6+M[12]+delta[12]),21);
  434. 			E7_2 = (D6 + ROL(f(A6+M12p ),17)) ^ ROL(g(A6+ M12p+delta[12]),21);
  435. 			
  436. 	
  437. 			if (E7_1 == E7_2) {
  438. 				printf("M[4] = 0x%.8x; M[9] = 0x%.8x;\n",M[4], M[9]);
  439. 				break;
  440. 			}/*if E7_1 == E7_2 */
  441. 			++M[9];
  442. 		} while( M[9] != 0 );
  443. 		
  444. 		if (E7_1 != E7_2) {
  445. 			++M[4];
  446. 		}
  447. 	} while (E7_1 != E7_2);
  448.  
  449. }/* derive1opt() */
  450.  
  451.  
  452.  
  453. /*** This function solves for branch 3 */
  454. int derive3(WRD CV[8],WRD M[16], WRD M12p ) {
  455. 	WRD A3,B3,C3,D3,E3,F3,G3,H3;
  456. 	WRD A,B,C,D,E,F,G,H;
  457. 	WRD holdF;
  458. 	WRD temp, temp2;
  459. 	WRD origE3;
  460. 	WRD y1, y2, z1, z2, dz;
  461. 	WRD ones, zeros;
  462. 	WRD mem1;
  463.  
  464. 	printf("\nsolving for branch 3...\n");
  465.  
  466. 	A3 = CV[0]; B3 = CV[1]; C3 = CV[2]; D3 = CV[3];
  467. 	E3 = CV[4]; F3 = CV[5]; G3 = CV[6]; H3 = CV[7];
  468. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[7],M[6],delta[1],delta[0]);
  469. 	mem1 = A3 + M[10];
  470. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[10],M[14],delta[3],delta[2]);
  471. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[13],M[2],delta[5],delta[4]);
  472. 	origE3 = E3;
  473. 	do {
  474. 		y1 = g(E3 + M[12]);
  475. 		y2 = g(E3 + M12p);
  476. 		z1 = f(E3 + M[12] + delta[6]);
  477. 		z2 = f(E3 + M12p + delta[6]);
  478. 		dz = z1 ^ z2;
  479. 		if (micro_possible( y1, y2, dz) && 
  480. 				micro_possible(ROL(y1,9),ROL(y2,9),ROL(dz,5)) &&
  481. 				micro_possible(ROL(y1,21),ROL(y2,21),ROL(dz,17)) ) {
  482. 			break;
  483. 		}
  484. 		++E3;
  485. 	} while (E3 != origE3);
  486.  
  487. 	if (!( micro_possible( y1, y2, dz) &&
  488. 			micro_possible(ROL(y1,9),ROL(y2,9),ROL(dz,5)) &&
  489. 			micro_possible(ROL(y1,21),ROL(y2,21),ROL(dz,17)) )) {
  490. 		printf("no solution for branch 3!\n");
  491. 		return 1;
  492. 	}
  493.  
  494. 	A = A3; B = B3; C = C3; D = D3; E = E3;
  495. 	get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros );
  496. 	if (y1 > y2)
  497. 		F = F3 = ones - y1;
  498. 	else
  499. 		F = F3 = ones - y2;
  500.  
  501. 	y1 = ROL(y1,9);
  502. 	y2 = ROL(y2,9);
  503. 	z1 = ROL(z1,5);
  504. 	z2 = ROL(z2,5);
  505. 	get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros );
  506. 	if (y1 > y2)
  507. 		G = G3 = ones - y1;
  508. 	else
  509. 		G = G3 = ones - y2;
  510.  
  511. 	y1 = ROL(y1,12);
  512. 	y2 = ROL(y2,12);
  513. 	z1 = ROL(z1,12);
  514. 	z2 = ROL(z2,12);
  515. 	get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros );
  516. 	if (y1 > y2)
  517. 		H = H3 = ones - y1;
  518. 	else
  519. 		H = H3 = ones - y2;
  520.  
  521. 	/* These are the values we want at the beginning of step 3: */
  522. 	A3 = A; B3 = B; C3 = C; D3 = D; E3 = E; F3 = F; G3 = G; H3 = H;
  523. 	back(A3,B3,C3,D3,E3,F3,G3,H3,M[13],M[2],delta[5],delta[4]);
  524. 	back(A3,B3,C3,D3,E3,F3,G3,H3,M[10],M[14],delta[3],delta[2]);
  525. 	M[6] = F3 - delta[0] - CV[4];
  526. 	printf("M[6] = 0x%.8x;\n",M[6]);
  527. 	A3 = CV[0]; B3 = CV[1]; C3 = CV[2]; D3 = CV[3];
  528. 	E3 = CV[4]; F3 = CV[5]; G3 = CV[6]; H3 = CV[7];
  529. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[7],M[6],delta[1],delta[0]);
  530. 	M[10] = mem1 - A3;
  531. 	printf("M[10] = 0x%.8x;\n",M[10]);
  532.  
  533. 	/* These are the values we want at the beginning of step 3: */
  534. 	A3 = A; B3 = B; C3 = C; D3 = D; E3 = E; F3 = F; G3 = G; H3 = H;
  535. 	back(A3,B3,C3,D3,E3,F3,G3,H3,M[13],M[2],delta[5],delta[4]);
  536. 	holdF = F3;
  537. 	A3 = CV[0]; B3 = CV[1]; C3 = CV[2]; D3 = CV[3];
  538. 	E3 = CV[4]; F3 = CV[5]; G3 = CV[6]; H3 = CV[7];
  539. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[7],M[6],delta[1],delta[0]);
  540. 	M[14] = holdF - E3 - delta[2];
  541. 	printf("M[14] = 0x%.8x;\n",M[14]);
  542.  
  543. 	A3 = CV[0]; B3 = CV[1]; C3 = CV[2]; D3 = CV[3];
  544. 	E3 = CV[4]; F3 = CV[5]; G3 = CV[6]; H3 = CV[7];
  545. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[7],M[6],delta[1],delta[0]);
  546. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[10],M[14],delta[3],delta[2]);
  547. 	M[2] = F - E3 - delta[4];
  548. 	printf("M[2] = 0x%.8x;\n",M[2]);
  549.  
  550. 	/* These are the values we want at the beginning of step 3: */
  551. 	A3 = CV[0]; B3 = CV[1]; C3 = CV[2]; D3 = CV[3];
  552. 	E3 = CV[4]; F3 = CV[5]; G3 = CV[6]; H3 = CV[7];
  553. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[7],M[6],delta[1],delta[0]);
  554. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[10],M[14],delta[3],delta[2]);
  555. 	step(A3,B3,C3,D3,E3,F3,G3,H3,M[13],M[2],delta[5],delta[4]);
  556. 	E3 = E;
  557. 	back(A3,B3,C3,D3,E3,F3,G3,H3,M[13],M[2],delta[5],delta[4]);
  558. 	back(A3,B3,C3,D3,E3,F3,G3,H3,M[10],M[14],delta[3],delta[2]);
  559. 	back(A3,B3,C3,D3,E3,F3,G3,H3,M[7],M[6],delta[1],delta[0]);
  560. 	CV[1] = B3;
  561. 	printf("IV[1] = 0x%.8x;\n",CV[1]);
  562. 	
  563. 	return 0;
  564. }/* derive3() */
  565.  
  566.  
  567. /*** This function solves for branch4 */
  568. int derive4(WRD CV[8], WRD M[16], WRD M12p, WRD * origE4step3plusM11) {
  569. 	WRD A4,B4,C4,D4,E4,F4,G4,H4;
  570. 	WRD A4p,B4p,C4p,D4p,E4p,F4p,G4p,H4p;
  571. 	WRD temp, temp2;
  572. 	WRD M3 = 0;
  573. 	WRD ones, zeros;
  574. 	WRD B, C, D;
  575. 	WRD A, E, F, G, H;
  576. 	WRD z1, z2, dz, y1, y2;
  577. 	WRD holdB, mem1, mem2;
  578. 	
  579. 	printf("\nsolving for branch 4...\n");
  580. 	
  581. 	A4 = A4p = CV[0]; B4 = B4p = CV[1]; C4 = C4p = CV[2]; D4 = D4p = CV[3];
  582. 	E4 = E4p = CV[4]; F4 = F4p = CV[5]; G4 = G4p = CV[6]; H4 = H4p = CV[7];
  583. 	
  584. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[5],M[12],delta[14],delta[15]);
  585. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[1],M[8],delta[12],delta[13]);
  586. 	mem1 = E4 + M[0];
  587. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[15],M[0],delta[10],delta[11]);
  588. 	mem2 = E4 + M[11];
  589. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[13],M[11],delta[8],delta[9]);
  590. 	
  591. 	step(A4p,B4p,C4p,D4p,E4p,F4p,G4p,H4p,M[5],M12p,delta[14],delta[15]);
  592. 	step(A4p,B4p,C4p,D4p,E4p,F4p,G4p,H4p,M[1],M[8],delta[12],delta[13]);
  593. 	step(A4p,B4p,C4p,D4p,E4p,F4p,G4p,H4p,M[15],M[0],delta[10],delta[11]);
  594. 	step(A4p,B4p,C4p,D4p,E4p,F4p,G4p,H4p,M[13],M[11],delta[8],delta[9]);
  595.  
  596. 	do {
  597. 		y1 = f( A4 + M3 );
  598. 		y2 = f( A4p + M3 );
  599. 		z1 = g( A4 + M3 + delta[6] );
  600. 		z2 = g( A4p + M3 + delta[6] );
  601. 		dz = z1 ^ z2;
  602. 		if (micro_possible( y1, y2, dz) && 
  603. 			micro_possible(ROL(y1,5),ROL(y2,5),ROL(dz,9)) &&
  604. 			micro_possible(ROL(y1,17),ROL(y2,17),ROL(dz,21)) )
  605. 			break;
  606. 		++M3;
  607. 	} while (M3 != 0);
  608.  
  609. 	if (!(micro_possible( y1, y2, dz) &&
  610. 			micro_possible(ROL(y1,5),ROL(y2,5),ROL(dz,9)) &&
  611. 			micro_possible(ROL(y1,17),ROL(y2,17),ROL(dz,21)) )) {
  612. 		printf("no solution for branch 4!\n");
  613. 		return 1;
  614. 	}
  615.  
  616. 	/*  now we want to set up B, C, and D to be what we want by choosing
  617. 	* the right values for M[8], M[0], and M[11]. */
  618. 	M[3] = M3;
  619. 	printf("M[3] = 0x%.8x\n",M[3]);
  620. 	get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros );
  621. 	if (y1 > y2)
  622. 		B = B4 = B4p = ones - y1;
  623. 	else
  624. 		B = B4 = B4p = ones - y2;
  625. 	
  626. 	y1 = ROL(y1,5);
  627. 	y2 = ROL(y2,5);
  628. 	z1 = ROL(z1,9);
  629. 	z2 = ROL(z2,9);
  630. 	get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros );
  631. 	if (y1 > y2)
  632. 		C = C4 = C4p = ones - y1;
  633. 	else
  634. 		C = C4 = C4p = ones - y2;
  635. 	
  636. 	y1 = ROL(y1,12);
  637. 	y2 = ROL(y2,12);
  638. 	z1 = ROL(z1,12);
  639. 	z2 = ROL(z2,12);
  640. 	get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros );
  641. 	if (y1 > y2)
  642. 		D = D4 = D4p = ones - y1;
  643. 	else
  644. 		D = D4 = D4p = ones - y2;
  645. 	
  646. 	A = A4; E = E4; F = F4; G = G4; H = H4;
  647. 	
  648. 	back(A4,B4,C4,D4,E4,F4,G4,H4,M[13],M[11],delta[8],delta[9]);
  649. 	back(A4,B4,C4,D4,E4,F4,G4,H4,M[15],M[0],delta[10],delta[11]);
  650. 	holdB = B4;
  651. 	A4 = CV[0]; B4 = CV[1]; C4 = CV[2]; D4 = CV[3];
  652. 	E4 = CV[4]; F4 = CV[5]; G4 = CV[6]; H4 = CV[7];
  653. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[5],M[12],delta[14],delta[15]);
  654. 	/* compute the new M[1]: */
  655. 	M[1]=holdB-delta[12]-A4;
  656. 	printf("M[1] = 0x%.8x;\n",M[1]);
  657. 	/* compute the new M[0]: */
  658. 	y2 = ROL( f(A4 + M[1]), 17 );
  659. 	z2 = ROL( g(A4 + M[1] + delta[12]), 21 );
  660. 	M[0] = mem1 - ((D4 + y2) ^ z2);
  661. 	printf("M[0] = 0x%.8x;\n",M[0]);
  662.  
  663.  
  664. 	/* now we go back to the 5th step again and set our variables
  665. 	* accordingly.  then we will step back to determine the new
  666. 	* m[15], m[11]. 	*/
  667. 	A4 = A; B4 = B; C4 = C; D4 = D; E4 = E; F4 = F; G4 = G; H4 = H;
  668. 	back(A4,B4,C4,D4,E4,F4,G4,H4,M[13],M[11],delta[8],delta[9]);
  669. 	holdB = B4;
  670. 	A4 = CV[0]; B4 = CV[1]; C4 = CV[2]; D4 = CV[3];
  671. 	E4 = CV[4]; F4 = CV[5]; G4 = CV[6]; H4 = CV[7];
  672. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[5],M[12],delta[14],delta[15]);
  673. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[1],M[8],delta[12],delta[13]);
  674. 	/* compute the new M[15]: */
  675. 	M[15]=holdB-delta[10]-A4;
  676. 	printf("M[15] = 0x%.8x;\n",M[15]);
  677. 	/* compute the new M[11]: */
  678. 	y2 = ROL( f(A4 + M[15]), 17 );
  679. 	z2 = ROL( g(A4 + M[15] + delta[10]), 21 );
  680. 	M[11] = mem2 - ((D4 + y2) ^ z2);
  681. 	printf("M[11] = 0x%.8x;\n",M[11]);
  682.  
  683. 	/* Finally we determine new M[13] */
  684. 	holdB = B;
  685. 	A4 = CV[0]; B4 = CV[1]; C4 = CV[2]; D4 = CV[3];
  686. 	E4 = CV[4]; F4 = CV[5]; G4 = CV[6]; H4 = CV[7];
  687. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[5],M[12],delta[14],delta[15]);
  688. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[1],M[8],delta[12],delta[13]);
  689. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[15],M[0],delta[10],delta[11]);
  690. 	/* compute the new M[13]: */
  691. 	M[13]=holdB-delta[8]-A4;
  692. 	printf("M[13] = 0x%.8x;\n",M[13]);
  693.  
  694. 	A4 = CV[0]; B4 = CV[1]; C4 = CV[2]; D4 = CV[3];
  695. 	E4 = CV[4]; F4 = CV[5]; G4 = CV[6]; H4 = CV[7];
  696. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[5],M[12],delta[14],delta[15]);
  697. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[1],M[8],delta[12],delta[13]);
  698. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[15],M[0],delta[10],delta[11]);
  699. 	*origE4step3plusM11 = E4 + M[11];
  700.  
  701. 	return 0;
  702. }/* derive4() */
  703.  
  704.  
  705. /** Corrects the value of M11 after solving for branch 3 */
  706. void fixM11( WRD CV[8],WRD M[16], WRD origE4step3plusM11 ) {
  707. 	WRD A4,B4,C4,D4,E4,F4,G4,H4;
  708. 	WRD temp;
  709. 	
  710. 	printf("\nfixing M[11]...\n");
  711. 	
  712. 	A4 = CV[0]; B4 = CV[1]; C4 = CV[2]; D4 = CV[3];
  713. 	E4 = CV[4]; F4 = CV[5]; G4 = CV[6]; H4 = CV[7];
  714. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[5],M[12],delta[14],delta[15]);
  715. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[1],M[8],delta[12],delta[13]);
  716. 	step(A4,B4,C4,D4,E4,F4,G4,H4,M[15],M[0],delta[10],delta[11]);
  717. 	M[11] = origE4step3plusM11 - E4;
  718. 	printf("M[11] = 0x%.8x;\n",M[11]);
  719. }/* fixM11() */
  720.  
  721. /** Picks randomly M[12] and necessary constants in IV[5,6,7] */
  722. void choose_M12_and_IV( WRD IV[8], WRD diff, WRD * M12, WRD * M12prime ) {
  723. 	WRD E;
  724. 	WRD x1, x2;
  725. 	WRD y1, y2;
  726. 	WRD z1, z2, dz;
  727. 	WRD F, G, H, ones, zeros;
  728. 	WRD startWith;
  729. 	
  730. 	printf("\nsolving for IV[5,6,7] and M[12]...\n");
  731. 	fflush(stdout);
  732. 	
  733. 	E = IV[4];
  734. 	/* *M12 = 0x1811f2d9; */
  735. 	/*choosing a random value from the set of candidates for M12 */
  736. 	startWith = RANDOM_WORD; 
  737. 	*M12 = startWith;
  738. 	do {
  739. 		x1 = E + *M12;
  740. 		x2 = E + *M12 + diff;
  741. 		y1 = g(x1);
  742. 		y2 = g(x2);
  743. 		z1 = f((x1+delta[15]));
  744. 		z2 = f((x2+delta[15]));
  745. 		dz = z1 ^ z2;
  746. 		if (micro_possible( y1, y2, dz) &&
  747. 				micro_possible(ROL(y1,9),ROL(y2,9),ROL(dz,5)) &
  748. 				micro_possible(ROL(y1,21),ROL(y2,21),ROL(dz,17)) ) {
  749. 			get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros );
  750. 			if (y1 > y2)
  751. 				F = ones - y1;
  752. 			else
  753. 				F =  ones - y2;
  754. 	
  755. 			y1 = ROL(y1,9);
  756. 			y2 = ROL(y2,9);
  757. 			z1 = ROL(z1,5);
  758. 			z2 = ROL(z2,5);
  759. 			get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros );
  760. 			if (y1 > y2)
  761. 				G =  ones - y1;
  762. 			else
  763. 				G =  ones - y2;
  764. 	
  765. 			y1 = ROL(y1,12);
  766. 			y2 = ROL(y2,12);
  767. 			z1 = ROL(z1,12);
  768. 			z2 = ROL(z2,12);
  769. 			get_ones_and_zeros( y1, y2, z1, z2, &ones, &zeros );
  770. 			if (y1 > y2)
  771. 				H =  ones - y1;
  772. 			else
  773. 				H =  ones - y2;
  774. 	
  775. 			*M12prime = *M12 + diff;
  776. 			printf("M[12] = 0x%.8x;\n M12p = 0x%.8x;\n",*M12,*M12prime);
  777. 			printf("IV[5] = 0x%.8x\n",F);
  778. 			IV[5] = F;
  779. 			printf("IV[6] = 0x%.8x\n",G);
  780. 			IV[6] = G;
  781. 			printf("IV[7] = 0x%.8x\n",H);
  782. 			IV[7] = H;
  783. 			return;
  784. 		}
  785. 		(*M12)++;
  786. 	} while ( (*M12) != startWith );
  787. 	/* If we are here, no microcollision could be found for this additive
  788. 		* difference, something is wrong! */
  789. 	printf("Illegal input difference!\n");
  790. 	exit(1);
  791. }/* choose_M12_and_IV() */
  792.  
  793.  
  794. int main(int argc, char * argv[]) {
  795. 	int i,hmwt;
  796. 	WRD IV[8] = {
  797. 		0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
  798. 		0x510e527f, 0x70852362, 0x923cf4a3, 0x4f4a3124
  799. 	};
  800. 	WRD M[16], CV1[8], CV2[8], M12prime, M12;
  801. 	WRD origE4step3plusM11;
  802. 	WRD out_diff[8];
  803. 	int seed = 0;
  804. 	FILE *fp;
  805. 	WRD diff = 0x22f80000;
  806. 	/*WRD diff = 0xdd080000;*/	
  807. 	/*WRD diff = 0x5a100000;*/
  808. 	int num_sols = 0;
  809. 	double count = 0.0;
  810. 	WRD startM4 = 0xfeefffff; /* to store the initial value of M4 we start with */
  811. 	const int MAXWT = 38; /* maximum weight of output diffs we want to output */
  812. 	double globalCPUtimederive1  = 0; /*total CPU time spent in derive1() */
  813. 	clock_t clockStart, clockEnd;
  814. 	char filename[1024];
  815. 	
  816. #ifdef USEHASHTABLE
  817. 	WRD * allowable = malloc( (1<<22)*sizeof(WRD) );
  818. 	int a_count = 0;
  819. 	unsigned char * hash_table = malloc( (HASH_SIZE + 7)/8 );
  820. 	HASH_MEM = (HASH_SIZE + 7)/8;
  821. #endif
  822.     
  823.  
  824. 	/* pseudorandom numbers are used in
  825. 	 * - choose_M12_and_IV() to pick a random value of M12 from the 
  826. 	 *       set of potentially producing microcollision
  827. 	 * - before derive1() to initialize some message words */
  828.  
  829. 	/* if possible, read the seed from first command-line parameter */
  830. 	if ((argc > 1) && (sscanf(argv[1],"%d",&seed)>0) ) {
  831. 		printf("Using seed : %d \n",seed);
  832. 	} else {
  833. 		/*if not, read the seed from the input*/
  834. 		printf("\n\n\nEnter seed: ");
  835. 		fflush(stdout);
  836. 		scanf("%d",&seed);
  837. 	}
  838. 	srand(seed);
  839.  
  840. 	sprintf(filename,"solutions%d.txt",seed);
  841.  
  842. #ifdef USEHASHTABLE
  843. 	get_allowable_values( diff, allowable, &a_count );
  844. #endif
  845. 	choose_M12_and_IV( IV, diff, &M12, &M12prime );
  846. 	/* set up first message */
  847. 	for (i=0; i < 16; ++i) {
  848. 		M[i] = 0;
  849. 	}
  850. 	M[12] = M12;
  851. 	M[4] = startM4; /* start is possible from arbitrary value of M[4] */
  852.  
  853. 	do {
  854. 		M[1]  = RANDOM_WORD;
  855. 		M[15] = RANDOM_WORD;
  856. 		M[13] = RANDOM_WORD;
  857. 		
  858. 		M[8]  = RANDOM_WORD;
  859. 		M[0]  = RANDOM_WORD;
  860. 		M[11] = RANDOM_WORD;
  861. 		/* pick random words until it is possible to solve for
  862. 		 * branches 4 and 3 */
  863. 	} while(derive4(IV, M, M12prime, &origE4step3plusM11 ) ||
  864. 			derive3(IV, M, M12prime ) );
  865.  
  866. 	fixM11( IV, M, origE4step3plusM11 );
  867.  
  868. #ifdef USEHASHTABLE
  869. 	prepare_hash_table( IV, M, M12prime, allowable, a_count, hash_table );
  870. #endif
  871.  
  872. 	do { /* main loop that goes through M[4] and M[9] and find near-colls */
  873. 		clockStart = clock();
  874. 		/* find near-collision */
  875. #ifdef USEHASHTABLE
  876. 		derive1hash( IV, M, M12prime, allowable, a_count, hash_table );
  877. #else
  878. 		derive1opt( IV, M, M12prime );
  879. #endif
  880. 		clockEnd = clock();
  881. 		globalCPUtimederive1 += ((double) (clockEnd-clockStart))/CLOCKS_PER_SEC;
  882. 		
  883. 		/* compute the first hash */
  884. 		for (i=0; i < 8; ++i){
  885. 			CV1[i] = IV[i];
  886. 		}
  887. 		FORK256_compression_function( CV1, M );
  888. 		
  889. 		/* compute the second hash */
  890. 		M[12] = M12prime;
  891. 		for (i=0; i < 8; ++i){
  892. 			CV2[i] = IV[i];
  893. 		}
  894. 		FORK256_compression_function( CV2, M );
  895. 	
  896. 		/* compute the difference of hashes and its Hamming weight */
  897. 		hmwt = 0;
  898. 		for (i=0; i < 8; ++i) {
  899. 			out_diff[i] = CV1[i] ^ CV2[i];
  900. 			hmwt += hammingWeight(out_diff[i]);
  901. 		}
  902. 		
  903. 		/* print to the solutions file hashes with weight less than MAXWT only */
  904. 		if ( hmwt < MAXWT ) {
  905. 			fp = fopen(filename,"a");	
  906. 			/* print IV */
  907. 			fprintf(fp, "  IV: ");
  908. 			for (i=0; i < 8; ++i) {
  909. 				fprintf(fp,"%.8x ",IV[i]);
  910. 			}
  911. 			fprintf(fp,"\n");
  912. 			/* print the first message */
  913. 			fprintf(fp, "   M: ");
  914. 			for (i=0; i < 16; ++i) {
  915. 				fprintf(fp,"%.8x ",M[i]);
  916. 			}
  917. 			fprintf(fp,"\n");
  918. 			/* print M[12] of the second message */
  919. 			fprintf(fp, "M12': %.8x\n",M12prime);
  920. 			
  921. 			/* print the first hash */
  922. 			fprintf(fp, "  H1: ");
  923. 			for (i=0; i < 8; ++i) {
  924. 				fprintf(fp,"%.8x ",CV1[i]);
  925. 			}
  926. 			fprintf(fp,"\n");
  927. 			/* print the second hash */
  928. 			fprintf(fp, "  H2: ");
  929. 			for (i=0; i < 8; ++i) {
  930. 				fprintf(fp,"%.8x ",CV2[i]);
  931. 			}
  932. 			fprintf(fp,"\n");
  933. 	
  934. 			/* print the difference */
  935. 			fprintf(fp,"diff: ");
  936. 			for (i=0; i < 8; ++i) {
  937. 				fprintf(fp,"%.8x ",out_diff[i]);
  938. 			}
  939. 			fprintf(fp,"\n");
  940. 			fprintf(fp,"\nHamming weight of difference is %d\n\n",hmwt);
  941. 			fclose(fp);
  942. 		}/*end of printing to solutions file */
  943. 		++num_sols;
  944. 		count = 4294967296.0 * (M[4]-startM4) + (double) M[9];
  945.  
  946. 		printf("\nSOLUTION NO %d FOUND!!! time %.2f \n\n",num_sols, ((double) (clockEnd-clockStart))/CLOCKS_PER_SEC);
  947. 		printf("Hamming weight of difference is %d\n\n",hmwt);
  948. 		printf("observed probability of passing branch1 is about 2^%.4f\n",
  949. 			(log(num_sols/count)/log(2)) );
  950. 		fflush(stdout);
  951. 		
  952. 		if ((++M[9]) == 0)
  953. 			++M[4];
  954. 		M[12] = M12;
  955.  
  956. 	} while ( num_sols < 50 ); /* change "while ( num_sols<50 )" to "while ( 1 )" for an infinite loop */
  957. 	
  958. #ifdef USEHASHTABLE
  959. 	free( allowable );
  960. 	free( hash_table );
  961. #endif
  962. 	printf ("\nTotal time spent in derive1() : %.2f s\n",globalCPUtimederive1);
  963. 	printf ("Average time for a single derive1(): %.3f s\n",globalCPUtimederive1/num_sols);
  964. 	
  965. 	return 0;
  966. }/*main()*/
  967.  
  968.