math - 导致 MD5 冲突的最短字符串对是什么？

Question

在不担心冲突的情况下，可以使用 MD5 作为哈希值，字符串长度最多为多少？

这可能是通过为特定字符集中的每个可能的字符串生成 MD5 哈希来计算的，长度不断增加，直到哈希第二次出现(冲突)。没有冲突的字符串的最大可能长度将比冲突对中最长的一个字符少一个字符。

是否已经针对 MD5、SHA1 等进行了测试？

Answer 1

更新

具有讽刺意味的是，在我发布之前的答案几周后，两位中国研究人员谢涛和冯登国published a new single-block collision for MD5 。直到现在我才知道那篇论文。单个 MD5 block 意味着输入大小为 64 字节或 512 位。请注意，输入大部分相同，仅存在 2 位差异。

他们的方法要到 2013 年 1 月才会发布，但现在可以使用论文中的数据来验证他们的碰撞:

>>> from array import array
>>> from hashlib import md5
>>> input1 = array('I',  [0x6165300e,0x87a79a55,0xf7c60bd0,0x34febd0b,0x6503cf04,
    0x854f709e,0xfb0fc034,0x874c9c65,0x2f94cc40,0x15a12deb,0x5c15f4a3,0x490786bb,
    0x6d658673,0xa4341f7d,0x8fd75920,0xefd18d5a])
>>> input2 = array('I', [x^y for x,y in zip(input1,
    [0, 0, 0, 0, 0, 1<<10, 0, 0, 0, 0, 1<<31, 0, 0, 0, 0, 0])])
>>> input1 == input2
False
>>> md5(input1).hexdigest()
'cee9a457e790cf20d4bdaa6d69f01e41'
>>> md5(input2).hexdigest()
'cee9a457e790cf20d4bdaa6d69f01e41'

更新:该论文已于 2013 年 3 月发表:Tao Xie and Fanbao Liu and Dengguo Feng - Fast Collision Attack on MD5

但是，如果您有更多的空间可以使用，几千字节的碰撞计算起来要快得多 - 在任何普通计算机上都可以在几小时内计算出它们。

旧答案

之前最短的冲突至少使用了两个 MD5 block 的输入——即 128 字节，1024 位。第一个 block 中的前缀可以由攻击者任意选择，其余的将被计算并显​​示为乱码。

这是两个不同的碰撞输入的示例，您可以在 Python 中自行尝试:

>>> from binascii import unhexlify
>>> from hashlib import md5
>>> input1 = 'Oded Goldreich\nOded Goldreich\nOded Goldreich\nOded Go' + unhexlify(
... 'd8050d0019bb9318924caa96dce35cb835b349e144e98c50c22cf461244a4064bf1afaecc582'
... '0d428ad38d6bec89a5ad51e29063dd79b16cf67c12978647f5af123de3acf844085cd025b956')
>>> len(input1)
128
>>> md5(input1).hexdigest()
'd320b6433d8ebc1ac65711705721c2e1'
>>> input2 = 'Neal Koblitz\nNeal Koblitz\nNeal Koblitz\nNeal Koblitz\n' + unhexlify(
... '75b80e0035f3d2c909af1baddce35cb835b349e144e88c50c22cf461244a40e4bf1afaecc582'
... '0d428ad38d6bec89a5ad51e29063dd79b16cf6fc11978647f5af123de3acf84408dcd025b956')
>>> md5(input2).hexdigest()
'd320b6433d8ebc1ac65711705721c2e1'

在 215 个节点的 Playstation 3 集群上生成这两个特定输入花了 2 天时间，by Mark Stevens :)