19

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.

fgrieu
  • 131,696
  • 12
  • 284
  • 553
Ari Sweedler
  • 303
  • 1
  • 2
  • 7
  • Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/77304/discussion-on-question-by-ari-sweedler-are-there-any-well-known-examples-of-sha). – e-sushi May 10 '18 at 12:14

1 Answers1

18

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.

fgrieu
  • 131,696
  • 12
  • 284
  • 553
  • 2
    Maybe I'm misunderstanding your answer, but why would you assume that all hashes ever computed by Bitcoin miners have been checked for collisions? – mitchus Aug 05 '19 at 14:09
  • 4
    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. – Jon Strayer Oct 04 '19 at 19:43
  • 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. – hmijail Sep 20 '21 at 00:06
  • @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. – JamesTheAwesomeDude Sep 16 '22 at 19:54
  • 1
    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 . – JamesTheAwesomeDude Sep 16 '22 at 19:59
  • @JamesTheAwesomeDude not sure how what you wrote relates, much less negates, to my comment - or the answer. Maybe you wanted to tag someone else? – hmijail Sep 18 '22 at 20:05