1

Regarding the SHA 1 deprecation, I found this information here:

http://blogs.technet.com/b/srd/archive/2013/11/12/security-advisory-2880823-recommendation-to-discontinue-use-of-sha-1.aspx

I know that the 2^77 and 2^61 deal with time complexities, but are these specific attacks against the full 80 rounds of SHA1 or do they mean SHA1 was broken with fewer rounds using those time complexities?

7

What the page you link to means is that there are known attacks which, when implemented, would allow building collisions with some costs:

  • If the goal is "raw collisions" then the computational effort is equivalent to running 261 times the SHA-1 function. A raw collision is such that the attack produces two messages m and m' which are distinct but hash to the same value. In fact, due to the nature of the attack, the attacker can choose a common prefix, i.e. m and m' begin with the same sequence of bytes that the attacker gets to choose; then come some bytes that he must accept "as is".

  • If the attacker wants messages m and m' begin with two distinct sequences and choose both those prefixes (that's chosen prefixes), then the cost is higher, up to an average cost of 277.1.

Since SHA-1 has output size 160 bits, both kinds of collisions can be done generically with effort about 280: a "generic" attack is one that works against all hash functions, however perfect they may be. To describe things simply: the attacker chooses his prefixes p and p', then generates random values r and r', computing h(p||r) and h(p'||r'). Once the attacker has accumulated about 280 values h(p||r), and 280 values h(p'||r'), then probability of a collision (one hash value appearing in both sets) begins to be non-negligible.

Important notes:

  • These attacks are theoretical: 261 is still quite a lot, and the attack has not been run yet. The description is sound, and our experience with MD5 tells us that it most probably works as advertised; but, until it has been executed, we don't really know.

  • To get the gist of what 261 represents, suppose (with very high optimism) that implementing the attack can be done efficiently on common GPU, with optimal parallelism (there are reasons to believe that it is not necessarily the case). Then we can use existing benchmarks to try to see what it would take to run the attack once. An AMD R9 290X can apparently run about 3.7 billions of SHA-1 par second; thus, a 261 effort translates to 20 years on a single such GPU. You can trim that down to one month if you buy and run 240 such GPU, one day if you have 7200 GPU. Power consumption alone will be in the megawatt range... this gotta be expensive.

  • To actually exploit the attack, to produce (for instance) a pair of colliding certificates (allowing to reuse the signature from the first certificate on the second), you need the chosen prefix attack; raw collisions don't cut it. This multiplies the computation effort by 216.1 (the ratio between 277.1 and 261), which is about 70000. With your GPU, assuming you get them all in line, then you will need your own nuclear power plant, and still be patient...

  • To be fair, we must also point out that the chosen prefix attack can result in rogue certificates only if the CA uses fully deterministic and predictable certificate contents -- in particular, a deterministic serial number. Some CA software does not have this specific issue; e.g. Microsoft's CA (ADCS) embeds about 30 bits of randomness in the serial number, which prevents application of the collision attacks (even with MD5).

  • The chosen prefix attack counts as an actual break, from an academic point of view, because 277.1 is lower than 280... but not much lower (only about 7 times lower). Although comparing numbers that high is perfectly valid in cryptography, it can be predicted that actually applying the attack will raise a non-negligible number of issues. When we are talking about efforts in the 230 or 240 range, things are easy: costs are mostly about buying a couple of big PC. In the 260 or more, the problem becomes one of thermodynamics (flowing energy in, evacuating heat) and economics, and we can no longer scale results with reliable accuracy.

Bottom-line: though the attacks which are talked about are "real" (academically speaking) and apply to the full SHA-1 (with all its internal rounds), they are still in the "theoretical only" range, and mapping their alleged costs to actual dollars is complex because they are in a range where non-cryptographic issues tend to dominate.


The gist of the advisory you show is this sentence:

It appears that SHA-1 is on a similar trajectory

That sentence is full of unsubstantiated insinuations, and must not be considered as more accurate than, say, astrology. Astrology works at least as well are pure luck, so it cannot be completely dismissed; but we must still note that the idea of attacks becoming faster over time is of an essence which is qualitatively distinct of, say, Moore's law. The steady pace of computing power available for a given price has been sustained by a number of ideas which were already known in the 1970s, and we are still not at the end of it. There are "physical walls" that will become bothersome in the future (quantum tunnelling of electrons between wires...) be we also know that we still have a few years before us; CPU in three years will be faster and cheaper, and we know how we will build them.

Advances on cryptographic attacks are not of the same kind. Predicting that attacks will get better means that we assume that better attacks exist, and that the relevant ideas will sprout in the right brains. This cannot be quantified with any kind of reliability. Maybe in ten years we will still be at 261 (and 277.1). Maybe we will be at 230 (i.e. sub-second break). We really don't know.

This does not mean that SHA-1 should not be avoided. In fact you already should not use it in new systems, and strive to implement support for SHA-256 anywhere. But you should not panic. The MD5 example shows us that we, actually, have time: it took 5 years between actual MD5 collisions, and the first (and only) demonstration of colliding certificates.

The current fashion of placing an anathema on SHA-1 should be understood politically, not cryptographically. The situation on SHA-1 has not substantially changed in the last four years. What happens right now is that Microsoft and Google have apparently agreed to force widespread SHA-256 support, and they do so by the usual expedient of empire builders: threats. They kick the anthill. They brandish the apocalyptic removal of SHA-1 so that the rest of the World finally sets in motion and begins to actually support SHA-256.

(My guess is that Microsoft, at least, will backpedal. For instance, consider that right now, the .NET framework is still based on CrytoAPI, not CNG, and appears to be incapable of computing CMS or XML-DSig signatures with SHA-256 as base hash function.)

  • 1
    Those 20 GPU years should cost around $10k, not *that* expensive. Of course that assumes that the actual cost is dominated by parallelizeable SHA-1 computations, which is not obvious since many cryptographic attacks don't use very realistic cost models. While we could extrapolate that to a billion dollars for the $2^77$ attack, that's not very meaningful since at that point the cost of developing ASIC is small enough. This should bring down the cost by a factor 100 or so. – CodesInChaos Sep 22 '14 at 16:03
  • I wonder how fast a FPGA would be. – Yuhong Bao Nov 30 '14 at 0:45
4

The SHA1 hash has a 160 bit output. If SHA1 was perfect, you would need approximately 2^80 iterations to find a collision. Why 2^80 and not 2^160? Because of the birthday paradox

A general "collision finding" algorithm is the Tortoise and Hare Algorithm, simply uses two pointers, the faster one (the hare) moving forwards at twice the speed of the slower one (the tortoise)

...
while(h1 != h2) {
  h1 = sha1(h1)
  h2 = sha1(h2)
  h2 = sha1(h2)
}
...

"2^61" means, somebody found a way, how to reduce average number of iterations (in comparison to the general algorithm) to "2^61", which is 2^19 times faster.

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.