md4coll.c

用c语言实现得用于测试/md4md5散列算法的可碰撞性算法,用于证明md4/md5的可碰撞性

/* MD4 Collision Generator by Patrick Stach <[e-mail]>
 * 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	0x6ED9EBA1

unsigned 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;