February 23, 2017
Security researchers at the CWI institute in Amsterdam working with a team from Google Research say they have found a faster way to compromise the SHA-1 hash algorithm — announcing what they describe as “the first practical technique for generating a SHA-1 collision” in a blog post today.
A ‘collision’ here refers to being able to generate the same hash multiple times — thereby potentially enabling a attacker to deceive a system into accepting a malicious file in place of its benign counterpart.
The SHA-1 hash algorithm is still in use for verifying the authenticity of digital content, despite the march of Moore’s Law ramping up compute power available to hackers in the wild — and despite other, more robust alternatives having existed for years.
The SHA-1 collision attack, which the group is puntastically naming ‘SHAttered’, is described in more detail here. Their website also hosts a proof of the attack — in the form of two PDFs with different content but the same hash.
Systems that could be compromised via the technique according to the researchers include document signature, HTTPS certificates, version control (git), backup systems, software updates, ISO checksums and more.
“It is now practically possible to craft two colliding PDF files and obtain a SHA-1 digital signature on the first PDF file which can also be abused as a valid signature on the second PDF file,” they write.
“For example, by crafting the two colliding PDF files as two rental agreements with different rent, it is possible to trick someone to create a valid signature for a high-rent contract by having him or her sign a low-rent contract.”
SHA-1 is more than two decades old at this point. And faster-than-brute-force techniques for attacking it have been around since as early as 2005. Indeed, you can read Bruce Schneier blogging about one such attack algorithm here.
But while that 2005 attack was able to find collisions in 269 calculations, or about 2,000 times faster than brute force — which Schneier described as being “just on the far edge of feasibility with current technology” — the CWI and Google Research method being announced now is described as “more than 100,000 times faster than a brute force attack”.
Hence being dubbed the “first practical technique” to compromise digital signatures incorporating SHA-1.
“The SHAttered attack is 100,000 faster than the brute force attack that relies on the birthday paradox. The brute force attack would require 12,000,000 GPU years to complete, and it is therefore impractical,” they write in an FAQ.
“This attack required over 9,223,372,036,854,775,808 SHA1 computations. This took the equivalent processing power as 6,500 years of single-CPU computations and 110 years of single-GPU computations.”
There have been industry attempts to try to accelerate the shift away from SHA-1 for multiple years now. Mozilla, for example, announced a depreciation plan for its Firefox browser as early as September 2014.