SHA-1 (Secure Hash Algorithm 1) forms part of several widely used security applications and protocols. However, the cryptographic hash function, that has been the backbone of Internet security, is now officially dead.
Security researchers at CWI Institute, Amsterdam, working with a Google Research team, have confirmed that SHA1 is no longer secure against well-funded opponents. In their blog post, they reveal details about the first practical technique for generating a SHA-1 collision.
A ‘collision’ is the ability to generate the same hash for multiple dissimilar files. This potentially enables an attacker to deceive a system into accepting a malicious file in place of the expected file.
The SHA-1 collision attack, humorously termed ‘SHAttered’, has long been an issue pondered over. In 2005, cryptanalysts found attacks on SHA-1 suggesting that the algorithm might no longer be secure for use. Since 2010, many organisations have shifted to the more secure SHA-2, SHA-3 replacement.
The 2005 attack revealed faster tactics, compared to the brute-force approach, as evident from Bruce Schneier’s blog. The strength of a hash function is usually compared to a symmetric cipher of half the message digest length. Thus, using brute-force, SHA-1 collisions are expected to be produced by 280 evaluations. However, the 2005 attack was able to find collisions in 269 calculations, which is 2,000 times faster than brute force.
In 2008, an attack methodology by Stéphane Manuel reported hash collisions with an estimated theoretical complexity of 251 to 257 operations. Many such reports followed, but were mostly retracted.
On 8 October 2015, Marc Stevens, Pierre Karpman, and Thomas Peyrin published a freestart collision attack on SHA-1’s compression function that required only 257 SHA-1 evaluations. Hence, this “first practical technique” can now endanger 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.
How SHA-1 Got SHAttered
Cryptographers refer to the attack disclosed on Thursday, as an “identical-prefix” collision. It allows the attacker to create two distinct messages that have the same hash value. Although, less powerful than the “chosen-prefix” MD5 collision carried out by Flame, it is critical.
In case of chosen-prefix collision, the attacker can choose two arbitrarily different documents. Then append different calculated values that result in the whole documents having an equal hash value.
While chosen-prefix is more powerful, identical-prefix collision attacks are more versatile. With such attacks, area of threats include certificates with identical names and different pubkeys, PDF files, PostScript files, TIFF files, JPEG files, Word files, file archives, signed software, Email message/attachment PGP/GPG signatures.
The findings are a result of nearly two-year collaboration between researchers at the Centrum Wiskunde & Informatica in the Netherlands and Google’s research security, privacy, and anti-abuse group. The study, done in phases, was opted on CPU clusters hosted by Google, rather than Amazon Web Services platform, to reduce expenditure.
The first phase of the attack was run on a heterogeneous CPU cluster that was hosted by Google and spread over eight physical locations. A second and more expensive phase was run on a heterogeneous cluster of K20, K40, and K80 GPUs.
The consequences of a collision attack can be widespread, like switching of legal documents and agreements. Fortunately, certificates to HTTPS-protected websites aren’t likely to be affected. Browser-trusted certificate authorities no longer rely on SHA1 to sign TLS certificates they issue.
Consistent with Google’s security disclosure policy, the source code for performing the collision attack will be published in 90 days. This gives a breathing space of three months for present systems that are still reliant on SHA-1 for security.
Revision control systems such as Git and Mercurial use SHA-1 not for security but for ensuring that the data has not changed due to accidental corruption. The GnuPG e-mail encryption program still relies on security by SHA1. Myriad software packages rely on SHA1 signatures to ensure installation and updation.
The official death of SHA-1 ensures that all these systems must migrate to the secure options available. The migration, though necessary, will be tricky. However, companies have already started taking swift actions.
Support for SHA-1 certificates was removed from Google’s Chrome browser in January, while Mozilla’s Firefox browser is due to remove support soon. Certification Authorities that abide by the CA/Browser Forum regulations are also not allowed to issue SHA-1 certificates anymore.
We hope that our practical attack against SHA-1 will finally convince the industry that it is urgent to move to safer alternatives such as SHA-256. It’s more urgent than ever for security practitioners to migrate to safer cryptographic hashes such as SHA-256 and SHA-3.
Meanwhile, the researchers have released a tool that detects if files are part of a collision attack. Protections have been added for Gmail and GSuite users, against PDF collision technique.