SHA-1 broken
As Bruce Schneier reported earlier this week, the SHA-1 cryptographic message digest algorithm has been broken by a team of Chinese researchers.
The researchers demonstrated that SHA-1 is not collision-free by relying on cryptanalytic techniques used previously on other algorithms:
Our analysis is built upon the original differential attack on SHA0, the near collision attack on SHA0, the multiblock collision techniques, as well as the message modification techniques used in the collision search attack on MD5. Breaking SHA1 would not be possible without these powerful analytical techniques.
As Slashdot reports today, it’s now even feasible to crack the algorithm with current computing power:
The findings are that SHA-1 is not collision free and can be broken in 2^69 attempts instead of 2^80. This is about 2000 times faster. With todays computing power and Moores Law, a SHA-1 hash does not last too long. Using a modified DES Cracker, for the small sum of up to $38M, SHA-1 can be broken in 56 hours, with current computing power. In 18 months, the cost should go down by half.
Quiet Earth laments the fact that the number of usable cryptographic hash algorithms is dwindling, but PGP’s CTO advices calm:
It’s time to walk, but not run, to the fire exits. You don’t see smoke, but the fire alarms have gone off.
In any case, it’s time to start leaving SHA-1 behind, along with the other relics of the crypto war. Sad though it may be that so many respected cryptographic algorithms have fallen to cryptanalysis in recent times, these events only serve to vindicate researchers believing in full disclosure. Bad news can only be worse when they’re affecting you and you’re not aware of them.
Update (21/2): Despite not running for the nearest fire exit, PGP Corp. is sure trying to be fast on it’s feet, as it seems it’ll be migrating from SHA-1 to a stronger variation. For a theoretical vulnerability (i.e. only recently demonstrated and probably only exploitable by state intelligence agencies at the moment), this one has caused a lot of commotion. The fact is that, at the moment, there is no golden hash, only shadows of grey. PGP know this of course, as their CTO’s article about last year’s cryptanalysis triumphs shows: the same Chinese researchers were then responsible for defeating MD5 and demolishing MD4
.
Because we don’t have their paper yet, we don’t know how they’re finding collisions. We do know that it’s a good mechanism, however. In their MD4 break, they said that they can do it with a work factor of 2^2 to 2^6.Yes, you saw that right, that was 2^2, commonly called 4 (or in English “four”), and 2^6, better known as 64 (sixty-four). They noted that in this case, the break can be done by hand-no computers required. We have known MD4 is broken for years, but that is an impressive result, indeed.
Of course, the examples given for hash collision attacks usually concern forged bank orders, and it’s understandable that a security firm would like to assuage the fears of it’s customers, but by standing behind not so well tested algorithms, such as are SHA-128 and SHA-256, without giving due warning, they might be doing them a bigger disservice.
Update (22/2): Schneier himself recommends using Whirlpool, a public domain hash function which has been selected for the IST NESSIE project portfolio of cryptographic primitives, included in the revised ISO/IEC 10118-3:2003(E) standard and implemented in the GNU Crypto library for Java. I guess that’s a good choice as any…
