哈希碰撞的概率

Question

哈希碰撞的概率

mathhashprobabilityshabirthday-paradox

25

我正在寻找一些关于MD5、SHA1和SHA256碰撞概率的精确数学数据，基于生日悖论。

我需要像这样的一个图表：“如果你有10^8个密钥，这是概率。如果你有10^13个密钥，这是概率等等。”

我查看了大量文章，但很难找到给我这些数据的文章。（对我来说最理想的选项是提供任何哈希大小的公式或代码来计算此数据）

- Dark Nebula

为什么？例如，对于MD5（和SHA-1在某种程度上），它严重依赖于您的输入是什么。MD5已知有碰撞攻击，因此如果恶意用户控制哈希算法的输入的一部分，则会显着影响碰撞的可能性。对于理论下限，完美的哈希算法应该与完美的随机数生成器没有任何区别。 - Joachim Sauer

主要只是出于好奇。我应该澄清一下，我正在寻找基于关键字大小（如128位、160位和256位等）的完美哈希碰撞概率的理论值。 - Dark Nebula

这些都在维基百科上有详细介绍，分别是生日悖论问题和生日攻击。 - President James K. Polk

@DarkNebula，是的，这是一个重要的澄清，从数学角度来看，这是一个更容易的问题。 - Joachim Sauer

2

我邀请你在bdayprob.com上尝试我的计算器，它可以输入以log2为底的对数。例如，要测试在SHA256中使用10^8 ≈ (2^(3.36))^8 = 2^(26.56) < 2^(27)个密钥发生冲突的可能性，只需解出N=2^(27)和D=2^(256)的P即可。您将发现风险是可以忽略的，几乎为0％。采用不同方法尝试解决方案，所有方法均可在维基百科文章中找到。如果您觉得有用，请告诉我 :) - fast-reflexes

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

假设我们有一个真正随机的哈希函数，可以将字符串哈希为n位数字。这意味着有2ⁿ种可能的哈希码，并且每个字符串的哈希码都从所有这些可能性中均匀随机选择。

生日悖论特别指出，一旦你看到大约√(2k)个项目，就有50%的碰撞几率，其中k是可能输出的不同数量。在哈希函数哈希到n位输出的情况下，这意味着你需要大约2^n/2次哈希才能获得碰撞。这就是为什么我们通常选择输出256位哈希的原因；这意味着我们需要惊人的2¹²⁸ ≈10³⁸个已哈希的项，才有“合理”的碰撞几率。对于512位哈希，您需要大约2²⁵⁶次哈希才能获得50%的碰撞几率，而2²⁵⁶大约等于已知宇宙中质子的数量。

使用n位哈希函数和k个字符串哈希获取碰撞的概率的确切公式为

1 - 2ⁿ! / (2^kn (2ⁿ - k)!)

这是一个相当棘手的量，但我们可以使用表达式

1 - e^{-k²/2ⁿ⁺¹} 得出此数量的相当近似值。

因此，要获得（大约）概率p的碰撞几率，我们可以解决以下问题 p ≈ 1 - e^{-k²/2ⁿ⁺¹} 1 - p ≈ e^{-k²/2ⁿ⁺¹} ln(1 - p) ≈ -k²/2ⁿ⁺¹ -ln(1 - p) ≈ k²/2ⁿ⁺¹ -2ⁿ⁺¹ ln(1 - p) ≈ k² 2^(n+1)/2 √(-ln(1 - p)) ≈ k

作为最后一次近似，假设我们正在处理非常小的p选择。然后ln(1 - p) ≈ -p，因此我们可以将其重写为

k ≈ 2^(n+1)/2 √p 请注意，这里仍然有一个巨大的2^(n+1)/2项，因此对于一个256位的哈希函数，该前导项为2^128.5，这是非常巨大的。例如，我们必须看多少个项目才能获得256位哈希函数发生2^-50碰撞的机会？那将是大约

2^(256+1)/2 √2^-50

= 2^257/2 2^-50/2

= 2^207/2

= 2^103.5.

因此，你需要大量的哈希来获得微小的碰撞几率。请注意，2^103.5约为10³¹，如果每个哈希计算需要1纳秒，那么你需要的时间比宇宙的寿命还要长。即使经过所有这些，你也只能获得2^-50的成功概率，约为10^-15。

事实上，这正是我们选择如此大的位数用于哈希函数的原因！这使得碰撞发生的机会极其不可能。

（请注意，我们今天拥有的哈希函数实际上并不是真正的随机函数，这就是为什么人们建议不要使用MD5、SHA1和其他已经暴露出安全漏洞的函数。）

希望这能帮到你！