9 Quintillion Tries Later: Researchers Crack SHA-1

Researchers at Google and CWI Amsterdam say they produced the first collision using hashes produced by the SHA-1 algorithm, hastening the end of life for the 22-year-old encryption technology.

In-brief: Researchers at Google and CWI Amsterdam say they produced the first “collision” of hashes produced with the SHA-1 algorithm, hastening the end of life for the 22-year-old encryption technology.

Researchers at Google said on Thursday that researchers at the company cracked the SHA-1 cryptographic function: creating a so-called “collision” that could open the door to attacks on privacy systems that rely on SHA-1. Google released two PDFs with different content, but the same SHA-1 hash as a proof of concept.

The successful experiment means that the SHA-1 algorithm, which was developed by the National Security Agency and first published in 1995, is no longer secure and should be “deprecated” in favor of more secure alternatives, Google said.  The company began phasing out use of SHA-1 in 2014 in favor of alternatives like SHA-256.

“For the tech community, our findings emphasize the necessity of sun setting SHA-1 usage,” the researchers from Google and Centrum Wiskunde & Informatica (CWI) Amsterdam wrote.

Cryptographic hashes take input of an indeterminate length and output a value (hash) of a predefined length based on the content. Collision attacks attempt to identify two, unique input strings that produce identical hashes. Collisions can be exploited by bad actors who could supplant a phony (or malicious) file for a legitimate one, but ensure that both files had the same cryptographic hash value attesting to their validity.

The implications for that in online transactions are dire. The SHA-1 algorithm is used to verify the authenticity of everything from signed documents to web site certificates to stored data.

Still, producing the collision was no mean task. Google and CWI Amsterdam said it required 9,223,372,036,854,775,808 (or 9 quintillion) SHA-1 compressions to generate the collision. That’s the equivalent of a single CPU running for 6,500 years or a machine with a single GPU (graphical processing unit) running for 110 years straight. A strict brute force (guessing) attack would require a GPU-based system to run for 12 million years to produce a collision, according to researchers Marc Stevens and Pierre Karpman of CWI Amsterdam and Elie Bursztein, Ange Albertini, Yarik Markov, Alex Petit Bianco and Clement Baisse of Google.

While considerable, that kind of processing power is within the reach of governments and (obviously) large technology companies. Even malicious actors who control global networks of hundreds of thousands of infected systems (bots) could also break up the task of cracking SHA-1 and spread the work across their botnets, greatly reducing the time needed to produce a collision. Also: Amazon’s Elastic Compute Cloud (EC2) allows anyone with a valid credit card to rent out clusters of CPU or GPU instances at reasonable rates, putting the cost of an attack within reach of non-state actors (though well-healed ones).

Though a significant milestone, the cracking of SHA-1 has long been anticipated. Chinese cryptographers in 2005 developed an algorithm that could find collisions in SHA-1 faster than mere guessing (or “brute force”) attacks. The eventual discovery of such a collision, then, is not expected to cause great disruption among online identity and trust providers.

NIST – the U.S. National Institute for Science and Technology – deprecated SHA-1 in 2011. Certificate Authorities who issue online identity certificates for web sites and applications, for example, have been prohibited from issuing certificates signed with the SHA-1 algorithm since 2014.  Google’s Chrome browser recently started warning about websites that are protected with a certificate signed with SHA-1 and Mozilla’s Firefox is expected to start doing so soon, as well.

“It’s not a surprise. The crypto community has been expecting and preparing for this for a decade. This is why NIST standardized on SHA-3 in 2012,” said Bruce Schneier of IBM and Harvard’s Berkman Center in an e-mail statement.

Companies should have made the transition from SHA-1 long ago, he said. “Last week (organizations) should have been using SHA-3 instead of SHA-1. This week they should have been using SHA-3 instead of SHA-1.”

Still, there are systems that still rely on SHA-1. Notably, the Git version control system, originally developed by Linux creator Linux Torvalds, still uses SHA-1 to identify and validate file objects and source code commits, the researchers from Google and CWI noted. The successful attack on SHA-1 now makes it possible for the validation features of GIT based source code repositories to be fooled, given that the attackers could generate their own collision.

“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. An attacker could potentially selectively serve either repository to targeted users,” the researchers wrote.

Spread the word!

Comments are closed.