268

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?

9
  • 2
    It depends on what you are using the hash keys for. If it's some kind of file identification, then a collision may as well mean the files are identical and thus you need to compare the files too in cases of collision. I'd say it would be fairly safe to just compare the file sizes.
    – mojuba
    Oct 25, 2010 at 11:37
  • Yes, in this case, if you compare file sizes, the possibility drastically decreases. You can also use two hashing algorithms and concatenate the results. Then, the possibility of a collision of both at the same time decreases more. But, the question is, how much is "fairly" safe? Maybe we need a formula and numbers. Oct 25, 2010 at 12:11
  • 2
    @Hristo Hristov: if we assume that the hash key is a pseudo random number (which theoretically is correct) then one billion of 128-bit keys gives a collision probability of 2.9 * 10^-30. You can't even call it "miniscule", it's less than that ;)
    – mojuba
    Oct 25, 2010 at 12:24
  • 4
    @mojuba: even better, he's asking about a 256-bit hash. Oct 25, 2010 at 12:25
  • FWIW: the GIT version control system identifies files by their content SHA.
    – snemarch
    Oct 25, 2010 at 12:55

3 Answers 3

516

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 p2/2n+1 (this is an approximation which is valid for "small" p, i.e. substantially smaller than 2n/2). For instance, with SHA-256 (n=256) and one billion messages (p=109) 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.

17
  • 19
    This is a very good answer, thanks! But, if in case of collision a nuclear power plant will explode, and it depends on you, will you take that risk? If you are completely right, then we can take the risk, because it is 45 orders of magnitude more probable the civilization to be destroyed. Right? Oct 25, 2010 at 13:13
  • 60
    @Hristo I think yes, one would take that risk. A nuclear power plant already has a far higher chance of exploding due to other things, like mechanical failure, human error in building it or operator error while running it, and we are already taking those chances. If SHA-256 collisions were the only things causing nuclear incidents we would almost certainly have had exactly zero of them so far. Dec 14, 2010 at 20:07
  • 46
    foxnews.com/science/2013/02/11/… I'd start thinking about SHA512. Feb 12, 2013 at 16:29
  • 62
    I can now rest easy knowing that I'll likely be wiped out by an asteroid long before I live to experience an SHA-256 collision.
    – AaronLS
    Aug 12, 2013 at 18:02
  • 15
    Sorry, you are missing on the so-called "birthday paradox". Have a better look at the "nice table", it does not work the way you think. For the figures I give, in that table, it would be a value "10^9" in a column labelled "4.3*10^-60" and row "128 bits" (but the table does not go below 10^-18). Mar 11, 2014 at 21:34
62

The possibility of a collision does not depend on the size of the files, only on their number.

This is an example of the birthday paradox. The Wikipedia page gives an estimate of the likelihood of a collision. If you run the numbers, you'll see that all harddisks ever produced on Earth can't hold enough 1MB files to get a likelihood of a collision of even 0.01% for SHA-256.

Basically, you can simply ignore the possibility.

Edit: if (some of) the files are potentially provided or manipulated by an adversary who could profit from provoking a collision, then the above of course only holds true as long as the hash algorithm is cryptographically strong without any known attacks.

9
  • 8
    I can't agree with the conclusion. Yes, no hardisks can store that number of files, but you IMO misinterpret the situation. It only takes two files to produce a collision. Although the possibility is very low it still can happen.
    – sharptooth
    Oct 25, 2010 at 12:00
  • 19
    @sharptooth: no, I'm not misrepresenting the situation. The possibility of you and everyone you know dying from a road accident on the same day is very low, but it still can happen (and it is much higher than that of an SHA-256 collision). Yet you are ignoring that possibility. Oct 25, 2010 at 12:18
  • 12
    @sharptooth: I was talking about separate, simultaneous road accidents of a few hundred specific people. You can't really take any stepts to make that lower. It would be pointless, as it's already bizarrely low. But still so much more likely than an SHA-256 collision that you can't even imagine how much. It's the same argument as Thomas made. Oct 25, 2010 at 12:31
  • 18
    @sharptooth: No, the chances do not grow significantly, because the number is still absolutely dwarfed by the size of the SHA-256 hash space. This is the one thing you're not taking into account properly - all the factors have to be weighted by their actual magnitude, not equally. If you generated one billion hashes per second for every single person on Earth, and did that for one thousand years, you'd still have less than 1% chance of a collision. Oct 27, 2010 at 12:24
  • 5
    If you don't check for the possibility of an uncorrected error on every fetch from memory or read from disk (which have a far higher probability than an SHA-256 collision), you may not fully understand probabilities.
    – Christophe
    Oct 24, 2015 at 18:46
27

First of all, it is not zero, but very close to zero.

The key question is what happens if a collision actually occurs? If the answer is "a nuclear power plant will explode" then you likely shouldn't ignore the collision possibility. In most cases the consequences are not that dire and so you can ignore the collision possibility.

Also don't forget that you software (or a tiny part of it) might be deployed and simultaneously used in a gazillion of computers (some tiny embedded microcomputers that are almost everywhere nowadays included). In such case you need to multiply the estimate you've got by the largest possible number of copies.

8
  • ...not by the # of copies, but the # of datasets all copies digest. Jul 24, 2013 at 17:15
  • 5
    This is wrong, the number of copies of software running is irrelevant. The only thing that matters is the number of unique files that are processed and the birthday paradox is the math for the calculation. Sep 22, 2016 at 22:02
  • 2
    I heard someone else mention that the likelihood of hardware failure - i.e. a bit flipping somewhere due to radiation, etc - is more likely than a hash collision, and hence, worrying about the hash collision is silly. Personally, I'd try to cover both cases, to be safe (the more safety in a nuclear power plant the better), but hash collisions would be probably very low on the list of potential dangers (assuming the hash space is large enough). However, this all assumes that there is not some hidden behavior in the hash function which causes collisions more frequently. Oct 20, 2016 at 20:22
  • '0' has its area Feb 28, 2017 at 19:38
  • 1
    If the answer is "a nuclear power plant will explode" then you can still totally ignore the probability that a collision will happen. Even when it kills all of humanity in the next second, it can still be ignored; because that chance is unimaginably much smaller than that that actually happens due to a astroid (see the accepted answer).
    – Carlo Wood
    Feb 7, 2020 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.