76
$\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$
6
  • 30
    $\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
  • 21
    $\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$ 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$ May 16 '19 at 14:49
  • $\begingroup$ "Why haven't any SHA-256 collisions been found yet" Collisions have been found $\endgroup$
    – Him
    May 13 '20 at 16:05
109
$\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$
7
  • 9
    $\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$ Jul 24 '17 at 18:38
  • 11
    $\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
  • 8
    $\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$ Oct 12 '17 at 15:37
  • 7
    $\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$ Oct 19 '17 at 2:50
  • 4
    $\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
-1
$\begingroup$

This is a comment more than answer 1-There is a slight divide mistake in the given answer ... the number ~3.6•10¹³ is on days, ie before dividing by 365.25. When we divide by 365.25 it becomes ~10¹¹ yrs (I approximate 2¹⁰=1024~10³, so 2¹²⁸~256•10³⁶ 256•10³⁶/[3•10²•10¹⁵•864•10²] ~256•10¹⁷/(3•864) ~10¹⁶ days ~3•10¹³ years)

»»»»»Apologies I am the wrong one here

2-These numbers has changed from 2017 till now https://www.blockchain.com/charts/hash-rate https://ycharts.com/indicators/bitcoin_network_hash_rate#:~:text=Basic%20Info,9.82%25%20from%20one%20year%20ago. The previously 300*10¹⁵ is now 121.88•10⁶•10¹²= 121.88•10¹⁸

3-The resulting number being down by ~10³ ie ~3•10¹⁰ yrs still safe ofcourse, but I think the risk could come from analytical attacks too, Differential attacks I mean (I've always been impressed by their old S-boxes story with DES)

4-I just found this paper today (while editing the answer) but I have no access to it's full version https://dl.acm.org/doi/abs/10.1145/3409501.3409513

-What if someone like entering previously hashed data as a learning/training set into an AI system for example??? In fact the AI thought just crossed my mind in this very moment. (If we humans cannot analyze some patterns, doesn't mean AI can't) enter image description here

5-From a new brute force paper HAL Id: hal-02306904 https://hal.archives-ouvertes.fr/hal-02306904v2 The actual computation was done on aging hardware. It required 7 calendar months using two obsolete second-hand bitcoin mining devices converted into “useful” computational devices. A second step required 570 CPU-years on an 8-year old IBM BlueGene/Q computer, a few weeks before it was scrapped. To the best of our knowledge, this is the first practical 128-bit collision-like result obtained by brute-force, and it is the first bitcoin miner-accelerated computation enter image description here

6-I think it maybe useful also to bring Justin Drake estimation to the discussion too, evaluating his words with the conflicts of interest in mind ofcourse (mins 29-32) https://podcasts.google.com/feed/aHR0cHM6Ly9icmVha2Rvd25zLmxpYnN5bi5jb20vcnNz/episode/ZjJkZGY1M2MtZjMzYy00N2M4LWFlNWItYzMxY2ZlYTk0ZDQ1?ep=14

Sorry if this kind of brainstorming more than an answer

$\endgroup$
2
  • $\begingroup$ No there's no mistake in the division; 2^128/300e15/86400 = 1.313e16 and 1.313e16/365.25 = 3.59e13. Although as I noted years ago bitcoin miners actually do two single-block SHA256 for each "hash" as measured by blockchain etc. And yes bitcoin capability has increased more. Machine learning works by finding patterns and a competently designed cryptohash like SHA256 has no patterns; search for avalanche criterion. PS: your numbers are garbled because you tried to use asterisk * in text, but Stack markdown uses that to indicate italics (or if doubled bold); see the help button in the editor. $\endgroup$ Jun 18 at 0:10
  • $\begingroup$ I very much apologize, I was the wrong one on the calculation. About SHA-256 not having patterns, that's for human analysis (uptil now, although I haven't read the full paper added in the modified answer); I don't think that guarantees that advanced AI techniques can't find any. $\endgroup$
    – ShAr
    Jun 18 at 2:49

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.