10
$\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.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi May 10 '18 at 12:14
12
$\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.

$\endgroup$
  • 1
    $\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 at 14:09
  • 1
    $\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 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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