原著：Wang Xiaoyun Feng Dengguo Lai Xuejia Yu Hongbo [由于不知道各人具体的姓名，不便用中文] （中国济南 山东大学 数学和系统科学院 250100、中国北京 中国科学研究院软件学会 100080、中国上海 上海交通大学计算机科学和机械部） [email protected]
原文：收藏
翻译：lover_P
MD5 由 Ron Rivest [9] 设计，是 MD4 [8] 的加强版。1993 年，Bert den Boer 和 Antoon Bosselaers [1] 发现了 MD5 算法的伪碰撞，它从两组不同的初始值得到了相同的消息。H. Dobbertin [3] 发现了一个单体状态的碰撞，它由一个给定的初始值 IV0' 所得到的两个不同的 512 位消息构成。
IV0': A0' = 0x12AC2375, B0' = 0x3B341042, C0' = 0x5F62B97C, D0' = 0xBA763ED
我们的攻击可以发现很多对具有相同原始初始值 IV0 的两个 1024 位 MD5 消息：
IV0: A0 = 0x67452301, B0 = 0xEFCDAB89, C0 = 098BADEFD, D0 = 0x10325476
M' = M + ΔC1, ΔC1 = (0, 0, 0, 0, 231, ..., 215, ..., 231, 0)
Ni' = Ni + ΔC2, ΔC2 = (0, 0, 0, 0 231, ..., -215, ..., 231, 0)
（位置4、11和14非零）
此时，
MD5(M, Ni) = MD5(M', Ni')
在 IBM P690 上，要用将近一个小时的时间来寻找这样的 M 和 M'，之后，只需要 15 秒到 5 分钟的时间就可以找到 Ni 和 Ni'，此时的 (M, Ni) 和 (M', Ni') 将产生相同的散列值。此外，我们的攻击可以工作于任意给定的初始值。
下面是会产生碰撞的两对 1024 位消息，这两个例子具有相同的前半部 512 位。
X1 M 2dd31d1 c4eee6c5 69a3d69 5cf9af98 87b5ca2f ab7e4612 3e580440 897ffbb8表1 MD5 的两对碰撞
2 HAVAL-128 中的碰撞HAVAL 也在提议之内 [10]。HAVAL 也是一种散列算法，通过对任意长度的消息经过 3、4 或 5 遍摘要产生一个长度为 128、160、192 或 224 位的指纹。
对 HAVAL 的一个简化版的攻击由 P. R. Kasselman 和 W. T. Penzhorn 给出 [7]，这由 HAVAL-128 的最后一轮（摘要）构成。而我们只通过大约 26 次 HAVAL 计算就破坏了整个 HAVAL-128 算法。这里我们给出 HAVAL-128 碰撞的两个例子，其中
M' = M + ΔC, ΔC = (2i-1, 0, 0, 0, 2i-12, ..., 2i-8, 0, ..., 0)
由于位置 0、11、18 非零，且 i = 0, 1, 2, ..., 31，因此 HAVAL(M) = HAVAL(M')。
M1 6377448b d9e59f18 f2aa3cbb d6cb92ba ee544a44 879fa576 1ca34633 76ca5d4f表2 两对碰撞，其中 i = 11 且这两个例子只有最后的一个字不同
3 MD4 中的碰撞MD4 由 R. L. Rivest [8] 设计。H. Dobbertin 于 Eurocrypto '96 的攻击 [2] 能够找到概率为 1/222 的碰撞。我们的攻击却可以通过手算来找到碰撞，如：
M' = M + ΔC, ΔC = (0, 231, -228 + 231, 0, 0, 0, 0, 0, 0, 0, 0, 0, -216, 0, 0, 0)
且 MD4(M) = MD4(M')。
M1 4d7a9c83 56cb927a b9d5a578 57a7a5ee de748a3c dcc366b3 b683a020 3b2a5d9f表3 MD4 的两对碰撞
4 RIPEMD 中的碰撞RIPEMD 由 RIPE 项目（RACE Integrrity Primitives Evalustion, 1988-1992）开发。在 1995 年，H. Dobbertin 提供的只有两轮（摘要）的 RIPEMD 简化版 [4] 并不是无碰撞的。而我们发现完整的 RIPEMD 也不是无碰撞的。下面是 RIPEMD 的两对碰撞：
Mi' = Mi + ΔC, ΔC = (0, 0, 0, 220, 0, 0, 0, 0, 0, 0, 218 + 231, 0, 0, 0, 0, 231)
M1 579faf8e 9ecf579 574a6aba 78413511 a2b410a4 ad2f6c9f b56202c 4d757911表4 RIPEMD 中的碰撞
5 备注除了上面我们破坏的几个散列函数，其他一些散列函数也并不具有理想的安全性。例如，SHA-0 [6] 的碰撞就可以通过大约 240 次 SHA-0 计算找到，以及 HAVAL-160 的一个概率为 1/232 的碰撞也是可以被找到的。
注意这篇报告中的所有消息和其他的值都是按照32位字分组的，每个32位字中的最左边一个字节是关键字节（译注：大尾数法表示）。
1 B. den Boer, Antoon Bosselaers, Collisions for the Compression Function of MD5, Eurocrypto,93.
2 H. Dobbertin, Cryptanalysis of MD4, Fast Software Encryption, LNCS 1039, D. , Springer-Verlag, 1996.
3 H. Dobbertin, Cryptanalysis of MD5 compress, presented at the rump session of EurocrZpt'96.
4 Hans Dobbertin, RIPEMD with Two-round Compress Function is Not Collision-Free, J. Cryptology 10(1),1997.
5 H. Dobbertin, A. Bosselaers, B. Preneel, "RIPMEMD-160: A Strengthened Version of RIPMMD," Fast Software EncrZption, LNCS 1039, D.Gollmann, Ed., Springer-Verlag, 1996, pp. 71-82.
6 FIPS 180-1, Secure hash standard, NIST, US Department of Commerce, Washington D. C., April 1995.
7 P. R. Kasselman, W T Penzhorn , Cryptananlysis od reduced version of HAVAL, Vol. 36, No. 1, Electronic Letters, 2000.
8 R. L. Rivest, The MD4 Message Digest Algorithm, Request for Comments (RFC)1320, Internet Activities Board, Internet Privacy Task Force, April 1992.
9 R. L Rivest, The MD5 Message Digest Algorithm, Request for Comments (RFC)1321, Internet Activities Board, Internet PrivacZ Task Force, April 1992.3RIPEMD-1281
10 Y. Zheng, J. Pieprzyk, J. Seberry, HAVAL--A One-way Hashing Algorithm with Variable Length of Output, Auscrypto'92.
本文地址：http://com.8s8s.com/it/it32980.htm