散列函数中的碰撞 (copy过来备忘,准备写代码)

类别:软件工程 点击:0 评论:0 推荐:
[翻译]王小云论文:散列函数中的碰撞 散列(哈希)函数 MD4、MD5、HAVAL-128 和 RIPEMD 中的碰撞

原著:Wang Xiaoyun  Feng Dengguo  Lai Xuejia  Yu Hongbo [由于不知道各人具体的姓名,不便用中文] (中国济南 山东大学 数学和系统科学院 250100、中国北京 中国科学研究院软件学会 100080、中国上海 上海交通大学计算机科学和机械部) [email protected]
原文
:收藏
翻译: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.

本文地址:http://com.8s8s.com/it/it32980.htm