Google kills SHA-1 with successful collision attack
Source: Fahmida Y. Rashid
SHA-1 in digital certificates and cryptographic keys hasn't been safe for years. With the world's first successful collision attack, the clock has run out for the hash function
It's official: The SHA-1 cryptographic algorithm has been "SHAttered." Google successfully broke SHA-1. Now what?
After years of warning that advances in modern computing meant a successful collision attack against SHA-1 was imminent, a team of researchers from Google and Centrum Wiskunde & Informatica (CWI) in the Netherlands have successfully developed the first successful SHA-1 collision. In practical terms, SHA-1 should not be relied upon for practical security.
Modern cryptographic hash functions depend on the fact that the algorithm generates a different cryptographic hash for every file. A hash collision refers to having two separate files with the same hash. The fact that cryptographic weaknesses in SHA-1 make certificates using the SHA-1 algorithm potentially vulnerable to collision attacks is well-known. The National Institute of Standards and Technology deprecated SHA-1 more than five years ago, and experts have been long urging organizations to switch to stronger hash algorithms. Up until now, the only thing going for SHA-1 was the fact that collision attacks were still expensive and theoretical.
No longer, as the Google-led research team has developed a method that let them generate two PDF files with different content but generating the same SHA-1 hash. While the collision attack is still expensive, the "SHA-1 shattered" attack is no longer theoretical, which means the attack is within the reach of anyone motivated enough and with deep enough pockets.
"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," the team from Google and CWI wrote in a blog post. "We were able to find this collision by combining many special cryptoanalytic techniques in complex ways and improving upon previous work."
However, it's worth noting that forging digital certificates will remain difficult thanks to the new CA/Browser Forum rules that require 20 bits of randomness to be added to digital certificate serial numbers.
SHA-1 is dead; act accordingly
Even though many organizations have been working on migrating to SHA-2 for the past year, the switchover isn't 100 percent complete, which means organizations who have not yet finished (or started!) their switchover are now at risk. Attackers now have proof collision attacks are possible, and under Google's disclosure policy, the code that would allow attackers to create these PDF documents will be public in 90 days. The clock is ticking.
Google's Chrome web browser began marking websites still using digital certificates signed with SHA-1 as not trusted at the beginning of 2017, and Microsoft and Mozilla are expected to follow suit with Edge and Firefox. Under the latest guidelines from the CA/Browser Forum, the main body regulating how certificate authorities issue TLS certificates, browser vendors and CAs are prohibited from issuing SHA-1 certificates.
View the INKvestment color inkjet All-in-One printers with super high yield cartridges. Learn more!
The research team created an online tool that scans for SHA-1 collisions in documents on the shattered.io website. Google has already integrated protections into Gmail and Google Drive.
While a significant number of organizations have taken the warnings to heart and migrated their websites, many still use SHA-1 for digitally signing software and to verify digital signatures and cryptographic keys for non-web-facing infrastructure such as software updates, backup systems, and other applications. Version control tools also rely on SHA-1--Git for example "strongly relies" on SHA-1.
"It is essentially possible to create two GIT repositories with the same head commit hash and different contents, say a benign source code and a backdoored one," the researchers wrote on the shattered.io site. "An attacker could potentially selectively serve either repository to targeted users."
The sky isn't falling ... yet
All that said, the attack is still difficult, and weaponized malware using SHAttered isn't going to be hitting networks overnight. The researchers said finding the collision was difficult and looked "impractical" at times. "We finally solved it by describing this problem as a mathematical problem itself," the researchers wrote.
The team wound up performing more than 9 quintillion (9,223,372,036,854,775,808) SHA-1 computations in total, which translated to approximately 6,500 years of single-CPU computations to complete the first phase of the attack, and 110 years of single-GPU computations to complete the second phase. The technique is still more than 100,000 times faster than a brute-force attack.
The heterogeneous CPU cluster used in the first phase was hosted by Google and spread across eight physical locations. The heterogeneous cluster of K20, K40, and K80 GPUs used in the second phase was also hosted by Google.
While those numbers seem very large, nation-states and many large companies have the cryptoanalysis expertise and financial resources to obtain enough GPUs to do this in a reasonable time, if they really wanted to.
Back in 2015, a different group of researchers disclosed a method that would have put the cost of creating a successful SHA-1 collision using Amazon's EC2 cloud between $75,000 and $120,000. The Google team estimated that running the second phase of the attack in Amazon's EC2 would cost roughly $560,000, but if the attacker is patient and willing to take the slower approach, that cost drops to $110,000, well within the range estimated back in 2015.
What's next?
The industry has known since 2011 that this day was coming, and most vendors have said they would speed up their deprecation plans and deadlines if a stronger attack becomes reality. NIST has been recommending everyone move from SHA-1 to SHA-2, as has the CA/Browser Forum. Expect to hear new timelines and schedules from major vendors over the next few weeks and incorporate the changes accordingly into your infrastructure.
But SHA-2 is subject to the same mathematical weaknesses as SHA-1, so why not move to the stronger SHA-3 algorithm, which doesn't share the same issues? As InfoWorld's Roger Grimes told me, that isn't a practical idea for several reasons, and it would likely lead to wide-scale difficulties and operational challenges. Although NIST has been recommending moving to SHA-3 since August 2015, practically no operating system or software supports it by default. Also, SHA-2 is not considered as operationally weak as SHA-1 because its hash lengths are longer, so it is good enough to use for now. SHA-2 hash lengths range from 192 bits to 512 bits, although 256 bits is the most common. Most vendors will start adding more SHA-3 support over time, so it's best to use the migration to SHA-2 as the opportunity to learn what to do for the inevitable SHA-2-to-SHA-3 migration.
The warnings were there all along, and now the time for warnings are over. IT teams need to finish the SHA-1 to SHA-2 migration, and they should use the news that a successful collision attack is now within reach as the hammer to bludgeon management into prioritizing the project.
| }
|