哈希冲突的概率

Question

我正在寻找一些关于基于生日悖论的 MD5、SHA1 和 SHA256 碰撞可能性的精确数学。

我正在寻找类似图表，上面写着“如果你有 10^8 个键，这是概率。如果你有 10^13 个键，这就是概率等等”

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

Answer 1

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

生日悖论明确指出，一旦你看到大约 ?(2k) 个项目，就有 50% 的机会发生碰撞，其中 k 是不同的可能输出的数量。在散列函数散列到 n 位输出的情况下，这意味着在发生冲突之前您将需要大约 2 ^{n/2 个}散列。这就是为什么我们通常选择输出 256 位的散列；这意味着我们需要对 2 ¹²⁸ ?10 ^{38 个}项目进行散列处理，然后才有“合理”的碰撞机会。随着512位散列，你需要大约2 ²⁵⁶获得碰撞的机率为50％，而2 ²⁵⁶是大约在已知的宇宙质子数。

与 n 位散列函数和散列的 k 个字符串发生冲突的概率的确切公式是

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

这是一个相当棘手的数量，直接使用，但我们可以使用表达式得到这个数量的近似值

1 - e ^{-k 2 /2 n+1}

因此，为了获得（大致）碰撞概率 p 的机会，我们可以求解得到

? 1 - e ^{-k 2 /2 n+1}

1-p ? e ^{-k 2 /2 n+1}

ln(1 - p) ? -k ² /2 ⁿ⁺¹

-ln(1 - p) ? k ² /2 ⁿ⁺¹

-2 ⁿ⁺¹ ln(1 - p) ? ķ ²

2 ^(n+1)/2 ?(-ln(1 - p)) ? 克

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

? 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 ^153.5。

所以，你需要一个惊人庞大的哈希数有察觉得到一个碰撞的可能性很小。图 2 ^153.5大约是 10 ⁴⁵，计算每个散列一纳秒将花费比计算宇宙长度更长的时间。毕竟，你会得到 2 ^-50的成功概率，大约是 10 ^-15。

事实上，这正是我们为哈希选择如此大量位的原因！这使得偶然发生碰撞的可能性极小。

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

希望这可以帮助！