📄 md5coll.cpp
字号:
/* MD5 Collision Generator by Patrick Stach
* Implementation of paper by Xiaoyun Wang, et all.
*
* A few optimizations to make the solving method a bit more deterministic
*
* Usage:
* ./md5coll or ./md5coll IV0 IV1 IV2 IV3
*
* Requires being built as 32 bit (unsigned int as 32 bit)
*
* Any derivative works or references must cite the authors.
*
* Modified by marstone@marstone.net, 2007.01.10, Immigrate to Windows platform.
*
*/
#include <stdio.h>
#include <stdlib.h>
// #include <unistd.h>
#include <time.h>
#define F(x, y, z) (z ^ (x & (y ^ z)))
#define G(x, y, z) F(z, x, y)
#define H(x, y, z) (x ^ y ^ z)
#define I(x, y, z) (y ^ (x | ~z))
#define RL(x, y) (((x) << (y)) | ((x) >> (32 - (y))))
#define RR(x, y) (((x) >> (y)) | ((x) << (32 - (y))))
// add by marstone, to immigration to windows.
#define RANDOM() ((unsigned int)(RL((unsigned int)rand(), 16) + (unsigned int)rand()))
unsigned int A0, B0, C0, D0;
unsigned int A1, B1, C1, D1;
unsigned int IV[4] = { 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476 };
// unsigned int IV[4] = { 0x2eb621f1, 0x638c200f, 0xaa63371d, 0xc4718ab6 }; // MD5("634634")
unsigned int Q0[65], Q1[65];
unsigned int X0[32], X1[32];
void block1(void)
{
printf("start to block #1\n");
size_t i, max;
int firstloop = 1;
block1_again:
if(0 == firstloop) printf("\tDEBUG: i=%d, block #1 again.\n", i);
firstloop = 0;
for(;;)
{
/* C1 */
Q0[3] = RANDOM() & ~0x00800040;
Q1[3] = Q0[3];
/* B1 */
Q0[4] = (RANDOM() | 0x80080800) & ~(0x00800040 | 0x0077f780);
Q0[4] |= (Q0[3] & 0x0077f780);
Q1[4] = Q0[4];
/* A2 */
Q0[5] = (RANDOM() | 0x88400025) & ~0x02bfffc0;
Q1[5] = Q0[5] - 0x00000040;
/* D2 */
Q0[6] = (RANDOM() | 0x027fbc41) & ~(0x888043a4 | 0x7500001a);
Q0[6] |= (Q0[5] & 0x7500001a);
Q1[6] = Q0[6] - 0x7f800040;
/* C2 */
Q0[7] = (RANDOM() | 0x03fef820) & ~0xfc0107df;
Q1[7] = Q0[7] - 0x07800041;
X0[6] = RR(Q0[7] - Q0[6], 17) - F(Q0[6], Q0[5], Q0[4])
- Q0[3] - 0xa8304613;
X1[6] = RR(Q1[7] - Q1[6], 17) - F(Q1[6], Q1[5], Q1[4])
- Q1[3] - 0xa8304613;
if(X0[6] != X1[6])
continue;
/* B2 */
Q0[8] = (RANDOM() | 0x01910540) & ~0xfe0eaabf;
Q1[8] = Q0[8] - 0x00827fff;
X0[7] = RR(Q0[8] - Q0[7], 22) - F(Q0[7], Q0[6], Q0[5])
- Q0[4] - 0xfd469501;
X1[7] = RR(Q1[8] - Q1[7], 22) - F(Q1[7], Q1[6], Q1[5])
- Q1[4] - 0xfd469501;
if(X0[7] != X1[7])
continue;
/* A3 */
Q0[9] = (RANDOM() | 0xfb102f3d) & ~(0x040f80c2 | 0x00001000);
Q0[9] |= (Q0[8] & 0x00001000);
Q1[9] = Q0[9] - 0x8000003f;
X0[8] = RR(Q0[9] - Q0[8], 7) - F(Q0[8], Q0[7], Q0[6])
- Q0[5] - 0x698098d8;
X1[8] = RR(Q1[9] - Q1[8], 7) - F(Q1[8], Q1[7], Q1[6])
- Q1[5] - 0x698098d8;
if(X0[8] != X1[8])
continue;
/* D3 */
Q0[10] = (RANDOM() | 0x401f9040) & ~0x80802183;
Q1[10] = Q0[10] - 0x7ffff000;
X0[9] = RR(Q0[10] - Q0[9], 12) - F(Q0[9], Q0[8], Q0[7])
- Q0[6] - 0x8b44f7af;
X1[9] = RR(Q1[10] - Q1[9], 12) - F(Q1[9], Q1[8], Q1[7])
- Q1[6] - 0x8b44f7af;
if(X0[9] != X1[9])
continue;
/* C3 */
Q0[11] = (RANDOM() | 0x000180c2) & ~(0xc00e3101 | 0x00004000);
Q0[11] |= (Q0[10] & 0x00004000);
Q1[11] = Q0[11] - 0x40000000;
X0[10] = RR(Q0[11] - Q0[10], 17) - F(Q0[10], Q0[9], Q0[8])
- Q0[7] - 0xffff5bb1;
X1[10] = RR(Q1[11] - Q1[10], 17) - F(Q1[10], Q1[9], Q1[8])
- Q1[7] - 0xffff5bb1;
if(X0[10] != X1[10])
continue;
/* B3 */
Q0[12] = (RANDOM() | 0x00081100) & ~(0xc007e080 | 0x03000000);
Q0[12] |= (Q0[11] & 0x03000000);
Q1[12] = Q0[12] - 0x80002080;
X0[11] = RR(Q0[12] - Q0[11], 22) - F(Q0[11], Q0[10], Q0[9])
- Q0[8] - 0x895cd7be;
X1[11] = RR(Q1[12] - Q1[11], 22) - F(Q1[11], Q1[10], Q1[9])
- Q1[8] - 0x895cd7be;
if((X0[11] ^ X1[11]) != 0x00008000)
continue;
/* A4 */
Q0[13] = (RANDOM() | 0x410fe008) & ~0x82000180;
Q1[13] = Q0[13] - 0x7f000000;
X0[12] = RR(Q0[13] - Q0[12], 7) - F(Q0[12], Q0[11], Q0[10])
- Q0[9] - 0x6b901122;
X1[12] = RR(Q1[13] - Q1[12], 7) - F(Q1[12], Q1[11], Q1[10])
- Q1[9] - 0x6b901122;
if(X0[12] != X1[12])
continue;
/* D4 */
Q0[14] = (RANDOM() | 0x000be188) & ~0xa3040000;
Q1[14] = Q0[14] - 0x80000000;
X0[13] = RR(Q0[14] - Q0[13], 12) - F(Q0[13], Q0[12], Q0[11])
- Q0[10] - 0xfd987193;
X1[13] = RR(Q1[14] - Q1[13], 12) - F(Q1[13], Q1[12], Q1[11])
- Q1[10] - 0xfd987193;
if(X0[13] != X1[13])
continue;
/* C4 */
Q0[15] = (RANDOM() | 0x21008000) & ~0x82000008;
Q1[15] = Q0[15] - 0x80007ff8;
X0[14] = RR(Q0[15] - Q0[14], 17) - F(Q0[14], Q0[13], Q0[12])
- Q0[11] - 0xa679438e;
X1[14] = RR(Q1[15] - Q1[14], 17) - F(Q1[14], Q1[13], Q1[12])
- Q1[11] - 0xa679438e;
if((X0[14] ^ X1[14]) != 0x80000000)
continue;
/* B4 */
Q0[16] = (RANDOM() | 0x20000000) & ~0x80000000;
Q1[16] = Q0[16] - 0xa0000000;
X0[15] = RR(Q0[16] - Q0[15], 22) - F(Q0[15], Q0[14], Q0[13])
- Q0[12] - 0x49b40821;
X1[15] = RR(Q1[16] - Q1[15], 22) - F(Q1[15], Q1[14], Q1[13])
- Q1[12] - 0x49b40821;
if(X0[15] != X1[15])
continue;
break;
}
#define LOOP_11 300
printf("\t\tLOOP #1 passed.\n");
for(i = 0; i < LOOP_11; i++)
{
/* A5 */
Q0[17] = RANDOM() & ~(0x80020000 | 0x00008008);
Q0[17] |= (Q0[16] & 0x00008008);
Q1[17] = Q0[17] - 0x80000000;
X0[1] = RR(Q0[17] - Q0[16], 5) - G(Q0[16], Q0[15], Q0[14])
- Q0[13] - 0xf61e2562;
X1[1] = RR(Q1[17] - Q1[16], 5) - G(Q1[16], Q1[15], Q1[14])
- Q1[13] - 0xf61e2562;
if(X0[1] != X1[1])
continue;
/* D5 */
Q0[18] = RL(G(Q0[17], Q0[16], Q0[15]) + Q0[14]
+ X0[6] + 0xc040b340, 9) + Q0[17];
if((Q0[18] & 0xa0020000)
!= (0x00020000 | (Q0[17] & 0x20000000)))
{
continue;
}
Q1[18] = RL(G(Q1[17], Q1[16], Q1[15]) + Q1[14]
+ X1[6] + 0xc040b340, 9) + Q1[17];
if((Q0[18] ^ Q1[18]) != 0x80000000)
continue;
/* C5 */
Q0[19] = RL(G(Q0[18], Q0[17], Q0[16]) + Q0[15]
+ X0[11] + 0x265e5a51, 14) + Q0[18];
if(Q0[19] & 0x80020000)
continue;
Q1[19] = RL(G(Q1[18], Q1[17], Q1[16]) + Q1[15]
+ X1[11] + 0x265e5a51, 14) + Q1[18];
if(Q0[19] - Q1[19] != 0x7ffe0000)
continue;
/* B5 */
Q0[20] = RANDOM() & ~0x80000000;
Q1[20] = Q0[20] - 0x80000000;
X0[0] = RR(Q0[20] - Q0[19], 20) - G(Q0[19], Q0[18], Q0[17])
- Q0[16] - 0xe9b6c7aa;
X1[0] = RR(Q1[20] - Q1[19], 20) - G(Q1[19], Q1[18], Q1[17])
- Q1[16] - 0xe9b6c7aa;
if(X0[0] != X1[0])
continue;
Q0[1] = RL(F(IV[1], IV[2], IV[3]) + IV[0]
+ X0[0] + 0xd76aa478, 7) + IV[1];
Q1[1] = Q0[1];
Q0[2] = RL(F(Q0[1], IV[1], IV[2]) + IV[3]
+ X0[1] + 0xe8c7b756, 12) + Q0[1];
Q1[2] = Q0[2];
X0[2] = RR(Q0[3] - Q0[2], 17) - F(Q0[2], Q0[1], IV[1])
- IV[2] - 0x242070db;
X1[2] = X0[2];
X0[3] = RR(Q0[4] - Q0[3], 22) - F(Q0[3], Q0[2], Q0[1])
- IV[1] - 0xc1bdceee;
X1[3] = X0[3];
X0[4] = RR(Q0[5] - Q0[4], 7) - F(Q0[4], Q0[3], Q0[2])
- Q0[1] - 0xf57c0faf;
X1[4] = RR(Q1[5] - Q1[4], 7) - F(Q1[4], Q1[3], Q1[2])
- Q1[1] - 0xf57c0faf;
if((X0[4] ^ X1[4]) != 0x80000000)
continue;
X0[5] = RR(Q0[6] - Q0[5], 12) - F(Q0[5], Q0[4], Q0[3])
- Q0[2] - 0x4787c62a;
X1[5] = RR(Q1[6] - Q1[5], 12) - F(Q1[5], Q1[4], Q1[3])
- Q1[2] - 0x4787c62a;
if(X0[5] != X1[5])
continue;
/* A6 */
Q0[21] = RL(G(Q0[20], Q0[19], Q0[18]) + Q0[17]
+ X0[5] + 0xd62f105d, 5) + Q0[20];
if((Q0[21] & 0x80020000) != (Q0[20] & 0x00020000))
continue;
Q1[21] = RL(G(Q1[20], Q1[19], Q1[18]) + Q1[17]
+ X1[5] + 0xd62f105d, 5) + Q1[20];
if((Q0[21] ^ Q1[21]) != 0x80000000)
continue;
/* D6 */
Q0[22] = RL(G(Q0[21], Q0[20], Q0[19]) + Q0[18]
+ X0[10] + 0x02441453, 9) + Q0[21];
if(Q0[22] & 0x80000000)
continue;
Q1[22] = RL(G(Q1[21], Q1[20], Q1[19]) + Q1[18]
+ X1[10] + 0x02441453, 9) + Q1[21];
if((Q0[22] ^ Q1[22]) != 0x80000000)
continue;
/* C6 */
Q0[23] = RL(G(Q0[22], Q0[21], Q0[20]) + Q0[19]
+ X0[15] + 0xd8a1e681, 14) + Q0[22];
if(Q0[23] & 0x80000000)
continue;
Q1[23] = RL(G(Q1[22], Q1[21], Q1[20]) + Q1[19]
+ X1[15] + 0xd8a1e681, 14) + Q1[22];
if(Q0[23] != Q1[23])
continue;
/* B6 */
Q0[24] = RL(G(Q0[23], Q0[22], Q0[21]) + Q0[20]
+ X0[4] + 0xe7d3fbc8, 20) + Q0[23];
Q1[24] = RL(G(Q1[23], Q1[22], Q1[21]) + Q1[20]
+ X1[4] + 0xe7d3fbc8, 20) + Q1[23];
if(Q0[24] != Q1[24])
continue;
/* A7 */
Q0[25] = RL(G(Q0[24], Q0[23], Q0[22]) + Q0[21]
+ X0[9] + 0x21e1cde6, 5) + Q0[24];
Q1[25] = RL(G(Q1[24], Q1[23], Q1[22]) + Q1[21]
+ X1[9] + 0x21e1cde6, 5) + Q1[24];
if(Q0[25] != Q1[25])
continue;
/* D7 */
Q0[26] = RL(G(Q0[25], Q0[24], Q0[23]) + Q0[22]
+ X0[14] + 0xc33707d6, 9) + Q0[25];
Q1[26] = RL(G(Q1[25], Q1[24], Q1[23]) + Q1[22]
+ X1[14] + 0xc33707d6, 9) + Q1[25];
if(Q0[26] != Q1[26])
continue;
/* C7 */
Q0[27] = RL(G(Q0[26], Q0[25], Q0[24]) + Q0[23]
+ X0[3] + 0xf4d50d87, 14) + Q0[26];
Q1[27] = RL(G(Q1[26], Q1[25], Q1[24]) + Q1[23]
+ X1[3] + 0xf4d50d87, 14) + Q1[26];
if(Q0[27] != Q1[27])
continue;
break;
}
if(i >= LOOP_11)
goto block1_again;
#define LOOP_12 0x20000000
printf("\t\t\tLOOP #2 passed.\n");
for(i = 0; i < LOOP_12; i++)
{
/* B5 */
Q0[20] ^= (1 << (RANDOM() % 31));
Q1[20] = Q0[20] - 0x80000000;
X0[0] = RR(Q0[20] - Q0[19], 20) - G(Q0[19], Q0[18], Q0[17])
- Q0[16] - 0xe9b6c7aa;
X1[0] = RR(Q1[20] - Q1[19], 20) - G(Q1[19], Q1[18], Q1[17])
- Q1[16] - 0xe9b6c7aa;
if(X0[0] != X1[0])
continue;
Q0[1] = RL(F(IV[1], IV[2], IV[3]) + IV[0]
+ X0[0] + 0xd76aa478, 7) + IV[1];
Q1[1] = Q0[1];
Q0[2] = RL(F(Q0[1], IV[1], IV[2]) + IV[3]
+ X0[1] + 0xe8c7b756, 12) + Q0[1];
Q1[2] = Q0[2];
X0[2] = RR(Q0[3] - Q0[2], 17) - F(Q0[2], Q0[1], IV[1])
- IV[2] - 0x242070db;
X1[2] = X0[2];
X0[3] = RR(Q0[4] - Q0[3], 22) - F(Q0[3], Q0[2], Q0[1])
- IV[1] - 0xc1bdceee;
X1[3] = X0[3];
X0[4] = RR(Q0[5] - Q0[4], 7) - F(Q0[4], Q0[3], Q0[2])
- Q0[1] - 0xf57c0faf;
X1[4] = RR(Q1[5] - Q1[4], 7) - F(Q1[4], Q1[3], Q1[2])
- Q1[1] - 0xf57c0faf;
if((X0[4] ^ X1[4]) != 0x80000000)
continue;
X0[5] = RR(Q0[6] - Q0[5], 12) - F(Q0[5], Q0[4], Q0[3])
- Q0[2] - 0x4787c62a;
X1[5] = RR(Q1[6] - Q1[5], 12) - F(Q1[5], Q1[4], Q1[3])
- Q1[2] - 0x4787c62a;
if(X0[5] != X1[5])
continue;
/* A6 */
Q0[21] = RL(G(Q0[20], Q0[19], Q0[18]) + Q0[17]
+ X0[5] + 0xd62f105d, 5) + Q0[20];
if((Q0[21] & 0x80020000) != (Q0[20] & 0x00020000))
continue;
Q1[21] = RL(G(Q1[20], Q1[19], Q1[18]) + Q1[17]
+ X1[5] + 0xd62f105d, 5) + Q1[20];
if((Q0[21] ^ Q1[21]) != 0x80000000)
continue;
/* D6 */
Q0[22] = RL(G(Q0[21], Q0[20], Q0[19]) + Q0[18]
+ X0[10] + 0x02441453, 9) + Q0[21];
if(Q0[22] & 0x80000000)
continue;
Q1[22] = RL(G(Q1[21], Q1[20], Q1[19]) + Q1[18]
+ X1[10] + 0x02441453, 9) + Q1[21];
if((Q0[22] ^ Q1[22]) != 0x80000000)
continue;
/* C6 */
Q0[23] = RL(G(Q0[22], Q0[21], Q0[20]) + Q0[19]
+ X0[15] + 0xd8a1e681, 14) + Q0[22];
if(Q0[23] & 0x80000000)
continue;
Q1[23] = RL(G(Q1[22], Q1[21], Q1[20]) + Q1[19]
+ X1[15] + 0xd8a1e681, 14) + Q1[22];
if(Q0[23] != Q1[23])
continue;
/* B6 */
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -