给定一组长度相等的 100 个不同字符串，如何量化这些字符串的 SHA1 摘要碰撞的概率是不太可能发生的... ?
SHA1碰撞的概率
74
- eastafri
6
请澄清一下，如何拥有“长度不同但相等”的字符串？ - KevinDTimm
6“a”，“b”，“c”是长度相等但不同的字符串。 - Joe Phillips
我假设这些字符串至少有20个字节长。否则，显然碰撞的机会会更高。 :) - Anthony Mills
4@安东尼，为什么显而易见？我不知道那是否属实。 - Joe Phillips
3重新阅读后，这很清楚。 - KevinDTimm
1这与以下问题相关：https://sites.google.com/site/itstheshappening/ 至少发现了一次碰撞。 - Christophe De Troyer
3个回答
148
SHA-1生成的160位哈希值足够大，以确保每个数据块的指纹都是唯一的吗？ 假设随机哈希值具有均匀分布，有n个不同的数据块和一个生成b位哈希值的哈希函数，出现一个或多个冲突的概率p受限于数据块对数乘以给定数据块对冲突的概率。
- Peter
5
13总之，发生碰撞的可能性约为10^-45的数量级。这非常、非常不可能。 - Paul Lammertsma
4但是SHA-1并不是均匀分布，它可能会超过这个上限。我怀疑这个方程不正确，至少相等式不成立。 - Kamel
2这个答案没有考虑到2005年中国的发现，他们能够在2^69次迭代中产生碰撞，而不是 brute force 预计的2^80。https://www.schneier.com/blog/archives/2005/02/sha1_broken.html - Djarid
5重要的是不要混淆意外哈希碰撞和恶意碰撞攻击。前者是指两个项目的哈希值发生碰撞的概率，遵循上述公式（尽管如Kamel所述，分布并不完全均匀，因此概率可能更高）。后者是用于故意寻找碰撞的，依赖于发现和利用哈希中的弱点。密码哈希试图对抗这样的攻击，但通常对于更简单的哈希应用（不传输机密）来说，它们过于复杂了。 - Pierre D
当2^b >> n^2时，该公式是准确的（并且当2^b非常大时）。我知道对于sha1来说这在大多数情况下都是正确的...但为了记录！ - MrIo
7
好的，碰撞的概率将会是：
1 - ((2^160 - 1) / 2^160) * ((2^160 - 2) / 2^160) * ... * ((2^160 - 99) / 2^160)
可以想象一下，在10个空间中发生2个物品的碰撞的概率。第一个物品是独特的，概率为100%。第二个物品有9/10的概率是独特的。因此，两者都是独特的概率为100% * 90%，碰撞的概率为：
1 - (100% * 90%)，或1 - ((10 - 0) / 10) * ((10 - 1) / 10)，或1 - ((10 - 1) / 10)
这是相当不可能的。你需要更多的字符串才能使其成为遥远的可能性。
看一下维基百科上这个页面上的表格；只需在128位和256位之间的行之间进行插值即可。
1 - ((2^160 - 1) / 2^160) * ((2^160 - 2) / 2^160) * ... * ((2^160 - 99) / 2^160)
可以想象一下，在10个空间中发生2个物品的碰撞的概率。第一个物品是独特的，概率为100%。第二个物品有9/10的概率是独特的。因此，两者都是独特的概率为100% * 90%，碰撞的概率为：
1 - (100% * 90%)，或1 - ((10 - 0) / 10) * ((10 - 1) / 10)，或1 - ((10 - 1) / 10)
这是相当不可能的。你需要更多的字符串才能使其成为遥远的可能性。
看一下维基百科上这个页面上的表格；只需在128位和256位之间的行之间进行插值即可。
- Anthony Mills
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接