99
$\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?

Improve this question
$\endgroup$
6
  • 35
    $\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, 2017 at 17:26
  • 24
    $\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, 2017 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, 2018 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, 2019 at 14:49
  • 1
    $\begingroup$ @Him These collissions where found in 24step Sha256, but the real Sha256 uses 64 rounds, so the collisions have been found in a very crippled variant. $\endgroup$
    – Daniel
    Nov 20, 2020 at 19:52

3 Answers 3

Reset to default
132
$\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.

Improve this answer
$\endgroup$
8
  • 10
    $\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, 2017 at 18:38
  • 13
    $\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, 2017 at 10:22
  • 10
    $\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, 2017 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$
    – dave_thompson_085
    Oct 19, 2017 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, 2017 at 16:28
1
$\begingroup$

Well It might be possible that a sha256 collision has happend on accident, but since it was on accident we dont know about it. Its possible that 2 or more inputs have been used to get same output but no one did it on porpuse meaning no one really realizes. Its interesting to think about it like that

Improve this answer
$\endgroup$
0
$\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

Improve this 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$
    – dave_thompson_085
    Jun 18, 2021 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, 2021 at 2:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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