[翻译]王小云论文：散列函数中的碰撞

散列（哈希）函数 MD4、MD5、HAVAL-128 和 RIPEMD 中的碰撞

原著：Wang Xiaoyun Feng Dengguo Lai Xuejia Yu Hongbo

[由于不知道各人具体的姓名，不便用中文] （中国济南 山东大学 数学和系统科学院 250100、中国北京 中国科学研究院软件学会 100080、中国上海

上海交通大学计算机科学和机械部） xywang@sdu.edu.cn

原文：收藏

翻译：lover_P

1 MD5 中的碰撞

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

634ad55 2b3f409 8388e483 5a417125 e8255108 9fc9cdf7 f2bd1dd9

5b3c3780

N1

d11d0b96 9c7b41dc f497d8e4 d555655a

c79a7335 cfdebf0 66f12930 8fb109d1

797f2775 eb5cd530 baade822 5c15cc79 ddcb74ed 6dd3c55f d80a9bb1 e3a7cc35

X1'

M'

2dd31d1 c4eee6c5 69a3d69 5cf9af98

7b5ca2f ab7e4612 3e580440 897ffbb8

634ad55 2b3f409 8388e483 5a41f125 e8255108 9fc9cdf7 72bd1dd9

5b3c3780

N1

d11d0b96 9c7b41dc f497d8e4 d555655a

479a7335 cfdebf0 66f12930 8fb109d1

797f2775 eb5cd530 baade822 5c154c79 ddcb74ed 6dd3c55f 580a9bb1 e3a7cc35

H

9603161f f41fc7ef 9f65ffbc a30f9dbf

X2

M

2dd31d1 c4eee6c5 69a3d69 5cf9af98

87b5ca2f ab7e4612 3e580440 897ffbb8

634ad55 2b3f409 8388e483 5a417125 e8255108 9fc9cdf7 f2bd1dd9 5b3c3780

N2

313e82d8 5b8f3456 d4ac6dae c619c936

b4e253dd fd03da87 6633902 a0cd48d2

42339fe9 e87e570f 70b654ce 1e0da880 bc2198c6 9383a8b6 2b65f996 702af76f

X2'

M'

2dd31d1 c4eee6c5 69a3d69 5cf9af98

7b5ca2f ab7e4612 3e580440 897ffbb8

634ad55 2b3f409 8388e483 5a41f125 e8255108 9fc9cdf7 72bd1dd9 5b3c3780

N2

313e82d8 5b8f3456 d4ac6dae c619c936

34e253dd fd03da87 6633902 a0cd48d2

42339fe9 e87e570f 70b654ce 1e0d2880 bc2198c6 9383a8b6 ab65f996 702af76f

H

8d5e7019 6324c015 715d6b58 61804e08

表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

a67a8a42 8d3adc8b b6e3d814 5630998d 86ea5dcd a739ae7b 54fd8e32 acbb2b36

38183c9a b67a9289 c47299b2 27039ee5 dd555e14 839018d8 aabbd9c9 d78fc632

fff4b3a7 40000096 7f466aac fffffbc0 5f4016d2 5f4016d0 12e2b0 f4307f87

M1'

6377488b d9e59f18 f2aa3cbb d6cb92ba ee544a44 879fa576 1ca34633

76ca5d4f

a67a8a42 8d3adc8b b6e3d814 d630998d 86ea5dcd a739ae7b 54fd8e32 acbb2b36

38183c9a b67a9289 c47299ba 27039ee5 dd555e14 839018d8 aabbd9c9 d78fc632

fff4b3a7 40000096 7f466aac fffffbc0 5f4016d2 5f4016d0 12e2b0 f4307f87

H

95b5621c ca62817a a48dacd8 6d2b54bf

M2

6377448b d9e59f18 f2aa3cbb d6cb92ba ee544a44 879fa576 1ca34633

76ca5d4f

a67a8a42 8d3adc8b b6e3d814 5630998d 86ea5dcd a739ae7b 54fd8e32 acbb2b36

38183c9a b67a9289 c47299b2 27039ee5 dd555e14 839018d8 aabbd9c9 d78fc632

fff4b3a7 40000096 7f466aac fffffbc0 5f4016d2 5f4016d0 12e2b0 f5b16963

M2'

6377488b d9e59f18 f2aa3cbb d6cb92ba ee544a44 879fa576 1ca34633

76ca5d4f

a67a8a42 8d3adc8b b6e3d814 d630998d 86ea5dcd a739ae7b 54fd8e32 acbb2b36

38183c9a b67a9289 c47299ba 27039ee5 dd555e14 839018d8 aabbd9c9 d78fc632

fff4b3a7 40000096 7f466aac fffffbc0 5f4016d2 5f4016d0 12e2b0 f5b16963

H

b0e99492 d64eb647 5149ef30 4293733c

表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

c69d71b3 f9e99198 d79f805e a63bb2e8 45dd8e31 97e31fe5 2794bf08 b9e8c3e9

M1'

4d7a9c83 d6cb927a 29d5a578 57a7a5ee

de748a3c dcc366b3 b683a020 3b2a5d9f

c69d71b3 f9e99198 d79f805e a63bb2e8 45dc8e31 97e31fe5 2794bf08 b9e8c3e9

H

5f5c1a0d 71b36046 1b5435da 9b0d807a

M2

4d7a9c83 56cb927a b9d5a578 57a7a5ee

de748a3c dcc366b3 b683a020 3b2a5d9f

c69d71b3 f9e99198 d79f805e a63bb2e8 45dd8e31 97e31fe5 f713c240 a7b8cf69

M2'

4d7a9c83 d6cb927a 29d5a578 57a7a5ee

de748a3c dcc366b3 b683a020 3b2a5d9f

c69d71b3 f9e99198 d79f805e a63bb2e8 45dc8e31 97e31fe5 f713c240 a7b8cf69

H

e0f76122 c429c56c ebb5e256 b809793

表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

bdeaae7 78bc91f2 47bc6d7d 9abdd1b1 a45d2015 817104ff 264758a8 61064ea5

M1'

579faf8e 9ecf579 574a6aba 78513511

a2b410a4 ad2f6c9f b56202c 4d757911

bdeaae7 78bc91f2 c7c06d7d 9abdd1b1 a45d2015 817104ff 264758a8 e1064ea5

H

1fab152 1654a31b 7a33776a 9e968ba7

M2

579faf8e 9ecf579 574a6aba 78413511

a2b410a4 ad2f6c9f b56202c 4d757911

bdeaae7 78bc91f2 47bc6d7d 9abdd1b1 a45d2015 a0a504ff b18d58a8 e70c66b6

M2'

579faf8e 9ecf579 574a6aba 78513511

a2b410a4 ad2f6c9f b56202c 4d757911

bdeaae7 78bc91f2 c7c06d7d 9abdd1b1 a45d2015 a0a504ff b18d58a8 670c66b6

H

1f2c159f 569b31a6 dfcaa51a 25665d24

表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.

• ·自己写的一个删除目录的代码（自己感觉不错200
• ·推荐个人网站使用的计数器
• ·oracle 学习笔记之一
• ·用IIs调试程序时错误代码不出现的问题解决方法
• ·AspectJ 开发环境指南 ——Aspect
• ·研究Bt下载的一点感想(1)
• ·Rotor, Mono 和 .NET
• ·AspectJ 开发环境指南 ——目录
• ·全中文全可视编程语言——“易语言”
• ·SAP推出的SMB是什么？ SAP出牌SMB