SHA-1 Considered Harmful Today

Remember all the fuss, not 6 months ago, when researchers created a rogue CA by exploiting MD5's weaknesses to collision attacks? Weaknesses that had been well known for at least a decade?

The affected Certificate Authority's response was to quickly switch to another cryptographic hash, SHA-1. A hash function that too had known attacks for years, which had been improving ever since.

Now it just got worse.

SHA-1 Collisions now 2^52. This yet unreleased paper lowers the bar on the practicality of producing a SHA-1 collision to a medium-sized organization or a large botnet. Note: Paper now available at ePrint.

Let's think about it for a while. On a current desktop computer, a single SHA-1 operation (compression) takes about 600 clock cycles. On a 3 GHz CPU, this means about 3*10^9 / 600 = 5 million operations per second (per core). On a single core, this attack would take too long to be useful, i.e. about 2^52 / 5*10^6 / 31536000 ~ 28 years. However, on a not-so-large cluster of 512 nodes this would go down to 20 days: quite doable with a reasonable budget. With Amazon's EC2 service, for instance, it would only cost about $6000 to do this kind of work. On a large-scale botnet, like the ones controlled by the Conficker or Storm worms, it could be done almost at no cost to the attacker!

Thus, we urge all organizations that provide or rely on digital signatures or employ SHA-1 for data integrity to switch to strong hash functions, such as SHA-2 (which includes SHA-224, SHA-256, SHA-384 and SHA-512) or Whirlpool, at least until 2012, when SHA-3 is due to be made an official standard. Other uses of hash functions, such as MACs or pseudo-random number generators are not affected by this new attack.

Update: Aumasson points out that the original paper has been withdrawn, as the complexity estimates of O(2^52) were wrong. More details on the ePrint entry. Still, the point made in this page is still valid, as attacks on SHA-1 are becoming practical fast.