在实践中忽略 SHA 冲突的可能性是否安全？

Question

假设我们有十亿张独特的图像，每张一兆字节。 我们计算每个文件内容的 SHA-256 哈希值。 碰撞的可能性取决于：

• 文件数量
• 单个文件的大小

假设这种可能性为零，我们可以在多大程度上忽略这种可能性？

Answer 1

通常的答案是这样的：一颗流氓小行星在下一秒内撞击地球、摧毁我们所知的文明并杀死数十亿人的概率有多大？可以说，任何低于这个概率的不幸事件实际上都不是很重要。

如果我们有一个输出大小为 n 的“完美”哈希函数，并且我们有 p 条消息要进行哈希处理（单个消息长度并不重要），那么冲突概率约为 p²/2^{n +1}（这是对“小”p有效的近似值，即远小于2^n/2）。例如，对于 SHA-256 (n=256) 和 10 亿条消息 (p=10⁹)，则概率约为 4.3*10^-60。

平均每 3000 万年就会发生一次大规模杀人太空岩石。这导致下一秒发生此类事件的概率约为 10^-15。这比 SHA-256 碰撞的可能性高 45 个数量级。简而言之，如果您发现 SHA-256 冲突很可怕，那么您的优先级就错了。

在安全设置中，攻击者可以选择要进行哈希处理的消息，那么攻击者可能会使用超过十亿条消息；然而，你会发现攻击者的成功概率仍然微乎其微。这就是使用具有 256 位输出的哈希函数的全部意义：这样就可以忽略冲突的风险。

当然，以上所有内容都假设 SHA-256 是一个“完美”的哈希函数，这还远未得到证明。不过，SHA-256 看起来相当稳健。

Answer 2

冲突的可能性不取决于文件的大小，只取决于文件的数量。

这是生日悖论的一个例子。维基百科页面给出了碰撞可能性的估计。如果您运行这些数字，您会发现地球上生产的所有硬盘都无法容纳足够的 1MB 文件，以至于 SHA-256 发生冲突的可能性甚至只有 0.01%。

基本上，你可以忽略这种可能性。

编辑：如果（某些）文件可能由可以从引发冲突中获利的对手提供或操纵，那么上述内容当然仅在散列算法具有强大的加密性且没有任何已知攻击的情况下才成立。

Answer 3

首先，它不是零，而是非常接近于零。

关键问题是如果真的发生碰撞会发生什么？如果答案是“核电站会爆炸”，那么您可能不应该忽视碰撞的可能性。在大多数情况下，后果并不那么可怕，因此您可以忽略碰撞的可能性。

也不要忘记，您的软件（或其一小部分）可能会在无数计算机（包括当今几乎无处不在的一些小型嵌入式微型计算机）中部署并同时使用。在这种情况下，您需要将您得到的估计值乘以最大可能的副本数。