First SHA-1 Collision Attack Conducted by Google, CWI

Researchers at Google and Centrum Wiskunde & Informatica (CWI) in the Netherlands have managed to conduct the first real world collision attack against SHA-1, creating two documents with different content but identical hashes.

SHA-1 was introduced in 1995 and the first attacks against the cryptographic hash function were announced a decade later. Attacks improved over the years and, in 2015, researchers disclosed a method that lowered the cost of an SHA-1 collision to $75,000-$120,000 using Amazon’s EC2 cloud over a period of a few months.

Despite steps taken by companies such as Google, Facebook, Microsoft and Mozilla to move away from SHA-1, the hash function is still widely used.

Google and CWI, which is the national research institute for mathematics and computer science in the Netherlands, have now managed to find a collision, demonstrating that these attacks have become increasingly practical. Their technique has been dubbed “SHA-1 shattered” or “SHAttered.”

“We were able to find this collision by combining many special cryptanalytic techniques in complex ways and improving upon previous work. In total the computational effort spent is equivalent to 2 63.1 SHA-1 compressions and took approximately 6 500 CPU years and 100 GPU years,” experts said in their paper.

While the task still required a large number of computations – nine quintillion (9,223,372,036,854,775,808) to be precise – the SHAttered attack is 100,000 times faster than a brute-force attack.

The first phase of the attack was run on a heterogeneous CPU cluster hosted by Google and spread across eight physical locations. The second and more expensive phase was run on a heterogeneous cluster of K20, K40 and K80 GPUs hosted by Google.

Researchers have calculated that conducting the second phase of the attack using Amazon’s cloud would cost roughly $560,000, but the cost can be reduced to $110,000 if the attacker is patient and takes advantage of Spot instances.

Google has demonstrated the attack by releasing two PDF files that have different content, but the same SHA-1 hash. In accordance with the company’s disclosure policy, the code that allows anyone to create such PDFs will be made available after 90 days.

These collisions can pose a serious threat to a wide range of systems, including digital certificates, email signatures, software updates, backup systems, and version control tools (e.g. Git).

In order to help users identify such attacks, a free online tool that scans for SHA-1 collisions in documents has been released on the shattered.io website. Protections have also been integrated into Gmail and Google Drive. However, Google and CWI hope this attack will convince the industry to speed up migration to SHA-256 and SHA-3.

“The attack still requires a large amount of computing on both CPUs and GPUs but is expected to be within the realm of ability for nation states or people who can afford the cloud computing time to mount a collision attack,” David Chismon, senior security consultant at MWR InfoSecurity, told SecurityWeek.

“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 configuration 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,” Chismon added. “However, whether this happens before malicious actors are able to exploit the issue for their benefit remains to be seen.”