Security researchers at Google and the CWI Institute in Amsterdam have found a way to crack the Secure Hash Algorithm-1 (SHA-1) cryptographic function.
The two organizations Thursday announced what they described as the first practical collision attack against SHA-1. In other words, what they have done is find a way to mathematically generate identical SHA-1 hashes for two entirely different sets of content, something that should typically never happen with a hash function.
A cryptographic hash is basically an alphanumeric representation of input data. A sentence or a word that goes through a cryptographic function comes out as a unique hash value or a fixed-length string of letters and numbers that bear no resemblance to the input data. With a strong hash function it is almost impossible to reverse the hash value to its original content.
The National Security Agency (NSA) designed the SHA-1 cryptographic hash function 10 years ago. Though Google and others have been warning about its susceptibility to attack, SHA-1 is still widely used for encrypting communication on the Internet and for functions like signing website digital security certificates and software code in order to authenticate them.
Cryptographic hash functions are considered critical to data integrity on the Internet for everything from authenticating passwords to ensuring that software code and security certificates haven’t been tampered with or changed. “Collision occurs when two distinct pieces of data—a document, a binary, or a website’s certificate-hash to the same [value],” a team of researchers from CWI and Google wrote in a blog Thursday.
In practice, no two different pieces of content should ever compute to the same hash value.
An attacker who figures out a way to do this “could then use this collision to deceive systems that rely on hashes into accepting a malicious file in place of its benign counterpart,” they said. As an example they pointed to two insurance documents with completely different terms both having the identical hash value.
The collision attack that Google and CWI researchers announced this week is the result of two years of research and builds on a theoretical approach first described in 2013. The theory is that it is possible to find matching hashes for two entirely different sets of content given enough hashes.
But because of the mind-boggling number of hashes it would take to find two matching ones, researchers have downplayed the chances of someone actually being able do it using brute force methods.
Researchers from Google and elsewhere have for sometime now been saying that the growing power and falling costs of modern computers would soon make it practically and economically possible for someone to compute hash collisions.
The attack that Google and CWI researchers announced this week harnessed Google’s cloud computing infrastructure and was one of the largest computations ever completed, according to the researchers. Finding a collision involved nine quintillion computations in total and took 6,500 years of CPU computation to complete the first phase and an additional 110 years of computation with graphics processing units to complete the second phase.
In a tweet lauding the achievement, Mikko Hypponnen, chief research officer at security firm F-Secure, estimated it would cost around $500,000 to $800,000 for someone to replicate the computational power and effort that Google and CWI put in to break SHA-1.
News of the collision attack is sure to heighten calls for SHA-1 to be deprecated especially for critical functions like signing TLS certificates that are used to authenticate websites. Google announced plans to phase out SHA-I use in Chrome back in 2014 and has been calling on others and the industry to move to SHA-256 and other cryptographic hash functions.
“We hope that our practical attack against SHA-1 will finally convince the industry that it is urgent to move to safer alternatives,” the researchers said in their blog.