‹‹ 上一主题 | 下一主题 ››
发新话题
打印

[转载]MD4 Collision Generator

zhcin

荣誉会员

Rank: 6Rank: 6Rank: 6

帖子
130 
精华
0 
积分
314 
阅读权限
100 
在线时间
1 小时 
注册时间
2005-1-2 
最后登录
2008-5-31 
楼主 大 中 小 发表于 2005-11-16 12:49  只看该作者

[转载]MD4 Collision Generator

MD4 Collision Generator by Patrick Stach <pstach@stachliu.com>
* Implementation of paper by Xiaoyun Wang, et. al.  (王小云)
复制内容到剪贴板
代码:
/* MD4 Collision Generator by Patrick Stach <[email]pstach@stachliu.com[/email]>
* 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;

           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]
         &nbs

...

[Message clipped]
省略部分参照 MD5 Collision Generator
你善良的像猫儿，你忠实的像狗，你可爱像鸟儿,你识途像马儿,你出色像蝶儿,你勤劳像蜂儿,你什么都相像,也难怪大家都叫你…………禽兽

TOP

‹‹ 上一主题 | 下一主题 ››
发新话题