?? md4coll.c
字號:
/* MD4 Collision Generator by Patrick Stach <pstach@stachliu.com> * Implementation of paper by Xiaoyun Wang, et. al. * * A few optimizations to make the solving method a bit more deterministic * * Usage: * ./md4coll or ./md4coll IV0 IV1 IV2 IV3 * * Requires being built 32 bit (unsigned int as 32 bit) * * Any derivative works or references must cite the authors. */#include <stdio.h>#include <stdlib.h>#include <unistd.h>#include <time.h>#define IV0 0x67452301#define IV1 0xefcdab89#define IV2 0x98badcfe#define IV3 0x10325476#define RL(x, y) (((x) << (y)) | ((x) >> (32 - (y))))#define RR(x, y) (((x) >> (y)) | ((x) << (32 - (y))))#define F(b, c, d) (((c ^ d) & b) ^ d)#define G(b, c, d) ((b & c) | (b & d) | (c & d))#define H(b, c, d) (b ^ c ^ d)#define K1 0x5A827999#define K2 0x6ED9EBA1unsigned int IV[4] = { IV0, IV1, IV2, IV3 };unsigned int Q0[49], Q1[49];unsigned int X0[16], X1[16];void md4gen(void){ size_t i;md4_again: for(;;) { /* D1 */ Q0[ 2] = random() & ~0x00000040; Q1[ 2] = Q0[ 2] - 0xffffffc0; /* C1 */ Q0[ 3] = (random() | 0x000000c0) & ~(0x00000800 | 0x02000000); Q0[ 3] |= (Q0[ 2] & 0x02000000); Q1[ 3] = Q0[ 3] - 0xfffffc80; /* B1 */ Q0[ 4] = (random() | 0x00000040) & ~0x02000480; Q1[ 4] = Q0[ 4] - 0xfe000000; /* A2 */ Q0[ 5] = (random() | 0x00000480) & ~(0x02000000 | 0x00002000); Q0[ 5] |= (Q0[ 4] & 0x00002000); Q1[ 5] = Q0[ 5]; /* D2 */ Q0[ 6] = (random() | 0x02000000) & ~(0x00002000 | 0x003c0000); Q0[ 6] |= (Q0[ 5] & 0x003c0000); Q1[ 6] = Q0[ 6] - 0xffffe000; X0[ 5] = RR(Q0[ 6], 7) - F(Q0[ 5], Q0[ 4], Q0[ 3]) - Q0[ 2]; X1[ 5] = RR(Q1[ 6], 7) - F(Q1[ 5], Q1[ 4], Q1[ 3]) - Q1[ 2]; if(X0[ 5] != X1[ 5]) continue; /* C2 */ Q0[ 7] = (random() | 0x00100000) & ~(0x002c2000 | 0x00005000); Q0[ 7] |= (Q0[ 6] & 0x00005000); Q1[ 7] = Q0[ 7] - 0xffe40000; X0[ 6] = RR(Q0[ 7], 11) - F(Q0[ 6], Q0[ 5], Q0[ 4]) - Q0[ 3]; X1[ 6] = RR(Q1[ 7], 11) - F(Q1[ 6], Q1[ 5], Q1[ 4]) - Q1[ 3]; if(X0[ 6] != X1[ 6]) continue; /* B2 */ Q0[ 8] = (random() | 0x00003000) & ~(0x003c4000 | 0x00010000); Q0[ 8] |= (Q0[ 7] & 0x00010000); Q1[ 8] = Q0[ 8] - 0xfffff000; X0[ 7] = RR(Q0[ 8], 19) - F(Q0[ 7], Q0[ 6], Q0[ 5]) - Q0[ 4]; X1[ 7] = RR(Q1[ 8], 19) - F(Q1[ 7], Q1[ 6], Q1[ 5]) - Q1[ 4]; if(X0[ 7] != X1[ 7]) continue; /* A3 */ Q0[ 9] = (random() | 0x00207000) & ~(0x001d0000 | 0x02400000); Q0[ 9] |= (Q0[ 8] & 0x02400000); Q1[ 9] = Q0[ 9] - 0xffff0000; X0[ 8] = RR(Q0[ 9], 3) - F(Q0[ 8], Q0[ 7], Q0[ 6]) - Q0[ 5]; X1[ 8] = RR(Q1[ 9], 3) - F(Q1[ 8], Q1[ 7], Q1[ 6]) - Q1[ 5]; if(X0[ 8] != X1[ 8]) continue; /* D3 */ Q0[10] = (random() | 0x02307000) & ~(0x00490000 | 0x20000000); Q0[10] |= (Q0[ 9] & 0x20000000); Q1[10] = Q0[10] - 0x01e80000; X0[ 9] = RR(Q0[10], 7) - F(Q0[ 9], Q0[ 8], Q0[ 7]) - Q0[ 6]; X1[ 9] = RR(Q1[10], 7) - F(Q1[ 9], Q1[ 8], Q1[ 7]) - Q1[ 6]; if(X0[ 9] != X1[ 9]) continue; /* C3 */ Q0[11] = (random() | 0x20010000) & ~(0x02780000 | 0x80000000); Q0[11] |= (Q0[10] & 0x80000000); Q1[11] = Q0[11] - 0x20000000; X0[10] = RR(Q0[11], 11) - F(Q0[10], Q0[ 9], Q0[ 8]) - Q0[ 7]; X1[10] = RR(Q1[11], 11) - F(Q1[10], Q1[ 9], Q1[ 8]) - Q1[ 7]; if(X0[10] != X1[10]) continue; /* B3 */ Q0[12] = (random() | 0x02300000) & ~(0xa0080000 | 0x00400000); Q0[12] |= (Q0[11] & 0x00400000); Q1[12] = Q0[12] - 0x80000000; X0[11] = RR(Q0[12], 19) - F(Q0[11], Q0[10], Q0[ 9]) - Q0[ 8]; X1[11] = RR(Q1[12], 19) - F(Q1[11], Q1[10], Q1[ 9]) - Q1[ 8]; if(X0[11] != X1[11]) continue; /* A4 */ Q0[13] = (random() | 0x20000000) & ~(0x82400000 | 0x14000000); Q0[13] |= (Q0[12] & 0x14000000); Q1[13] = Q0[13] - 0xfdc00000; X0[12] = RR(Q0[13], 3) - F(Q0[12], Q0[11], Q0[10]) - Q0[ 9]; X1[12] = RR(Q1[13], 3) - F(Q1[12], Q1[11], Q1[10]) - Q1[ 9]; if((X0[12] ^ X1[12]) != 0x00010000) continue; /* D4 */ Q0[14] = (random() | 0x94000000) & ~0x22400000; Q1[14] = Q0[14] - 0xf4000000; X0[13] = RR(Q0[14], 7) - F(Q0[13], Q0[12], Q0[11]) - Q0[10]; X1[13] = RR(Q1[14], 7) - F(Q1[13], Q1[12], Q1[11]) - Q1[10]; if(X0[13] != X1[13]) continue; /* C4 */ Q0[15] = (random() | 0x02400000) & ~(0x34000000 | 0x00040000); Q0[15] |= (Q0[14] & 0x00040000); Q1[15] = Q0[15]; X0[14] = RR(Q0[15], 11) - F(Q0[14], Q0[13], Q0[12]) - Q0[11]; X1[14] = RR(Q1[15], 11) - F(Q1[14], Q1[13], Q1[12]) - Q1[11]; if(X0[14] != X1[14]) continue; /* B4 */ Q0[16] = (random() | 0x14000000) & ~0x20040000; Q1[16] = Q0[16] - 0xfffc0000; X0[15] = RR(Q0[16], 19) - F(Q0[15], Q0[14], Q0[13]) - Q0[12]; X1[15] = RR(Q1[16], 19) - F(Q1[15], Q1[14], Q1[13]) - Q1[12]; if(X0[15] != X1[15]) continue; break; }#define LOOP_11 100 for(i = 0; i < LOOP_11; i++) { Q0[ 1] = random() & ~(0x00000040 | 0x00000480); Q0[ 1] |= (IV[1] & 0x00000040) | (Q0[ 2] & 0x00000480); Q1[ 1] = Q0[ 1]; X0[ 0] = RR(Q0[ 1], 3) - F(IV[1], IV[2], IV[3]) - IV[0]; X1[ 0] = X0[ 0]; X0[ 1] = RR(Q0[ 2], 7) - F(Q0[ 1], IV[1], IV[2]) - IV[3]; X1[ 1] = RR(Q1[ 2], 7) - F(Q1[ 1], IV[1], IV[2]) - IV[3]; if((X0[ 1] ^ X1[ 1]) != 0x80000000) continue; X0[ 2] = RR(Q0[ 3], 11) - F(Q0[ 2], Q0[ 1], IV[1]) - IV[2]; X1[ 2] = RR(Q1[ 3], 11) - F(Q1[ 2], Q1[ 1], IV[1]) - IV[2]; if((X0[ 2] ^ X1[ 2]) != 0x90000000) continue; X0[ 3] = RR(Q0[ 4], 19) - F(Q0[ 3], Q0[ 2], Q0[ 1]) - IV[1]; X1[ 3] = RR(Q1[ 4], 19) - F(Q1[ 3], Q1[ 2], Q1[ 1]) - IV[1]; if(X0[ 3] != X1[ 3]) continue; X0[ 4] = RR(Q0[ 5], 3) - F(Q0[ 4], Q0[ 3], Q0[ 2]) - Q0[ 1]; X1[ 4] = RR(Q1[ 5], 3) - F(Q1[ 4], Q1[ 3], Q1[ 2]) - Q1[ 1]; if(X0[ 4] != X1[ 4]) continue; Q0[17] = RL(G(Q0[16], Q0[15], Q0[14]) + Q0[13] + X0[ 0] + K1, 3); Q1[17] = RL(G(Q1[16], Q1[15], Q1[14]) + Q1[13] + X1[ 0] + K1, 3); if((Q0[17] - Q1[17]) != 0x8e000000) continue; Q0[18] = RL(G(Q0[17], Q0[16], Q0[15]) + Q0[14] + X0[ 4] + K1, 5); Q1[18] = RL(G(Q1[17], Q1[16], Q1[15]) + Q1[14] + X1[ 4] + K1, 5); if(Q0[18] != Q1[18]) continue; Q0[19] = RL(G(Q0[18], Q0[17], Q0[16]) + Q0[15] + X0[ 8] + K1, 9); Q1[19] = RL(G(Q1[18], Q1[17], Q1[16]) + Q1[15] + X1[ 8] + K1, 9); if(Q0[19] != Q1[19]) continue; Q0[20] = RL(G(Q0[19], Q0[18], Q0[17]) + Q0[16] + X0[12] + K1, 13); Q1[20] = RL(G(Q1[19], Q1[18], Q1[17]) + Q1[16] + X1[12] + K1, 13); if((Q0[20] - Q1[20]) != 0xa0000000) continue; break; } if(i >= LOOP_11) goto md4_again;#define LOOP_12 0x4000000 for(i = 0; i < LOOP_12; i++) { Q0[ 1] = random() & ~(0x00000040 | 0x00000480); Q0[ 1] |= (IV[1] & 0x00000040) | (Q0[ 2] & 0x00000480); Q1[ 1] = Q0[ 1]; X0[ 0] = RR(Q0[ 1], 3) - F(IV[1], IV[2], IV[3]) - IV[0]; X1[ 0] = X0[ 0]; X0[ 1] = RR(Q0[ 2], 7) - F(Q0[ 1], IV[1], IV[2]) - IV[3]; X1[ 1] = RR(Q1[ 2], 7) - F(Q1[ 1], IV[1], IV[2]) - IV[3]; if((X0[ 1] ^ X1[ 1]) != 0x80000000) continue; X0[ 2] = RR(Q0[ 3], 11) - F(Q0[ 2], Q0[ 1], IV[1]) - IV[2]; X1[ 2] = RR(Q1[ 3], 11) - F(Q1[ 2], Q1[ 1], IV[1]) - IV[2]; if((X0[ 2] ^ X1[ 2]) != 0x90000000) continue; X0[ 3] = RR(Q0[ 4], 19) - F(Q0[ 3], Q0[ 2], Q0[ 1]) - IV[1]; X1[ 3] = RR(Q1[ 4], 19) - F(Q1[ 3], Q1[ 2], Q1[ 1]) - IV[1]; if(X0[ 3] != X1[ 3]) continue; X0[ 4] = RR(Q0[ 5], 3) - F(Q0[ 4], Q0[ 3], Q0[ 2]) - Q0[ 1]; X1[ 4] = RR(Q1[ 5], 3) - F(Q1[ 4], Q1[ 3], Q1[ 2]) - Q1[ 1]; if(X0[ 4] != X1[ 4]) continue;?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -