md4coll.c

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

                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;

                Q0[21] = RL(G(Q0[20], Q0[19], Q0[18]) + Q0[17]
                        + X0[ 1] + K1,  3);
                Q1[21] = RL(G(Q1[20], Q1[19], Q1[18]) + Q1[17]
                        + X1[ 1] + K1,  3);
		if((Q0[21] - Q1[21]) != 0x70000000)
			continue;

                Q0[22] = RL(G(Q0[21], Q0[20], Q0[19]) + Q0[18]
                        + X0[ 5] + K1,  5);
                Q1[22] = RL(G(Q1[21], Q1[20], Q1[19]) + Q1[18]
                        + X1[ 5] + K1,  5);
		if(Q0[22] != Q1[22])
			continue;

                Q0[23] = RL(G(Q0[22], Q0[21], Q0[20]) + Q0[19]
                        + X0[ 9] + K1,  9);
                Q1[23] = RL(G(Q1[22], Q1[21], Q1[20]) + Q1[19]
                        + X1[ 9] + K1,  9);
		if(Q0[23] != Q1[23])
			continue;

                Q0[24] = RL(G(Q0[23], Q0[22], Q0[21]) + Q0[20]
                        + X0[13] + K1, 13);
                Q1[24] = RL(G(Q1[23], Q1[22], Q1[21]) + Q1[20]
                        + X1[13] + K1, 13);
		if(Q0[24] != Q1[24])
			continue;

                Q0[25] = RL(G(Q0[24], Q0[23], Q0[22]) + Q0[21]
                        + X0[ 2] + K1,  3);
                Q1[25] = RL(G(Q1[24], Q1[23], Q1[22]) + Q1[21]
                        + X1[ 2] + K1,  3);
		if(Q0[25] != Q1[25])
			continue;

                Q0[26] = RL(G(Q0[25], Q0[24], Q0[23]) + Q0[22]
                        + X0[ 6] + K1,  5);
                Q1[26] = RL(G(Q1[25], Q1[24], Q1[23]) + Q1[22]
                        + X1[ 6] + K1,  5);
		if(Q0[26] != Q1[26])
			continue;

                Q0[27] = RL(G(Q0[26], Q0[25], Q0[24]) + Q0[23]
                        + X0[10] + K1,  9);
                Q1[27] = RL(G(Q1[26], Q1[25], Q1[24]) + Q1[23]
                        + X1[10] + K1,  9);
		if(Q0[27] != Q1[27])
			continue;

                Q0[28] = RL(G(Q0[27], Q0[26], Q0[25]) + Q0[24]
                        + X0[14] + K1, 13);
                Q1[28] = RL(G(Q1[27], Q1[26], Q1[25]) + Q1[24]
                        + X1[14] + K1, 13);
		if(Q0[28] != Q1[28])
			continue;

                Q0[29] = RL(G(Q0[28], Q0[27], Q0[26]) + Q0[25]
                        + X0[ 3] + K1,  3);
                Q1[29] = RL(G(Q1[28], Q1[27], Q1[26]) + Q1[25]
                        + X1[ 3] + K1,  3);
		if(Q0[29] != Q1[29])
			continue;

                Q0[30] = RL(G(Q0[29], Q0[28], Q0[27]) + Q0[26]
                        + X0[ 7] + K1,  5);
                Q1[30] = RL(G(Q1[29], Q1[28], Q1[27]) + Q1[26]
                        + X1[ 7] + K1,  5);
		if(Q0[30] != Q1[30])
			continue;

                Q0[31] = RL(G(Q0[30], Q0[29], Q0[28]) + Q0[27]
                        + X0[11] + K1,  9);
                Q1[31] = RL(G(Q1[30], Q1[29], Q1[28]) + Q1[27]
                        + X1[11] + K1,  9);
		if(Q0[31] != Q1[31])
			continue;

                Q0[32] = RL(G(Q0[31], Q0[30], Q0[29]) + Q0[28]
                        + X0[15] + K1, 13);
                Q1[32] = RL(G(Q1[31], Q1[30], Q1[29]) + Q1[28]
                        + X1[15] + K1, 13);
		if(Q0[32] != Q1[32])
			continue;

                Q0[33] = RL(H(Q0[32], Q0[31], Q0[30]) + Q0[29]
                        + X0[ 0] + K2,  3);
                Q1[33] = RL(H(Q1[32], Q1[31], Q1[30]) + Q1[29]
                        + X1[ 0] + K2,  3);
		if(Q0[33] != Q1[33])
			continue;

                Q0[34] = RL(H(Q0[33], Q0[32], Q0[31]) + Q0[30]
                        + X0[ 8] + K2,  9);
                Q1[34] = RL(H(Q1[33], Q1[32], Q1[31]) + Q1[30]
                        + X1[ 8] + K2,  9);
		if(Q0[34] != Q1[34])
			continue;

                Q0[35] = RL(H(Q0[34], Q0[33], Q0[32]) + Q0[31]
                        + X0[ 4] + K2, 11);
                Q1[35] = RL(H(Q1[34], Q1[33], Q1[32]) + Q1[31]
                        + X1[ 4] + K2, 11);
		if(Q0[35] != Q1[35])
			continue;

                Q0[36] = RL(H(Q0[35], Q0[34], Q0[33]) + Q0[32]
                        + X0[12] + K2, 15);
                Q1[36] = RL(H(Q1[35], Q1[34], Q1[33]) + Q1[32]
                        + X1[12] + K2, 15);
		if((Q0[36] ^ Q1[36]) != 0x80000000)
			continue;

                Q0[37] = RL(H(Q0[36], Q0[35], Q0[34]) + Q0[33]
                        + X0[ 2] + K2,  3);
                Q1[37] = RL(H(Q1[36], Q1[35], Q1[34]) + Q1[33]
                        + X1[ 2] + K2,  3);
		if((Q0[37] ^ Q1[37]) != 0x80000000)
			continue;

                Q0[38] = RL(H(Q0[37], Q0[36], Q0[35]) + Q0[34]
                        + X0[10] + K2,  9);
                Q1[38] = RL(H(Q1[37], Q1[36], Q1[35]) + Q1[34]
                        + X1[10] + K2,  9);
		if(Q0[38] != Q1[38])
			continue;

                Q0[39] = RL(H(Q0[38], Q0[37], Q0[36]) + Q0[35]
                        + X0[ 6] + K2, 11);
                Q1[39] = RL(H(Q1[38], Q1[37], Q1[36]) + Q1[35]
                        + X1[ 6] + K2, 11);
		if(Q0[39] != Q1[39])
			continue;

                Q0[40] = RL(H(Q0[39], Q0[38], Q0[37]) + Q0[36]
                        + X0[14] + K2, 15);
                Q1[40] = RL(H(Q1[39], Q1[38], Q1[37]) + Q1[36]
                        + X1[14] + K2, 15);
		if(Q0[40] != Q1[40])
			continue;

                Q0[41] = RL(H(Q0[40], Q0[39], Q0[38]) + Q0[37]
                        + X0[ 1] + K2,  3);
                Q1[41] = RL(H(Q1[40], Q1[39], Q1[38]) + Q1[37]
                        + X1[ 1] + K2,  3);
		if(Q0[41] != Q1[41])
			continue;

                Q0[42] = RL(H(Q0[41], Q0[40], Q0[39]) + Q0[38]
                        + X0[ 9] + K2,  9);
                Q1[42] = RL(H(Q1[41], Q1[40], Q1[39]) + Q1[38]
                        + X1[ 9] + K2,  9);
		if(Q0[42] != Q1[42])
			continue;

                Q0[43] = RL(H(Q0[42], Q0[41], Q0[40]) + Q0[39]
                        + X0[ 5] + K2, 11);
                Q1[43] = RL(H(Q1[42], Q1[41], Q1[40]) + Q1[39]
                        + X1[ 5] + K2, 11);
		if(Q0[43] != Q1[43])
			continue;

                Q0[44] = RL(H(Q0[43], Q0[42], Q0[41]) + Q0[40]
                        + X0[13] + K2, 15);
                Q1[44] = RL(H(Q1[43], Q1[42], Q1[41]) + Q1[40]
                        + X1[13] + K2, 15);
		if(Q0[44] != Q1[44])
			continue;

                Q0[45] = RL(H(Q0[44], Q0[43], Q0[42]) + Q0[41]
                        + X0[ 3] + K2,  3);
                Q1[45] = RL(H(Q1[44], Q1[43], Q1[42]) + Q1[41]
                        + X1[ 3] + K2,  3);
		if(Q0[45] != Q1[45])
			continue;

                Q0[46] = RL(H(Q0[45], Q0[44], Q0[43]) + Q0[42]
                        + X0[11] + K2,  9);
                Q1[46] = RL(H(Q1[45], Q1[44], Q1[43]) + Q1[42]
                        + X1[11] + K2,  9);
		if(Q0[46] != Q1[46])
			continue;

                Q0[47] = RL(H(Q0[46], Q0[45], Q0[44]) + Q0[43]
                        + X0[ 7] + K2, 11);
                Q1[47] = RL(H(Q1[46], Q1[45], Q1[44]) + Q1[43]
                        + X1[ 7] + K2, 11);
		if(Q0[47] != Q1[47])
			continue;

                Q0[48] = RL(H(Q0[47], Q0[46], Q0[45]) + Q0[44]
                        + X0[15] + K2, 15);
                Q1[48] = RL(H(Q1[47], Q1[46], Q1[45]) + Q1[44]
                        + X1[15] + K2, 15);
		if(Q0[48] != Q1[48])
			continue;
                break;
        }
	if(i >= LOOP_12)
		goto md4_again;
	return;
}

int main(int argc, char *argv[])
{
	size_t i;

	srandom(time(NULL) ^ (getpid() << 16));

	if(argc == 5)
	{
		IV[0] = strtoul(argv[1], NULL, 16);
		IV[1] = strtoul(argv[2], NULL, 16);
		IV[2] = strtoul(argv[3], NULL, 16);
		IV[3] = strtoul(argv[4], NULL, 16);
	}

	md4gen();

	printf("unsigned int m0[16] = {\n");
	for(i = 0; i < 16; i++)
	{
		printf("0x%08x%c ", X0[ i], (i < 15) ? ',' : ' ');
		if((i & 3) == 3)
			printf("\n");
	}
	printf("};\n\n");
	printf("unsigned int m1[16] = {\n");
	for(i = 0; i < 16; i++)
	{
		printf("0x%08x%c ", X1[ i], (i < 15) ? ',' : ' ');
		if((i & 3) == 3)
			printf("\n");
	}
	printf("};\n\n");
	return 0;
}