Engineers at Google have created the first SHA-1 collision, an achievement that should lay to rest any remaining doubts about the practical security of the hash function.
Cryptographers and security researchers have been warning about weaknesses in SHA-1 for several years, saying that modern computing power would soon put a collision within reach. A hash collision results from two separate files coming out with the same cryptographic hash. In theory, this shouldn’t happen when a hash function is secure, but Google researchers, working with colleagues from the Centrum Wiskunde and Informatica in the Netherlands were able to produce two distinct PDF documents that hash to the same digest.
That, as they say, should be that for SHA-1.
“We started by creating a PDF prefix specifically crafted to allow us to generate two documents with arbitrary distinct visual contents, but that would hash to the same SHA-1 digest. In building this theoretical attack in practice we had to overcome some new challenges. We then leveraged Google’s technical expertise and cloud infrastructure to compute the collision which is one of the largest computations ever completed,” the team from Google and CWI said in a post announcing the results Thursday.
The results, while not a shock to security researchers, represent a significant breakthrough. SHA-1 has been deprecated officially by NIST for more than five years and experts have considered it unfit for use for even longer, encouraging organizations to move to alternatives such as SHA-256. The researchers involved in the attack said there were some hurdles along the way that made finding the collision look impractical at times.
“We finally solved it by describing this problem as a mathematical problem itself.”
“Yes, in between the two phases of the attack, i.e., after the CPU computation and before the GPU computation, we ran into serious problems in building the second phase of the attack. We tried several approaches to overcome this problems, but the earlier solutions made the expected computational time far too big and our attack might not have been practical,” Marc Stevens, a tenured researcher at CWI, said in an email.
“We finally solved it by describing this problem as a mathematical problem itself that allowed us to really overcome this problem without any compromise in attack complexity.”
The practical implications of this attack are serious and wide-ranging. SHA-1 still is used for verifying digital signatures and cryptographic keys in many applications and also is used to sign many software applications. Crucially, browser vendors and certificate authorities have moved away from SHA-1 already, and the main group that regulates TLS certificate issuance, the CA/Browser Forum, prohibits issuing SHA-1 certificates.
But, now that this work is public and Google and CWI have shown that practical collisions are possible, other researchers and attackers likely will pick up the ball and run with it. It’s no easy task, as the numbers involved in the hash collision show:
- Nine quintillion (9,223,372,036,854,775,808) SHA1 computations in total
- 6,500 years of CPU computation to complete the attack first phase
- 110 years of GPU computation to complete the second phase
“While those numbers seem very large, the SHA-1 shattered attack is still more than 100,000 times faster than a brute force attack which remains impractical. Moving forward, it’s more urgent than ever for security practitioners to migrate to safer cryptographic hashes such as SHA-256 and SHA-3,” the researchers said.
Despite the difficulty of the attack and the massive amount of resources needed to create the collision, Stevens said there are other groups outside of Google who could accomplish the task.
“It required more than 110 years of total GPU time, but many countries and large companies can afford enough GPUs to do this in reasonable time. But it also requires expertise in cryptanalysis and scaling the attack,” Stevens said.
Image: Shawn Rossi, CC By license.
