22
$\begingroup$

The popularity of SHA-256 as a hashing algorithm, along with the fact that it has 2256 buckets to choose from leads me to believe that collisions do exist but are quite rare.

Are there any well-documented SHA-256 collisions? Or any well-known collisions at all? I am curious to know.

I find that showing collisions to people I'm explaining hashing to is a great way to show them what non-invertibility means when they have a hard time seeing how the modulo_x operation relates to the SHA-256 operation.

Improve this question
$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – e-sushi
    May 10, 2018 at 12:14

1 Answer 1

Reset to default
21
$\begingroup$

No, there is not any known SHA-256 collision. Publication of one, or of a remotely feasible method to obtain one, would be considered major.

It is next to impossible that two distinct strings with the same SHA-256 have been computed so far. The most visible such computation is in bitcoin mining. By summing this data giving history of SHA256d hash rate (that's two SHA-256), I get that by end of April 2018 that had made 289.7 SHA-256, with the exponent growing roughly by 2 per year for the last few years. My computations, and opinion that they represent the bulk of SHA-256 made, have not been challenged there. Extending to 291 to account for other cryptocurrencies and (perhaps coverts) password search activity, odds are about 1 against 2256+1-91-91 = 275 that a collision occurred (see Birthday problem for cryptographic hashing).

For the purpose of illustrating collisions, perhaps make an example with SHA-256 restricted to its first 64 bits (16 hexadecimal characters instead of 64), and explain that each 2 bits added doubles the expected number of hashes before a collision occurs.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ Maybe I'm misunderstanding your answer, but why would you assume that all hashes ever computed by Bitcoin miners have been checked for collisions? $\endgroup$
    – mitchus
    Aug 5, 2019 at 14:09
  • 4
    $\begingroup$ He didn't assume they were compared. He gave you an estimate the odds of finding a collision if ALL the SHA256s ever generated were compared. If you take that estimate and assume we could generate all those hashes in one second, it would take roughly a billion years to generate one collision. $\endgroup$
    – Jon Strayer
    Oct 4, 2019 at 19:43
  • $\begingroup$ My understanding is that the writer did assume that those 2^91 hashes never caused a collision, which is the thing needing to be backed up. You could imagine the same argument being made for MD5 being used N times for file sharing in the 00's, and from there deducing that it'd take billions of years to get a collision - and you'd be wrong. $\endgroup$
    – hmijail
    Sep 20, 2021 at 0:06
  • 1
    $\begingroup$ @hmijail MD5 had collision attacks completed against it in 2004. These "one in a zillion" odds everyone's throwing around in this thread are, in fact assuming that no successful attack against SHA-256 has occurred—but that's intentional, as we can use Bayes' theorem to run the argument backwards upon seeing any SHA-256 collision, to deduce with near 100% probability that the assumption no longer holds and an attack is the cause of the collision. It won't collide if no attacks succeed; if it collides, therefore, an attack almost certainly did succeed. $\endgroup$
    – JamesTheAwesomeDude
    Sep 16, 2022 at 19:54
  • 1
    $\begingroup$ And, yes, the calculations also assume that the vast majority of Bitcoin ASIC rigs are optimized for, y'know, getting as many hashes done as possible, rather than conspiring to implement unreleased collision attacks in a scheme that's remained completely secret from the public through today 😉. $\endgroup$
    – JamesTheAwesomeDude
    Sep 16, 2022 at 19:59

Your Answer

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

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