假设我们有十亿张不同的图片,每张1m。 我们计算每个文件内容的SHA-256哈希值。 碰撞的可能性取决于:

文件数量 单个文件的大小

假设它为零,忽略这种可能性我们能走多远?


当前回答

首先,它不是零,但非常接近于零。

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

此外,不要忘记您的软件(或其中的一小部分)可能被部署并同时用于无数台计算机(一些现在几乎无处不在的微型嵌入式计算机)。在这种情况下,你需要将估算结果乘以可能的最大拷贝数。

其他回答

首先,它不是零,但非常接近于零。

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

此外,不要忘记您的软件(或其中的一小部分)可能被部署并同时用于无数台计算机(一些现在几乎无处不在的微型嵌入式计算机)。在这种情况下,你需要将估算结果乘以可能的最大拷贝数。

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

这是生日悖论的一个例子。维基百科页面给出了碰撞可能性的估计。如果您运行这些数字,您将看到地球上生产的所有硬盘都无法存储足够的1MB文件,因此SHA-256发生碰撞的可能性甚至为0.01%。

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

编辑:如果(一些)文件可能是由对手提供或操纵的,他们可以从引发冲突中获利,那么当然,只要哈希算法在加密上是强大的,没有任何已知的攻击,上述情况才成立。

通常的答案是这样的:一颗流氓小行星在下一秒内撞击地球,毁灭我们所知的文明,杀死几十亿人的概率是多少?可以说,任何概率低于这个数字的不幸事件实际上都不是很重要。

如果我们有一个输出大小为n的“完美”哈希函数,并且我们有p条消息要哈希(单个消息长度不重要),那么碰撞概率大约是p2/2n+1(这是一个对“小”p有效的近似,即大大小于2n/2)。例如,对于SHA-256 (n=256)和10亿条消息(p=109),那么概率大约是4.3*10-60。

太空陨石平均每3000万年就会发生一次大爆炸。这导致下一秒发生此类事件的概率约为10-15。这比SHA-256碰撞的可能性高45个数量级。简单地说,如果你觉得SHA-256碰撞很可怕,那么你的优先级就错了。

在安全设置中,攻击者可以选择将被散列的消息,那么攻击者可能会使用超过10亿条消息;然而,您会发现攻击者的成功概率仍然是微乎其微的。这就是使用256位输出的哈希函数的全部意义:这样就可以忽略碰撞的风险。

当然,上面所有的假设都是SHA-256是一个“完美的”哈希函数,这还远远没有被证明。不过,SHA-256似乎相当健壮。