在实践中忽略SHA冲突的可能性是否安全？ [英] Is it safe to ignore the possibility of SHA collisions in practice?

问题描述

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

• 文件数量


• 单个文件的大小

假设它为零，我们可以忽略这种可能性吗？这个通常的答案是这样的：一个流氓小行星在接下来的一秒内崩溃在地球上的可能性是什么，它消灭了文明 - 即 - 我们知道它，并杀死数十亿人？如果我们有一个完美的散列函数，其输出大小为，那么这个散列函数的实际结果可能并不是非常重要。

n ，并且我们有 p 消息散列（单个消息长度不重要），那么碰撞概率大约是

2 / 2 < （这是对小 p 有效的近似，即基本上小于<2> n / 2 SUP> 的）。例如，在SHA-256（ n = 256 ）和10亿条消息（ p = 10 <9> ）的情况下， > 4.3 * 10 ^-60 。

平均每3000万年发生一次大规模凶手太空摇滚。这导致在接下来的一秒内发生这种事件的可能性大约 10 <-15> 。这比SHA-256碰撞的可能性要强45个数量级。简单地说，如果你发现SHA-256冲突可怕，那么你的优先级是错误的。

在安全设置中，攻击者可以选择将被散列的消息，那么攻击者可能会使用大量超过10亿条消息;但是，你会发现攻击者的成功概率仍然很小。这是使用具有256位输出的散列函数的关键：所以碰撞风险可以忽略不计。

当然，以上所有假设SHA -256是一个完美的散列函数，这远远没有被证明。尽管如此，SHA-256似乎相当强大。

Let's say we have a billion unique images, one megabyte each. We calculate the SHA-256 hash for the contents of each file. The possibility of collision depends on:

• the number of files
• the size of the single file

How far can we go ignoring this possibility, assuming it is zero?

解决方案

The usual answer goes thus: what is the probability that a rogue asteroid crashes on Earth within the next second, obliterating civilization-as-we-know-it, and killing off a few billion people? It can be argued that any unlucky event with a probability lower than that is not actually very important.

If we have a "perfect" hash function with output size n, and we have p messages to hash (individual message length is not important), then probability of collision is about p²/2ⁿ⁺¹ (this is an approximation which is valid for "small" p, i.e. substantially smaller than 2^n/2). For instance, with SHA-256 (n=256) and one billion messages (p=10⁹) then the probability is about 4.3*10^-60.

A mass-murderer space rock happens about once every 30 million years on average. This leads to a probability of such an event occurring in the next second to about 10^-15. That's 45 orders of magnitude more probable than the SHA-256 collision. Briefly stated, if you find SHA-256 collisions scary then your priorities are wrong.

In a security setup, where an attacker gets to choose the messages which will be hashed, then the attacker may use substantially more than a billion messages; however, you will find that the attacker's success probability will still be vanishingly small. That's the whole point of using a hash function with a 256-bit output: so that risks of collision can be neglected.

Of course, all of the above assumes that SHA-256 is a "perfect" hash function, which is far from being proven. Still, SHA-256 seems quite robust.

这篇关于在实践中忽略SHA冲突的可能性是否安全？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！