Security researchers have achieved the first real-world collision attack against the SHA-1 hash function, producing two different PDF files with the same SHA-1 signature. This shows that the algorithm’s use for security-sensitive functions should be discontinued as soon as possible.
SHA-1 (Secure Hash Algorithm 1) dates back to 1995 and has been known to be vulnerable to theoretical attacks since 2005. The U.S. National Institute of Standards and Technology has banned the use of SHA-1 by U.S. federal agencies since 2010, and digital certificate authorities have not been allowed to issue SHA-1-signed certificates since Jan. 1, 2016, although some exemptions have been made.
However, despite these efforts to phase out the use of SHA-1 in some areas, the algorithm is still fairly widely used to validate credit card transactions, electronic documents, email PGP/GPG signatures, open-source software repositories, backups and software updates.
A hash function such as SHA-1 is used to calculate an alphanumeric string that serves as the cryptographic representation of a file or a piece of data. This is called a digest and can serve as a digital signature. It is supposed to be unique and non-reversible.
If a weakness is found in a hash function that allows for two files to have the same digest, the function is considered cryptographically broken, because digital fingerprints generated with it can be forged and cannot be trusted. Attackers could, for example, create a rogue software update that would be accepted and executed by an update mechanism that validates updates by checking digital signatures.
In 2012, cryptographers estimated that a practical attack against SHA-1 would cost $700,000 using commercial cloud computing services by 2015 and $173,000 by 2018. However, in 2015, a group of researchers from Centrum Wiskunde and Informatica (CWI) in the Netherlands, Nanyang Technological University (NTU) in Singapore and Inria in France devised a new way to break SHA-1 that they believed would significantly lower the cost of attacks.
Since then, the CWI researchers have worked with Google, using the company’s massive computing infrastructure, to put their attack into practice and achieve a practical collision. It took nine quintillion SHA-1 computations, but they succeeded.
According to Google, it was one of the largest computations ever completed: the equivalent processing power of 6,500 years of single-CPU computations and 110 years of single-GPU computations. It was performed on the same infrastructure that powers Alphabet’s AlphaGo artificial intelligence program and services like Google Photo and Google Cloud.
Does this mean that achieving SHA-1 collisions is now within the grasp of most attackers? No, but it’s certainly within the capabilities of nation-states. In less than three months, the researchers plan to release the code that made their attack possible so other researchers can learn from it.
“Moving forward, it’s more urgent than ever for security practitioners to migrate to safer cryptographic hashes such as SHA-256 and SHA-3,” Google said in a blog post Thursday. “In order to prevent this attack from active use, we’ve added protections for Gmail and GSuite users that detects our PDF collision technique. Furthermore, we are providing a free detection system to the public.”
Starting with version 56, released this month, Google Chrome will mark all SHA-1-signed HTTPS certificates as unsafe. Other major browser vendors plan to do the same.
“Hopefully these new efforts of Google of making a real-world attack possible will lead to vendors and infrastructure managers quickly removing SHA-1 from their products and configurations as, despite it being a deprecated algorithm, some vendors still sell products that do not support more modern hashing algorithms or charge an extra cost to do so,” said David Chismon, senior security consultant at MWR InfoSecurity. “Whether this happens before malicious actors are able to exploit the issue for their benefit remains to be seen.”
More information about the attack, which has been dubbed SHAttered, is available on a dedicated website and in a research paper.