38
$\begingroup$

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?

$\endgroup$
  • 20
    $\begingroup$ 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. $\endgroup$ – tylo May 29 '17 at 17:26
  • 14
    $\begingroup$ @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. $\endgroup$ – CodesInChaos May 29 '17 at 19:27
  • $\begingroup$ 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? $\endgroup$ – Vérace Oct 12 '18 at 19:45
  • $\begingroup$ @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! $\endgroup$ – Paul Wagland May 16 at 14:49
59
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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? $\endgroup$ – JamesTheAwesomeDude Jul 24 '17 at 18:38
  • 8
    $\begingroup$ @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. $\endgroup$ – desowin Oct 5 '17 at 10:22
  • 4
    $\begingroup$ 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? $\endgroup$ – JamesTheAwesomeDude Oct 12 '17 at 15:37
  • 5
    $\begingroup$ 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. $\endgroup$ – dave_thompson_085 Oct 19 '17 at 2:50
  • 2
    $\begingroup$ Yeesh. I must've gotten too excited typing 3.33. That's a lot fewer universe. Thanks. $\endgroup$ – user47922 Oct 19 '17 at 16:28

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.