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

Question

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

Hri*_*tov 197 hash sha

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

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

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

Answer 1

Tho*_*nin 362

通常的答案是这样的:一个流氓小行星在下一秒内在地球上坠毁的概率是多少,消灭了我们所知道的文明,杀死了几十亿人？可以说,任何概率低于该事件的不幸事件实际上都不是非常重要.

如果我们有与输出尺寸的"完美"的散列函数Ñ,我们有p消息进行散列(单独的消息长度是不重要的),则碰撞的可能性为大约p ² /2 ^{n + 1个}(这是一个近似值,其是对"小" p有效,即基本上小于2 ^n/2).例如,使用SHA-256(n = 256)和十亿条消息(p = 10 ⁹),则概率约为4.3*10 ^-60.

大规模杀人犯太空岩石平均每3000万年发生一次.这导致这种事件在下一秒发生的概率大约为^10-15.这比SHA-256碰撞的可能性高45个数量级.简而言之,如果您发现SHA-256碰撞可怕,那么您的优先级是错误的.

在安全设置中,攻击者可以选择要进行哈希处理的消息,然后攻击者可能会使用超过10亿条消息; 但是,你会发现攻击者的成功概率仍然很小.这是使用具有256位输出的散列函数的全部要点:因此可以忽略碰撞的风险.

当然,以上所有假设SHA-256都是一个"完美"的哈希函数,这远未得到证实.不过,SHA-256似乎相当强大.

@Hristo我想是的,人们会冒这个风险.由于机械故障,建造中的人为错误或运行中的操作员错误,核电厂已经具有甚至更高的爆炸机会,我们已经抓住了这些机会.如果SHA-256碰撞是导致核事故的唯一因素,那么到目前为止我们几乎肯定已经完成了零事故. (45认同)
我现在可以轻松地知道,在我遇到SHA-256碰撞之前,我很可能会被一颗小行星摧毁. (35认同)
http://www.foxnews.com/science/2013/02/11/150-foot-asteroid-has-close-encounter-with-earth-this-week/我开始考虑SHA512. (25认同)
这是一个非常好的答案,谢谢!但是,如果发生碰撞,核电站会爆炸,而且取决于你,你会冒这个风险吗？如果你是完全正确的,那么我们就可以承担风险,因为它的文明被破坏的可能性要高出45个数量级.对？ (10认同)
对不起,_you_在所谓的"生日悖论"中失踪了.更好地看看"漂亮的桌子",它不会像你想象的那样工作.对于我给出的数字,在该表中,在标有"4.3*10 ^ -60"和行"128位"的列中它将是值"10 ^ 9"(但表格不低于10 ^ -18 ). (9认同)
这写得很好，但它错了（可以这么说，差了几个数量级）。你错过了生日悖论的含义。关于它的维基百科文章有一个很好的表格来检查机会：http://en.wikipedia.org/wiki/Birthday_attack (2认同)
既然 NASA 已经成功执行了 DART 任务，有人可以对这次碰撞事件发表评论吗？这是否会增加或减少哈希冲突的可能性？我只是一个卑微的软件开发人员，不懂天体物理学和生日。 (2认同)

Answer 2

Mic*_*rdt 47

碰撞的可能性不取决于文件的大小,只取决于它们的数量.

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

基本上,你可以简单地忽略这种可能性.

@sharptooth:不,有机会*不会*显着增长,因为这个数字仍然与SHA-256哈希空间的大小相比相形见绌.这是你没有正确考虑的一件事 - 所有因素都必须按实际幅度加权,而不是平等.如果你为地球上的每个人每秒产生10亿个哈希值,并且这样做了一千年,你仍然有不到1%的碰撞几率. (12认同)
@sharptooth:不,我不是在歪曲事实.你和你认识的每个人在同一天因交通事故死亡的可能性非常低,但它仍然可能发生(并且它远远高于SHA-256碰撞的可能性).但你忽略了这种可能性. (11认同)
@sharptooth:我在谈论*单独的*,几百个特定人的同时发生的道路交通事故.你不能真正采取任何措施来降低这一点.这将是毫无意义的,因为它已经奇怪的低.但仍然比SHA-256碰撞更可能,你甚至无法想象多少.这与托马斯提出的论点相同. (11认同)
我不能同意这个结论.是的,没有硬盘可以存储这么多的文件,但你IMO误解了这种情况.它只需要两个文件就可以产生碰撞.虽然可能性非常低,但仍然可能发生. (5认同)
如果您没有检查每次从内存中获取或从磁盘读取时出现未校正错误的可能性(其远比SHA-256碰撞的概率高很多),您可能无法完全理解概率. (3认同)

Answer 3

sha*_*oth 17

首先,它不是零,而是非常接近于零.

关键问题是如果实际发生碰撞会发生什么？如果答案是"核电站将爆炸",那么你可能不应该忽视碰撞的可能性.在大多数情况下,后果并不严重,因此您可以忽略碰撞的可能性.

也不要忘记,你的软件(或它的一小部分)可能会被部署,同时在计算机的使用极大数(一些微小的嵌入式微型计算机被几乎无处不在时下含税).在这种情况下,您需要将您获得的估计值乘以最大可能的副本数.

这是错误的，运行的软件副本数量无关紧要。唯一重要的是处理的唯一文件的数量，生日悖论是计算的数学。 (3认同)
我听到其他人提到硬件故障的可能性 - 即由于辐射等原因在某处有点翻转 - 比散列冲突更有可能，因此，担心散列冲突是愚蠢的。就我个人而言，为了安全起见，我会尝试涵盖这两种情况（核电站越安全越好），但哈希冲突在潜在危险列表中可能非常低（假设哈希空间足够大） . 然而，这一切都假设散列函数中没有一些隐藏的行为会更频繁地导致冲突。 (2认同)

归档时间：	15 年，6 月前
查看次数：	66488 次
最近记录：	8 年，11 月前