106
$\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$
7
  • 37
    $\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
  • $\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
  • $\begingroup$ "Why haven't any SHA-256 collisions been found yet" Collisions have been found $\endgroup$
    – Him
    May 13, 2020 at 16:05
  • 2
    $\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
139
$\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$
9
  • 11
    $\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
0
$\begingroup$

Well, it might be possible that a SHA-256 collision has happened by accident, but since it was by accident we don't know about it. It's possible that two or more inputs have been used to get the same output, but no one did it on purpose meaning no one ever realized. It's interesting to think about it like that.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Might be possible? Only in a very strictly technical sense. It's statistically impossible that a sha256 collision has happened by accident. $\endgroup$
    – James Roper
    Oct 26, 2023 at 1:58
  • $\begingroup$ It is a lot more possible that the same hash has been calculated twice from different data than the second key actually being found. $\endgroup$
    – gnasher729
    Mar 20 at 20:19
-2
$\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$
3
  • $\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
  • $\begingroup$ @ShAr That's not how AI works. Cryptography involves methodically proving that the patterns do not exist, so the lack of pattern is by design, not an accident. It's like saying something designed to be water-proof can somehow be discovered that it isn't... if that happens, then someone screwed up. It's not something to be "discovered" like this. $\endgroup$
    – Nelson
    Dec 6, 2023 at 0:50

Your Answer

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

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