Researchers demonstrate practical break of SHA-1 hash function

Another nail in the coffin for aging hashing algorithm

Computer scientists have refined a more affordable and practical attack against SHA-1, the aging but still widely used hashing algorithm.

SHA-1 (Secure Hash Algorithm 1) is a cryptographic hash function, first developed in the 1990s, that remains in active use in many applications.

Although superseded by more modern hashing algorithms, SHA-1 is still supported as the default hash function by legacy versions of GnuPG/PGP as well as the Secure Shell (SSH) and TLS protocol, for in-process digital signatures.

Software revision control utilities such as Git use SHA-1 to verify the integrity of software builds.

Web browser vendors such as Mozilla dropped support for SHA-1 SSL certificates back in 2017, shortly after security researchers at CWI Amsterdam and Google went public with a “collision attack” against SHA-1.

The attack – put together using the power of an extensive GPU cluster – involved identifying two dissimilar PDF documents that gave the same SHA-1 hash, known as a “collision”.

Hashing functions take an input and process it to give a fixed size hash value or message digest. What’s more threatening than finding two arbitrary files that have the same hash value is identifying a way to append data to two existing documents in such a way that they return the same SHA-1 hash, a “chosen-prefix collision” (a much bigger deal).

This type of attack has been practical against the earlier MD5 hashing protocol since 2004.

Work by researchers Gaëtan Leurent and Thomas Peyrin shows that SHA-1 has now fallen to a “chosen-prefix collision” using a level of resources available to academics or well-resourced attackers, rather than the unlimited budgets and number-crunching capabilities afforded through supercomputers that government intel agencies might be able to rely upon.

The academics put together a practical attack that would cost around $45K per generated chosen-prefix collision to replicate, as explained in a paper (PDF) entitled “SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust”. It explains:

We managed to significantly reduce the complexity of collisions attack against SHA-1: on an Nvidia GTX 970, identical-prefix collisions can now be computed with a complexity of 261.2 rather than 264.7, and chosen-prefix collisions with a complexity of 263.4 rather than 267.1. When renting cheap GPUs, this translates to a cost of $11k for a collision, and $45k for a chosen-prefix collision, within the means of academic researchers.

Chosen prefix collision against SHA-1 have been achieved before but never at a cost of less than $100K. Leurent and Peyrin illustrate their improved and more powerful attack by creating a pair of PGP/GnuPG keys with different identities, but colliding SHA-1 certificates.

The clear message from the research is the developers still relying on SHA-1 need to migrate onto more secure SHA-2 and SHA-3 schemes, which remain unbroken.

The research, summarised on a dedicated site, was presented at the Real World Crypto Symposium in New York City earlier this week.

Although the cryptography behind SHA-1 is no longer reliable it would be wrong to think that practical attacks will flood the web, security luminary Rob Graham cautions.

“Nobody has yet taken an existing MD5 or SHA-1 hash and created a different document/message/file that comes out to the same hash,” Graham explains on Twitter.

Read the latest encryption security news

The practical upshot is that SSL certificates that were issued using a SHA-1 hash are still secure, but new certificates that rely on the ageing hashing algorithm ought not to be trusted.

“I can't create a fraudulent SSL certificate that matches an already issued certificate. But, I can create two certificates, for two different domains, and have a certificate authority sign one, creating a valid signature for the other domain (Google, etc.),” Graham concludes.

Professor Alan Woodward, a computer scientist at the University of Surrey, said that the latest cryptographic research ought to be the “coup de grace” for SHA-1.

“We’d seen one example of a SHA-1 collision and that really made everyone feel it was pretty much dead,” Prof. Woodward told The Daily Swig.

“This latest attack just shows that more generalised attack is possible, but it’s still expensive to do, although as with all such attacks that’ll drop.”

Practical consequences of the research center on legacy systems.

“The only real consequence is where we still have legacy use of SHA-1: some older PGP for example. I think these legacy systems are problematic for a variety of reasons not least is you sometimes find old ciphers that just never should be an option,” Prof. Woodward explained.

“As long as these things are available, which you’d hope would be very short periods, you stand a chance of downgrade attacks,” he added.

LISTEN NOW SwigCast, Episode 2: ENCRYPTION