谁能告诉我md5加密的原理？
以下是她在国际密码学会发表的关于破解原理的论文。
哈希函数的冲突
哈希函数的冲突
MD4、MD5、HAVAL-128和RIPEMD
王晓云1，邓国锋2，来3，于洪波1
山东大学数学与系统科学学院，济南250100，中国1
中国科学院软件研究所，北京100080
上海交通大学计算机科学与工程系，上海，中国
xywang@sdu.edu.cn1
修订于2004年8月17日
1 MD5冲突
MD5是Ron Rivest [9]设计的哈希函数，是MD4 [8]的加强版。在1993伯特登
Boer和Antoon Bosselaers [1]发现了MD5的伪冲突，MD5由两个相同的消息组成
不同组的初始值。H. Dobbertin[3]发现了一个由两个不同的512位组成的自由开始碰撞
具有选定初始值0 V I的消息。
ED BA x C B F x C B AC x A V I 763 4 0 D，97 62 5 0，341042 3 0x B，2375 12 0 : 0 0 0 0 0
我们的攻击可以发现许多由两个1024位消息与原始消息组成的真实冲突
MD5的初始值0 IV:
10325476 0，98 0，89 0 67452301 0 0:0 0 0 0 0 x D bad cfe x C xefcdab，B x A IV
) 0 , 2 ,..., 2 ,..., 2 , 0 , 0 , 0 , 0 ( , 31 15 31
1 1
) 0 , 2 ,..., 2 ,..., 2 , 0 , 0 , 0 , 0 ( , 31 15 31
2 2 C C N N i i
(位置4，11和14处的非零值)
到这样的程度
)，(5)，(5 i i N M MD N M MD。
在IBM P690上，找到这样的M和M大约需要一个小时，之后，只需要15秒到5
分钟找到i N和i N，这样，(i N M和)，(i N M将产生相同的散列相同的值。此外，
我们的攻击对任何给定的初始值都有效。
以下是两对产生冲突的1024位消息，这两个示例具有相同的1-st
半512位。
M
2dd 31d 1 C4 eee 6 c 5 69 a3d 69 5 cf 9 af 98 87 b5 ca 2f ab 7e 4612 3e 580440 897 ffbb 8
634 ad 55 2b3f 409 8388 e 483 5a 417125 e 8255108 9 fc9 CDF 7 f2bd 1dd 9 5b3c 3780
X1
N1
d 11d0b 96 9c7b 41dc f 497 d8e 4d 555655 a c79a 7335 cf debf 0 66f 12930 8fb 109d 1
797 f 2775 eb5cd 530 baade 822 5c 15cc 79 ddcb 74 ed 6 DD 3c 55 f d 80 a9 bb 1 E3 a7 cc 35
M0
2dd 31d 1 C4 eee 6 c 5 69 a3d 69 5 cf 9 af 98 7 b5 ca 2f ab 7e 4612 3e 580440 897 ffbb 8
634 ad 55 2b3f 409 8388 e 483 5a 41f 125 e 8255108 9 fc9 CDF 7 72bd 1dd 9 5b3c 3780
X1
N1
d 11d0b 96 9c7b 41dc f 497 d8e 4d 555655 a 479 a 7335 cf debf 0 66f 12930 8fb 109d 1
797 f 2775 eb5cd 530 baade 822 5c 154 c 79 ddcb 74 ed 6 DD 3c 55 f 580 a9 bb 1 E3 a7 cc 35
h 9603161f f 41 fc 7 ef 9 f 65 ffbc a 30 f 9 DBF
M
2dd 31d 1 C4 eee 6 c 5 69 a3d 69 5 cf 9 af 98 87 b5 ca 2f ab 7e 4612 3e 580440 897 ffbb 8
634 ad 55 2b3f 409 8388 e 483 5a 417125 e 8255108 9 fc9 CDF 7 f2bd 1dd 9 5b3c 3780
X2
N2
313 e82d 8 5b8f 3456 d4ac 6 DAE c 619c 936 b4e 253 DD FD 03 da 87 6633902 A0 CD 48d 2
42339 Fe 9 e 87 e 570 f 70 b 654 ce 1 e0da 880 BC 2198 c 6 9383 A8 b 6 2b 65 f 996 702 af 76f
M0
2dd 31d 1 C4 eee 6 c 5 69 a3d 69 5 cf 9 af 98 7 b5 ca 2f ab 7e 4612 3e 580440 897 ffbb 8
634 ad 55 2b3f 409 8388 e 483 5a 41f 125 e 8255108 9 fc9 CDF 7 72bd 1dd 9 5b3c 3780
313 e82d 8 5b8f 3456 d4ac 6 DAE c 619c 936 34e 253 DD FD 03 da 87 6633902 A0 CD 48d 2
42339 Fe 9 e87e 570 f 70 b 654 ce 1e0d 2880 BC 2198 c 6 9383 A8 b 6 ab65f 996 702 af 76f
h8 d5e 7019 6324 c 015 715 d6b 58 61804 e08
表1 MD5的两对冲突
哈弗-128两起碰撞
哈弗拟在【10】。HAVAL是一种哈希算法，可以压缩3，4
并且产生长度为128、160、192或224位的指纹。
P. R. Kasselman和W . T . penz horn[7]对哈弗的简化版本进行了攻击
由哈弗-128的最后几轮组成。我们打破了哈弗-128的满员只剩26左右的哈弗
计算。这里我们举两个哈弗-128碰撞的例子，其中
) 0 ,..., 0 , 2 ,....2，0，0，0，2(，8 12 1
在位置0，11，18和31具有非零值，...2，1，0 i，这样)()(M哈弗M哈弗。
M1
6377448 b d 9 e 59 f 18 F2 aa 3c bb d6cb 92 ba ee 544 a 44 879 fa 576 1ca 34633 76 ca 5d 4 f
a 67 A8 a 42 8d 3 ADC 8 b b 6 e3d 814 5630998d 86 ea 5 DCD a 739 ae7b 54 fd8e 32 acbb2b 36
38183 c9a b67a 9289 c 47299 b 2 27039 ee5 DD 555 e 14 839018d 8 aa bbd 9 c 9d 78fc 632
fff 4b 3a 7 400000096 7 f 466 AAC fffffbc 0 5f 4016 D2 5f 4016d 0 12 e2b 0 f 4307 f 87
M1
6377488 b d 9 e 59 f 18 f 2 aa 3c bb d6cb 92 ba ee 544 a 44 879 fa 576 1ca 34633 76 ca 5d 4 f
a 67 A8 a 42 8d 3 ADC 8 b b 6 e3d 814d 630998d 86 ea 5 DCD a 739 ae7b 54 fd8e 32 acbb 2 b 36
38183 c9a b67a 9289 c 47299 ba 27039 ee5 DD 555 e 14 839018d 8 aa bbd 9 c 9d 78fc 632
fff 4b 3a 7 400000096 7 f 466 AAC fffffbc 0 5f 4016 D2 5f 4016d 0 12 e2b 0 f 4307 f 87
h 95b 5621c ca 62817a a 48 dacd 8 6d2b 54 BF
货币供应量之二
6377448 b d 9 e 59 f 18 F2 aa 3c bb d6cb 92 ba ee 544 a 44 879 fa 576 1ca 34633 76 ca 5d 4 f
a 67 A8 a 42 8d 3 ADC 8 b b 6 e3d 814 5630998d 86 ea 5 DCD a 739 ae7b 54 fd8e 32 acbb2b 36
38183 c9a b67a 9289 c 47299 b 2 27039 ee5 DD 555 e 14 839018d 8 aa bbd 9 c 9d 78fc 632
fff 4b 3a 7 400000096 7 f 466 AAC fffffbc 0 5f 4016 D2 5f 4016d 0 12 e2b 0 f5b 16963
6377488 b d 9 e 59 f 18 f 2 aa 3c bb d6cb 92 ba ee 544 a 44 879 fa 576 1ca 34633 76 ca 5d 4 f
a 67 A8 a 42 8d 3 ADC 8 b b 6 e3d 814d 630998d 86 ea 5 DCD a 739 ae7b 54 fd8e 32 acbb 2 b 36
38183 c9a b67a 9289 c 47299 ba 27039 ee5 DD 555 e 14 839018d 8 aa bbd 9 c 9d 78fc 632
fff 4b 3a 7 400000096 7 f 466 AAC fffffbc 0 5f 4016 D2 5f 4016d 0 12 e2b 0 f5b 16963
h b0e 99492 d64eb 647 5149 ef 30 4293733 c
表2两对碰撞，其中i=11，这两个例子只在最后一个字上不同
MD4的3次冲突
MD4由R. L. Rivest设计[8]。H. Dobbertin在Eurocrypto'96[2]中的攻击可以找到与
概率1/222。我们的攻击可以用手计算发现碰撞，这样
)0，0，0，2，0，0，0，0，0，0，0，2 2，2，0(，16 31 28 31 C C M M
和)(4 ) ( 4 M MD M MD。
M1
4d 7 a9 c 83 56 CB 927 a b 9 d5a 578 57 a 7 a5 ee de 748 a3 c DCC 366 B3 b 683 a 020 3 B2 a5 d 9 f
c69d 71 B3 f9e 99198 d79f 805 e a 63 bb 2e 8 45 dd8e 31 97e 31 Fe 5 2794 bf08 b 9 E8 c3e 9
M1
4d 7 a9 c 83 d6cb 927 a 29 d5a 578 57 a7 a5 ee de 748 a3 c DCC 366 B3 b683a 020 3 B2 a5 d 9 f
c69d 71 B3 f9e 99198 d79f 805 e a 63 bb 2e 8 45 dc8e 31 97e 31 Fe 5 2794 bf08 b 9e 8 c3e 9
h 5f5c 1a0d 71b 36046 1b 5435 da 9b0d 807 a
货币供应量之二
4d 7 a9 c 83 56 CB 927 a b 9 d5a 578 57 a 7 a5 ee de 748 a3 c DCC 366 B3 b 683 a 020 3 B2 a5 d 9 f
c69d 71 B3 f9e 99198 d79f 805 e a 63 bb 2e 8 45 dd8e 31 97e 31 Fe 5 f 713c 240 a7b 8 cf 69
4d 7 a9 c 83 d6cb 927 a 29 d5a 578 57 a7 a5 ee de 748 a3 c DCC 366 B3 b683a 020 3 B2 a5 d 9 f
c69d 71 B3 f9e 99198 d79f 805 e a 63 bb 2e 8 45 dc8e 31 97e 31 Fe 5 f 713c 240 a7b 8 cf 69
h e0f 76122 c 429 c 56c ebb 5 e 256 b 809793
表MD4的两对碰撞
RIPEMD的4次冲突
RIPEMD是为RIPE项目开发的(RACE integrity Primitives evaluation，1988-1992)。在…里
1995，H. Dobbertin证明了具有两轮的缩减版RIPEMD不是无碰撞的[4]。我们展示
完整的RIPEMD也不是无冲突的。以下是RIPEMD的两对冲突:
)2，0，0，0，0，2 2，0，0，0，0，0，0，2，0，0，0，0(，31 31 1 20 ' C C M M I
M1
579 faf8e 9 ECF 579 574 a6 ABA 78413511 a2b 410 a4 ad 2 f 6 c 9 f b 56202 c 4d 757911
bde aae 7 78 BC 91 F2 47 BC 6d 7d 9 abdd 1 a45d 2015 817104 ff 264758 A8 61064 ea 5
M1
579 faf8e 9 ECF 579 574 a6 ABA 78513511 a2b 410 a4 ad 2 f 6 c 9 f b 56202 c 4d 757911
bde aae 7 78 BC 91 F2 c 7c 06d 7d 9 abdd 1 a45d 2015 817104 ff 264758 A8 e 1064 ea 5
h 1 fab 152 1654 a 31b 7a 33776 a 9e 968 ba 7
货币供应量之二
579 faf8e 9 ECF 579 574 a6 ABA 78413511 a2b 410 a4 ad 2 f 6 c 9 f b 56202 c 4d 757911
bde aae 7 78 BC 91 F2 47 BC 6d 7d 9 abdd 1 a45d 2015 a0a 504 ff b 18d 58 a 8 e 70 c 66 b 6
579 faf8e 9 ECF 579 574 a6 ABA 78513511 a2b 410 a4 ad 2 f 6 c 9 f b 56202 c 4d 757911
bde aae 7 78 BC 91 F2 c 7c 06d 7d 9 abdd 1 a45d 2015 a0a 504 ff b 18d 58 a 8 670 c66b 6
h 1f2c 159 f 569 b 31 a6 dfcaa 51a 25665 d24
表RIPEMD的碰撞
5备注
除了我们破解的上述哈希函数之外，还有一些其他的哈希函数不具有理想的安全性。为
例如，SHA-0 [6]的冲突可以用SHA-0算法的大约240次计算和一个冲突来发现
对于哈弗-160可以用概率1/232找到。
请注意，本文中的消息和所有其他值由32位字组成，每个32位字中
最左边的字节是最高有效字节。
1 B. den Boer，Antoon Bosselaers，MD5压缩函数的碰撞，Eurocrypto，93。
2 H. Dobbertin，MD4的密码分析，快速软件加密，LNCS 1039，d .，施普林格出版社，1996。
3 H. Dobbertin，MD5压缩的密码分析，在EurocrZpt’96的rump会议上发表。
4 Hans Dobbertin，具有双轮压缩功能RIPEMD不是无冲突的，密码学杂志10(1)，
1997.
5 H. Dobbertin，A. Bosselaers，B. Preneel，“rip memd-160:rip mmd的加强版”，Fast
软件加密，LNCS 1039，D.Gollmann编辑。，施普林格出版社，1996，第71-82页。
6 FIPS 180-1，安全散列标准，NIST，美国商务部，华盛顿特区，邮编:1995。
7王晓明，王晓明，李晓明，计算机密码分析，2000，11(2)
信件，2000年。
8 R. L. Rivest，MD4消息摘要算法，征求意见稿(RFC)1320，互联网活动
互联网隐私工作组委员会，4月1992。
9 R. L Rivest，MD5消息摘要算法，征求意见稿(RFC)1321，互联网活动
互联网隐私工作组理事会，4月1992.3日
10 Y .郑，J. Pieprzyk，J. Seberry，HAVAL -一种输出长度可变的单向哈希算法，
92年的Auscrypto。