Researchers unveiled on Thursday the first practical collision attack for the 22-year old cryptographic hash function SHA-1.
While long expected, news of the attack, dubbed ‘SHAttered,’ should further accelerate the urgency of sunsetting of the maligned algorithm.
Researchers from Google, Elie Bursztein, Ange Albertini, and Yarik Markov, along with researchers from the Cryptology Group at Centrum Wiskunde and Informatica (CWI) – a research center in Amsterdam – Marc Stevens and Pierre Karpman, discussed the attack in a blog post and academic paper (.PDF) on Thursday.
The attack, which was in the works for two years, stems from the colliding of two PDF files. Bursztein and company claim that through the attack, it’s possible to obtain the SHA-1 digital signature on the first PDF file and then use that to abuse the second PDF file by mimicking that signature.
The researchers claim the collision–which they got off the ground with help from Google’s cloud infrastructure–is “one of the largest computations ever completed.” The numbers back up the claim. In order to perform the attack, the researchers claim they needed to carry out nine quintillion SHA-1 computations in total, something that took 6,500 years of CPU computation time to complete the first phase and 110 years of GPU computations to finish the second.
“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,” the researchers explained.
The first phase of the attack was carried out on a CPU cluster by Google in eight separate locations; the second was carried out on a single cluster of K20, K40, and K80 GPUs, also hosted by Google.
In their paper, the researchers said the ability to use GPUs was crucial and allowed them to “significantly decrease the calendar time necessary to perform the computation.”
Coincidentally, Google began offering support for graphic processing units, or GPUs, for its cloud platform, earlier this week. The units of computational power have become increasingly integrated into machine learning, scientific computing, and other specialized workload scenarios.
While the computations would require years to complete, the researchers claim their method is still more than 100,000 times faster than a brute force attack, the likes of which have been theorized but are still considered impractical as one would take 12,000,000 GPU years to complete.
Cryptographers have long forecasted the death of SHA-1. Theoretical attacks, in which two inputs of a hash function generate the same hash, have existed in some shape or form since 2005.
Browsers began deprecating the algorithm in earnest over the past two months – both Google and Mozilla removed SHA-1 support from their browsers in January; Microsoft cut off support for SHA-1 last week in its Edge and Internet Explorer 11 browsers.
Many experts began advocating the algorithm be phased out as early as 2013 and 2014.
Noted cryptographer Bruce Schneier famously predicted in 2012 that a practical collision attack against SHA-1 would cost $700,000 in 2015 and $143,000 in 2018. He surmised at that cost attacks, especially if they were carried out by a wealthy criminal enterprise or government entity, could be feasible.
Karpman and Stevens, assisted by Thomas Peyrin, previously published research on a freestart collision attack for SHA-1, in 2015. That paper described how a theoretical freestart attack could be carried out against SHA-1’s compression function in months, not years, and cost upwards to $120,000. Shortly after that paper was published, Stevens began working with Bursztein on ‘SHAttered,’ leveraging Google’s infrastructure for attacks.
In wake of the discovery, the researchers are warning that it’s critical for the security community to move away from SHA-1 and instead adopt “safer alternatives” like SHA-256.
Google, for its part, says it has reinforced Gmail and GSuite to protect against the collision technique.
Stevens and Dan Shumow, a cryptographer with Microsoft, have also coded a command line detection tool, available for free on GitHub, in which users can upload a file to test if they’re part of a collision attack.
Given the mitigations currently in place, Google says it will stand by its vulnerability disclosure policy and release code around the collision attack in late May.
“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 write. “Following Google’s vulnerability disclosure policy, we will wait 90 days before releasing code that allows anyone to create a pair of PDFs that hash to the same SHA-1 sum given two distinct images with some pre-conditions.”
SHA-1 has been on its deathbed for years. Despite being officially deprecated by NIST in 2011, its still used in a variety of ways worldwide. The algorithm figures into how some credit card transactions are processed and some software is updated. It’s also used in document signing systems, back up systems, and GIT, a system that’s used for tracking changes in computer files and coordinating work between users.
While those systems were urged to distance themselves from the insecure algorithm years ago, for those still using it, the real countdown to move away from SHA-1 begins today.
