最多可以将 MD5 用作哈希而不担心发生冲突的可能性的字符串长度是多少？
这可能是通过为特定字符集中的每个可能的字符串生成一个 MD5 散列来计算的，长度增加，直到散列第二次出现（冲突）。没有冲突的字符串的最大可能长度将比冲突对中最长的字符少一个字符。
这是否已经针对 MD5、SHA1 等进行了测试？
问问题
23184 次
3 回答
74
更新
具有讽刺意味的是，在我发布上一个答案几周后，两位中国研究人员谢涛和冯登国发表了一个新的 MD5 单块碰撞。直到现在我才知道那篇论文。单个 MD5 块表示输入大小为 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 月发表：谢涛和刘凡宝和冯登国 - MD5 上的快速碰撞攻击
然而，如果你有更多的空间可以玩，几千字节的碰撞计算速度要快得多——在任何普通计算机上都可以在几小时内计算出来。
旧答案
之前最短的冲突使用了至少两个 MD5 块的输入——即 128 字节，1024 位。攻击者可以任意选择第一个块中的前缀，其余部分将被计算并显示为乱码。
这是两个不同碰撞输入的示例，您可以在 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 天时间，作者 Mark Stevens :)
于 2010-12-06T23:01:08.513 回答
10
生日悖论的数学使碰撞概率的拐点大致在 sqrt(N) 附近，其中 N 是散列函数中不同 bin 的数量，所以对于 128 位散列，当你得到大约 64 位时，你是中等可能发生 1 次碰撞。所以我的猜测是对于完整的 8 字节字符串集，它有点可能发生冲突，而对于 9 字节字符串，它极有可能发生冲突。
编辑：这假设 MD5 哈希算法导致从输入字节串到接近“随机”的输出哈希的映射。（与在一组可能的散列中更均匀地分配字符串相比，在这种情况下它会更接近 16 个字节。）
同样对于更具体的数字答案，如果您查看计算碰撞概率的近似值之一，您会得到
p(k) ≈ 1 - e -k(k-1)/(2*2 128 )其中 k = 可能输入的空间大小 = 2 m其中输入字节串为 m 位长。
8 字节字符串的集合： p(2 64 ) ≈ 1 - e -0.5 ≈ 0.3935
9 字节字符串的集合： p(2 72 ) ≈ 1 - e -2 144 /(2*2 128 ) = 1 - e -2 15 = 1 - e -32768 ≈ 1
另请注意，这些假设是完整的 m/8 字节字符串集。如果只使用字母数字字符，则需要更多字节才能发生可能的冲突。
于 2010-01-04T14:55:23.030 回答
1
我怀疑是否有任何有用的长度不会发生碰撞。这些算法并没有真正用于该目的。它旨在尝试对数据的细微变化（如损坏的文件）保持唯一性，而不是在所有可能的数据集上保持唯一性。
于 2010-01-04T14:50:01.133 回答