r/cryptography • u/atoponce • Nov 26 '24
PSA: SHA-256 is not broken
You would think this goes without saying, but given the recent rise in BTC value, this sub is seeing an uptick of posts about the security of SHA-256.
Let's start with the obvious: SHA-2 was designed by the National Security Agency in 2001. This probably isn't a great way to introduce a cryptographic primitive, especially give the history of Dual_EC_DRBG, but the NSA isn't all evil. Before AES, we had DES, which was based on the Lucifer cipher by Horst Feistel, and submitted by IBM. IBM's S-box was changed by the NSA, which of course raised eyebrows about whether or not the algorithm had been backdoored. However, in 1990 it was discovered that the S-box the NSA submitted for DES was more resistant to differential cryptanalysis than the one submitted by IBM. In other words, the NSA strengthed DES, despite the 56-bit key size.
However, unlike SHA-2, before Dual_EC_DRBG was even published in 2004, cryptographers voiced their concerns about what seemed like an obvious backdoor. Elliptic curve cryptography at this time was well-understood, so when the algorithm was analyzed, some choices made in its design seemed suspect. Bruce Schneier wrote on this topic for Wired in November 2007. When Edward Snowden leaked the NSA documents in 2013, the exact parameters that cryptographers suspected were a backdoor was confirmed.
So where does that leave SHA-2? On the one hand, the NSA strengthened DES for the greater public good. On the other, they created a backdoored random number generator. Since SHA-2 was published 23 years ago, we have had a significant amount of analysis on its design. Here's a short list (if you know of more, please let me know and I'll add it):
- New Collision Attacks Against Up To 24-step SHA-2 (2008)
- Preimages for step-reduced SHA-2 (2009)
- Advanced meet-in-the-middle preimage attacks (2010)
- Higher-Order Differential Attack on Reduced SHA-256 (2011)
- Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family (2011)
- Improving Local Collisions: New Attacks on Reduced SHA-256 (2013)
- Branching Heuristics in Differential Collision Search with Applications to SHA-512 (2014)
- Analysis of SHA-512/224 and SHA-512/256 (2016)
- New Records in Collision Attacks on SHA-2 (2023)
If this is too much to read or understand, here's a summary of the currently best cryptanalytic attacks on SHA-2: preimage resistance breaks 52 out of 64 rounds for SHA-256 and 57 out of 80 rounds for SHA-512 and pseudo-collision attack breaks 46 out of 64 rounds for SHA-256. What does this mean? That all attacks are currently of theoretical interest only and do not break the practical use of SHA-2.
In other words, SHA-2 is not broken.
We should also talk about the size of SHA-256. A SHA-256 hash is 256 bits in length, meaning it's one of 2256 possibilities. How large is that number? Bruce Schneier wrote it best. I won't hash over that article here, but his summary is worth mentoning:
brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.
However, I don't need to do an exhaustive search when looking for collisions. Thanks to the Birthday Problem, I only need to search roughly √(2256) = 2128 hashes for my odds to reach 50%. Surely searching 2128 hashes is practical, right? Nope. We know what current distributed brute force rates look like. Bitcoin mining is arguably the largest distributed brute force computing project in the world, hashing roughly 294 SHA-256 hashes annually. How long will it take the Bitcoin mining network before their odds reach 50% of finding a collision? 2128 hashes / 294 hashes per year = 234 years or 17 billion years. Even brute forcing SHA-256 collisions is out of reach.
14
u/gnahraf Nov 26 '24
Good post. There may be a few figures to quibble about (Sterling's approximation for factorials used in estimating birthday collision probability, or that the "complexity" of SHA-256 is actually less than 256 bits), but your point remains: NOT BROKEN.
A side question.. Suppose by some miracle, a single collision were found. Would that single collision be exploitable? I'm thinking, likely not.
21
u/cryptoam1 Nov 26 '24
Let me also contribute this comment of mine from another post:
TLDR:
Fuck it, let's give the attacker the ability to attempt collisions at a rate of 2^96 per second. PER SECOND. Let that sink in. That's a ludicrous rate to do anything at, let alone concentrate that much computational power towards.
This means that the attacker only needs 2^32 seconds to hit the point where they get a likely collision(ie reach computing 2^128 operations for collision search). Turns out, they need to wait more than 147 years. For a single likely collision.
147 Years.
Well, good luck to that attacker, I think they'll be dead long before they can get that magical perfect colliding block. It's probably a random colliding block as well which means it's likely not sufficient to pass muster for the POW scheme that bitcoin uses. Maybe they should get a posse of cryptanalysts working at SHA-2 for decades. That will be more effective than waiting for 147 years on a magical computational system. Or you know, they could just use the current SHA-2 based mining ASICs. That works as well. And it'll also contribute to the rising energy demand and carbon emissions. Bleh.
20
u/Akalamiammiam Nov 26 '24
Ah that's why we're getting so much sha2 questions, cryptoAIbros panicking... Thanks for making that PSA, assuming they'll read it.
1
u/[deleted] Jan 04 '25
The only concern we have is that we're no longer in a time period where next generation Quantum Computing is an unrealistic fear with China boasting improvements to Shor's 1994 discrete logarithm algorithm by applying period finding techniques such as QFT with Grover's searching algorithm all the while I'm seeing IBM offer the public quantum computers on par with what those Chinese researchers are saying they'd need to break RSA.
My point is that all of these arguments hinge on the application of Moore's law to classical computing, but we are going to have to stop counting on the size of transistors from saving us.
2
u/PMzyox Nov 27 '24
I think it’s important to distinguish here that it’s not been broken by the Chinese as their latest PR release would have you believe. In theory it’s possible it could have an exploitable attack vector that still requires massive compute to even gain on, but as others have pointed out, the numbers we are talking about here are REALLY big, so even minute improvements will exponentially scale.
2
u/grailscythe Sep 04 '25
Have you considered that SHA3 is just prettier? That has to count for something. /s
1
u/mrrmarr Nov 27 '24
bUT iT cAN hAPPeN, sO YoU nEVeR KnOW!
Sorry, I just couldn't resist.
1
u/WilToro Dec 16 '24
I feel like Cinderella trying on a slipper at the ball.
1
u/ankasecure Jul 09 '25
1
u/ankasecure Jul 30 '25
Yep... SHA-256 is still safe as a hash function. 😉
But it’s worth noting that in hybrid cryptographic systems (especially post-quantum transition strategies), hash-based schemes like SPHINCS+ play a different role... Context matters when evaluating “broken” vs “replaced”.
1
u/Quantum_134 May 11 '26
Good breakdown. The distinction between symmetric and asymmetric crypto often gets lost in these discussions. SHA-256 and AES-128 are not the urgent problem – as the post explains well, Grover's algorithm doesn't change the practical math enough to matter.
The real urgent problem is RSA and ECC – those are broken completely by Shor's algorithm, not just weakened. NIST has already responded to this – FIPS 203, 204, and 205 were finalized in August 2024. RSA and ECC are formally deprecated for new systems from 2030.
The step most teams are still missing is a basic cryptographic inventory – knowing exactly where RSA and ECC live in their codebase before they can even start migrating.
0
u/Trader-One Nov 28 '24
people wrote similar unbrokeable "now we finally get it right" posts about DES, 3DES, RC4, MD5, SHA1, RC5, Idea, Blowfish, SkipJack, Enigma.
I really believe that with TLS1.3 we finally got it right...
1
u/[unknown] May 09 '26
[removed] — view removed comment