33

Wikipedia reports

Currently, the best public attacks break 46 of the 64 rounds of SHA-256 or 46 of the 80 rounds of SHA-512.

What does this mean, and how safe is SHA-256 expected to be in the conceivable future? To a layperson, 46 out of 64 may sound like it's about "72% broken". Since Bitcoin relies on SHA-256, is it still likely going to remain secure?

2 Answers2

36

Many cryptographic algorithms (hash functions, symmetric encryption...) are organized as a sequence of "rounds", which are more or less similar to each other. It was empirically noticed that for a given algorithm structure, usually, more rounds imply more security; precisely, some classes of attacks (e.g. differential and linear cryptanalysis) see their efficiency decrease more or less exponentially with the number of rounds.

When cryptographers don't know how to break a complete algorithm, they try to break reduced versions of the same algorithm, with some features removed; in particular less rounds, for algorithms which have rounds. When SHA-256 is said to be broken "up to 46 rounds", then this means that another hash function, obtained by taking SHA-256 but removing the last 18 rounds, can be attacked (at least in an "academic way": the attack needs not be realistic, it just needs to be less impossible than attacking the full function); but removing only the last 17 rounds yields a function which, as far as we know, is as good as the full thing. Cryptographers will feel safer if the maximum number of attacked rounds is substantially lower than the actual number of rounds in the full algorithm.

Since attack efficiency behaviour tends to be exponential in the number of rounds, not linear, this cannot (and must not) be translated, even intuitively, into: "can break 80% of the rounds -> algorithm broken at 80%". Analogy: suppose you want to increase your fortune, by doubling it ten times. You start with one dollar; after ten doublings, you would have 1024 dollars; that's your goal. After eight doublings, you have 256 dollars. Eight doublings done out of ten: that's 80% of the work, right ? Then how comes you have only 256 dollars, and not 80% of 1024 dollars (which would be 819.2 dollars) ?

To sum up, you should not try to read too much in these assertions. They are scientific results which are interesting for scientists, but which can easily be overinterpreted.

Tom Leek
  • 168,808
  • 28
  • 337
  • 475
9

Firstly, to address the "72%" part:

Nope. They're more or less at the same level security.

Let's look at another quote on the page:

There are two meet-in-the-middle preimage attacks against SHA-2 with a reduced number of rounds. The first one attacks 41-round SHA-256 out of 64 rounds with time complexity of 2253.5 and space complexity of 216, and 46-round SHA-512 out of 80 rounds with time 2511.5 and space 23. The second one attacks 42-round SHA-256 with time complexity of 2251.7 and space complexity of 212, and 42-round SHA-512 with time 2502 and space 222.

SHA-256 has a time complexity of 2256 to crack normally. Reducing it to 2253.5 is a negligible difference, and it would take centuries of such changes before cracking SHA would be feasible.

About "rounds":

SHA-256 and SHA-512 are basically a particular function (with different constants for the two algorithms) applied over and over on a number. Each time you apply it, it is called a "round". What these researchers seem to have done is taken the SHA algorithms for a reduced number of rounds, and cracked that.

Manishearth
  • 8,237
  • 5
  • 34
  • 56
  • 1
    2^>200 will likely *never* be feasible barring changes to known physical laws. – ike Nov 12 '14 at 05:33
  • 1
    Never say never. Someone could develop a quantum computing attack on this cipher any day now and all this cryptography will quickly become as worthless as a old Pentium chip with that floating point bug. – pilavdzice Oct 09 '15 at 05:22
  • 2
    @pilavdzice You are incorrect. First, SHA-256 **is not a cipher**, it is a hash. Second, a quantum computer cuts the keyspace from 2^n to 2^(n/2) for key recovery for ciphers or for preimage attacks against hashes, and from 2^(n/2) to 2^(n/3) for collision attacks against hashes. A >200-bit cipher cannot be broken by a quantum computer... – forest Apr 24 '18 at 04:49