# Why haven't any SHA-256 collisions been found yet?

I've been thinking about this for a few days, a SHA-256 algorithm outputs 64 characters which can either be a lowercase letter or a number from 0-9. Which should mean that there are 64^36 distinct SHA-256 results.

How has a collision never been found? If I decide to find the hash for a random input of increasing length I should find a collision eventually, even if it takes years. I imagine this can also be done where the input is a large file and you just change one byte and calculate the hashes until you find a collision. Why hasn't' this happened?

• The human brain is exceptionally bad at imagining large numbers. This reminds me of a question for a list of all 1024 bit prime numbers. Anyway: Hexadecimal output is not all lowercase letters. And that is just one way to express all $2^{256}$ possible outputs (and the actual number format is entirely irrelevant, just computers tend to use hexadecimal often). And then it would be $36^{64}$, not $64^{36}$ - which is vastly different. – tylo May 29 '17 at 17:26
• @Swailem95 Hex only uses 6 letters, so there are 16 different characters, not 36. Also you're confusing base and exponent. The size of the alphabet goes into the base, the length into the exponent. So you get $2^{256}$ looking at the bit representation, $256^{32}$ looking at the byte representation or $16^{64}$ looking at the hex representation. – CodesInChaos May 29 '17 at 19:27
• Consider that Eddington's number =136 * $2^{256} \approx 10^{80}$. Now, Eddington's number purports (see Wiki for assumptions - hint - huge) to be the number of fundamental particles (protons + electrons, assuming that a neutron is made up of a proton and an electron)) in the universe. So, you'd basically only have 2 * 136 (= 272) particles per SHA-256 hash to be available to store your data for a collision (+ overhead)? I put in the 2 for a 50% change of a clash - is my maths OK? – Vérace Oct 12 '18 at 19:45
• @Vérace your maths isn't quite right. The birthday paradox (as per the answer) states that you only need $2^{128}$ hashes for a 50% chance of a collision. So you would have $136 * 2^{128}$ particles to store each hash. Of course this is still wildly impractical! – Paul Wagland May 16 '19 at 14:49
• "Why haven't any SHA-256 collisions been found yet" Collisions have been found – Scott May 13 at 16:05

I think you underestimate just how large $2^{256} \gg 64^{36}$ is.

How has a collision never been found?

It will take a very, very, very, $\text{very}^{\text{very}}$ long time to find one. For comparison, as of January 2015, Bitcoin was computing 300 quadrillion SHA-256 hashes per second. That's $300 \times 10^{15}$ hashes per second.

Let's say you were trying to perform a collision attack and would "only" need to calculate $2^{128}$ hashes. At the rate Bitcoin is going, it would take them

$2^{128} / (300 \times 10^{15} \cdot 86400 \cdot 365.25) \approx 3.6 \times 10^{13}$ years. In comparison, our universe is only about $13.7 \times 10^9$ years old. Brute-force guessing is not a practical option.

• So, given ~2600 universe-lifespans, all the bitcoin miners together would have a good shot at finding data that shares a given SHA-256 hash? Am I interpreting+calculating that right? – JamesTheAwesomeDude Jul 24 '17 at 18:38
• @JamesTheAwesomeDude During that time all the bitcoin miners would have a good chance that the two hashes that were calculated had the same hash. You would still have to find which two hashes these were. By "a given SHA-256 hash" I believe you mean Second Preimage Attack which cannot rely on birthday paradox. – desowin Oct 5 '17 at 10:22
• So, in 2600 universe-lifespans, we would have a chance of finding a collision, but only if we saved/recorded/stored every single hash discarded by all the bitcoin miners in the world, and, even then, it would just be two random block+nonce files with the same hash? – JamesTheAwesomeDude Oct 12 '17 at 15:37
• galvatron: for your formula I get 3.59e13 (not e33). Also each bitcoin hash is two (albeit constrained) SHA256. @James: your link divides by 1.37e9 and gives 26,254, but dividing by the correct 13.7e9 does give 2,625 like your text. Both: in Oct '17 bitcoin is up to 10e18x2/s thus 5.4e11 years or 39 universes. Plus, as you say, storing and comparing. – dave_thompson_085 Oct 19 '17 at 2:50
• Yeesh. I must've gotten too excited typing 3.33. That's a lot fewer universe. Thanks. – user47922 Oct 19 '17 at 16:28