SHA-1 Has One Foot In the Grave

Posted on May 22, 2019 by Derek Zimmer

Last week, researchers Gaëtan Leurent and Thomas Peyrin released a paper detailing improvements to the original SHAttered project that theoretically allow chosen-plaintext attacks against SHA-1.

After the initial generation of a collision was demonstrated with SHAttered, there was a rapid response by major software vendors to take corrective action to deprecate or fully stop using SHA-1. This is because the SHAttered project did the required computation with an equivalent budget of around $100,000 for leased cloud-computing hardware, which places an exploit well within reach of a motivated attacker.

But, as with all cryptography, attacks only improve over time, and algorithms get progressively weaker as they age and techniques against them are refined.

What’s The Improvement With This New Attack?

This attack is a chosen-prefix attack.

The SHAttered project gave you no control over the colliding data, so you had to have a set of data, and then generate “garbled” data to make the SHA-1 collision fit, so that your two differing documents would produce the same hash. This is an important distinction because in the SHAttered attack you couldn’t meaningfully manipulate a file, and then make your collision fit. You could only add seemingly-random gibberish to make two files with the same core properties give you the same hash.

The chosen-prefix attack is different, because it leads us down a road where forged documents and a things like an entire rogue certificate system are possible. A fully-functional version of this type of attack was demonstrated in 2009 with a dramatic improvement to chosen-prefix attacks for the MD5 hash algorithm.

The Impact

The attack is more complex than the SHAttered attack, and requires greater computing power to find a working collision. While the attack is estimated, the methodology of attempting to gauge the cost of finding a collision appears to be sound.  While the SHAttered attack costs around $300,000 USD to perform (the SHAttered team got lucky and found theirs for less than expected), this attack is estimated to cost between $1.2 million and $7 million to generate a chosen-prefix collision. While this puts it squarely within the means of governments to exploit, it is expensive enough to be out of the reach of most adversaries.

The cost, combined with the deprecation of the algorithm because of the SHAttered attack, gives us some reassurance. However, old software running at organizations that fail to upgrade their infrastructure for years may face threats from this type of attack. Old systems could contain vulnerable SSH, IKE, or even TLS client impersonation via the SLOTH attack. And, as always, these attacks always improve and it is very likely that SHA-1 attacks will get cheaper as more improvements are found, and computer hardware gets faster.

Mitigation

These attacks continue to improve, and the time to walk away from SHA-1 was two years ago. SHA-2 and SHA-3 are already standardized and theoretically much stronger fundamentally due to their designs. SHA-3 is particularly interesting because the sponge-construction is entirely new and has no relation at all to older SHA techniques.

If you do switch over to SHA-2, it is important to note that SHA256 and SHA512 are vulnerable to length extension attacks if they are they not implemented properly, and it is safer to use SHA384 or the truncated versions of SHA2 (SHA512/256 is not the same as SHA512 or SHA256). If given the choice between SHA3 and BLAKE2 they bare both theorized to be at least as strong as SHA512/256. SHA3 is slower but gives you standards compliance for things like FIPS. BLAKE2 is significantly faster and immune to length-extension attacks.

The only case where SHA-1 is safe to be used is in HMAC. Where the hash function does not need to have the same properties to maintain secure operation.