（哈希）函数 MD4、MD5、HAVAL-128 和 RIPEMD 中的碰撞.doc
4星 · 超过85%的资源 需积分: 13 200 浏览量
2011-04-10
01:49:00
上传
评论
收藏 70KB DOC 举报 
散列（哈希）函数 MD4、MD5、HAVAL-128 和 RIPEMD 中的碰撞
1 MD5 中的碰撞
MD5 由 Ron Rivest [9] 设计，是 MD4 [8] 的加强版。1993 年，Bert
den Boer 和 Antoon Bosselaers [1] 发现了 MD5 算法的伪碰撞，它从两组
不同的初始值得到了相同的消息。H. Dobbertin [3] 发现了一个单体状态的碰
撞，它由一个给定的初始值 IV
0
' 所得到的两个不同的 512 位消息构成。
IV
0
': A
0
' = 0x12AC2375, B
0
' = 0x3B341042, C
0
' = 0x5F62B97C, D
0
' = 0xBA763ED
我们的攻击可以发现很多对具有相同原始初始值 IV
0
的两个 1024 位 MD5
消息：
IV
0
: A
0
= 0x67452301, B
0
= 0xEFCDAB89, C
0
= 098BADEFD, D
0
= 0x10325476
M' = M + ΔC
1
, ΔC
1
= (0, 0, 0, 0, 2
31
, ..., 2
15
, ..., 2
31
, 0)
N
i
' = N
i
+ ΔC
2
, ΔC
2
= (0, 0, 0, 0 2
31
, ..., -2
15
, ..., 2
31
, 0)
（位置 4、11 和 14 非零）
此时，
MD5(M, N
i
) = MD5(M', N
i
')
在 IBM P690 上，要用将近一个小时的时间来寻找这样的 M 和 M'，之后，
只需要 15 秒到 5 分钟的时间就可以找到 N
i
和 N
i
'，此时的 (M, N
i
) 和 (M', N
i
')
将产生相同的散列值。此外，我们的攻击可以工作于任意给定的初始值。
下面是会产生碰撞的两对 1024 位消息，这两个例子具有相同的前半部 512 位。
X
1
M
2dd31d1 c4eee6c5 69a3d69 5cf9af98 87b5ca2f ab7e4612
3e580440 897&bb8
634ad55 2b3f409 8388e483 5a417125 e8255108 9fc9cdf7
f2bd1dd9 5b3c3780
N
1
d11d0b96 9c7b41dc f497d8e4 d555655a c79a7335 cfdebf0
66f12930 8fb109d1
797f2775 eb5cd530 baade822 5c15cc79 ddcb74ed 6dd3c55f
d80a9bb1 e3a7cc35
X
1
'M'
2dd31d1 c4eee6c5 69a3d69 5cf9af98 7b5ca2f ab7e4612
3e580440 897&bb8
资源评论
sunjia9616732782012-09-16很好，对在meo软件中的哈希函数调用很有帮助
