Hadamard Get the app

Is SHA-1 Broken? From 2^69 on Paper to a $45,000 Collision

Is SHA-1 Broken? From 2^69 on Paper to a $45,000 Collision — Hadamard

Yes, SHA-1 is broken: its collision resistance has failed in practice. Researchers made the first real full SHA-1 collision in 2017. By 2020, a chosen-prefix collision, the more dangerous kind, was estimated to cost about $45,000 in rented GPU time.

So if you’re asking whether SHA-1 is broken, the precise answer is that it no longer guarantees two different inputs won’t share a hash. All the attacks below are collision attacks. Below is how the cost dropped from a theoretical result to something you can buy, where SHA-1 still shows up (Git, PGP, DNSSEC), and what NIST’s 2030 deadline means for anyone still using it.

Is SHA-1 broken? What “broken” actually means

A cryptographic hash function turns any input into a short, fixed-length digest. One of its main promises is collision resistance: finding two different inputs with the same digest should be infeasible. Signatures, certificates and content-addressed storage all depend on it. When you sign a hash, you are in effect signing every input that produces that hash.

Why 280 was the bar

SHA-1 produces a 160-bit digest. The birthday paradox means a generic collision search takes roughly the square root of the output space, not the whole space. For a 160-bit output that’s about 280 operations. Brute force can never do better than that, so cryptographers call a hash “broken” for collisions once someone finds a method that’s clearly cheaper than 280.

That definition matters, because “broken” doesn’t mean “anyone can reverse it.” It means the security margin the design promised is gone, and attacks only get cheaper over time.

2005: Wang, Yin and Yu cut the cost to 269

The first serious break came in February 2005. On February 15, Bruce Schneier reported on his blog that Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu, “mostly from Shandong University in China,” had found a way to produce full SHA-1 collisions in about 269 operations, compared with 280 for brute force.

That is 211, or about 2,048 times less work. The same research gave about 239 operations for SHA-0 and 233 for a 58-round version of SHA-1. Schneier’s headline was blunt, though he noted in the same post that the paper wasn’t generally available yet and he couldn’t confirm the attack was real. He wrote:

“SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.”

Nobody actually produced a collision in 2005. 269 was still a huge computation at the time. But the result showed that SHA-1’s design had a structural weakness, and further improvements would only lower the cost.

SHAttered: the first full SHA-1 collision in 2017

Twelve years later, the theory became a concrete result. On February 23, 2017, CWI Amsterdam (Marc Stevens, Pierre Karpman) and Google (Elie Bursztein, Ange Albertini, Yarik Markov) announced the first SHA-1 collision on the Google Security Blog. The attack, called SHAttered, produced two different, valid PDF files with the same SHA-1 hash.

The compute was large but finite. The SHAttered project site describes about nine quintillion SHA-1 computations, roughly 6,500 CPU-years plus 110 GPU-years. The accompanying paper, “The first collision for full SHA-1”, gives the effort as 263.1 calls to SHA-1’s compression function and about “100 GPU years.” It calls the attack “more than 100,000 times faster than a brute force search.”

SHAttered was an identical-prefix collision. Both files start with the same content, and the attacker computes a pair of differing blocks that bring the hash states back together. That’s enough to make two documents that look different but share a hash. The attacker can’t take two arbitrary existing documents and make them collide.

SHA-1 chosen-prefix collisions: Shambles and the $45k attack

That limit fell in January 2020. Gaëtan Leurent and Thomas Peyrin published “SHA-1 is a Shambles – First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust”. In a chosen-prefix collision, the attacker picks two different starting points, such as two different names or identities, then computes suffixes that make the full messages hash to the same value.

The paper lowered the cost of both attack types (measured on an Nvidia GTX 970):

Attack type Previous best Shambles (2020) Estimated rental cost
Identical-prefix collision 264.7 about 261.2 about $11k
Chosen-prefix collision 267.1 about 263.4 about $45k

The researchers then ran the computation for real: about two months on 900 Nvidia GTX 1060 GPUs, at a cost of about $75k. The Shambles project site also projected that a chosen-prefix collision would cost under $10k by 2025.

Real-world damage: forged PGP key certifications (CVE-2019-14855)

The researchers aimed the attack at a real system. GnuPG 1.4 used SHA-1 by default for identity certifications, the signatures that make up the PGP Web of Trust. They built two keys with different UserIDs and colliding certificates. A legitimate signature on one key could then be moved onto a forged key impersonating someone else.

The issue is tracked as CVE-2019-14855. GnuPG 2.2.18, released November 25, 2019, fixed it by treating SHA-1 identity signatures created after 2019-01-19 as invalid. The authors also advise DNSSEC users with algorithm numbers 7 or lower to upgrade. Their general advice is short: “Remove any use of SHA-1 in your product as soon as possible.”

Does Git still use SHA-1?

Git is the best-known system that still runs on SHA-1, which uses it to name every commit, tree and file. The project responded in two stages.

The first was a hardened implementation. According to Git’s hash function transition document: “Git v2.13.0 and later subsequently moved to a hardened SHA-1 implementation by default, which isn’t vulnerable to the SHAttered attack, but SHA-1 is still weak.” The hardened version detects the specific patterns that collision attacks leave behind. It doesn’t make SHA-1 strong again.

The second is a full change of hash. Git considered SHA-256, SHA-512/256, SHA-256×16, K12 and BLAKE2bp-256, and “in late 2018 the project picked SHA-256 as its successor hash.” Git needs collision and second-preimage resistance. It doesn’t need length-extension resistance, which helped narrow the choice.

The Git SHA-256 transition and Git 3.0

Git’s BreakingChanges document states that in Git 3.0, “The default hash function for new repositories will be changed from ‘sha1’ to ‘sha256’.” It notes that “SHA-1 has been deprecated by NIST in 2011”. It also lists the attacks behind the change: The SHAppening (2015), SHAttered (2017, two valid PDFs with 263 operations), Birthday-Near-Collision (2019) and Shambles (2020).

There are two caveats. First, “There is no plan to deprecate the ‘sha1’ object format at this point in time”. The wider ecosystem, including code forges, has to support SHA-256 before anything else can change. Second, “There is no planned release date for this breaking version yet.”

NIST SHA-1 retirement: the December 31, 2030 deadline

On December 15, 2022, NIST announced that it is retiring SHA-1. NIST will stop using SHA-1 in its remaining protocols by December 31, 2030. It plans to publish FIPS 180-5, which removes the SHA-1 specification. The replacements are the SHA-2 and SHA-3 families.

Some history: SHA-1 has been in use since 1995 under FIPS 180-1. It’s a modified version of SHA, the first hash function the U.S. federal government standardized, in 1993. NIST’s Chris Celi summed up the practical guidance:

“We recommend that anyone relying on SHA-1 for security migrate to SHA-2 or SHA-3 as soon as possible.”

He also spelled out the procurement consequence: “Modules that still use SHA-1 after 2030 will not be permitted for purchase by the federal government.” For vendors selling cryptographic modules into the U.S. public sector, that sets a hard date.

SHA-1 vs SHA-256: what to use instead

The answer is the same across NIST, the Shambles authors and the Git project: use SHA-2 (SHA-256 or SHA-512 variants) or SHA-3. SHA-256 is the most widely supported and is Git’s chosen successor. If you’re wondering whether SHA-256 holds up against future quantum computers, we covered that separately in what Grover and BHT really do to SHA-256.

What to audit

  • Signatures and certificates: anything that signs a SHA-1 digest is exposed to collision-based forgery. This is exactly what the PGP attack did.
  • PGP keys: move to GnuPG 2.2.18 or later, and re-certify keys with SHA-2 signatures.
  • DNSSEC: check for algorithm numbers 7 or lower, as the Shambles authors advise.
  • Git repositories: make sure you’re on a version with hardened SHA-1 (2.13.0 or later). If your tools and forge support it, consider SHA-256 for new repositories.
  • Checksums and deduplication: if an attacker can influence any of the inputs, SHA-1 can’t be trusted to tell different content apart.
  • Compliance: list every module that relies on SHA-1 before the December 31, 2030 NIST cutoff.

To see how other cryptographic transitions are progressing, our Post-Quantum Migration Tracker follows standards, browsers, messengers and blockchains as they move to new primitives.

The SHA-1 timeline also matters to us at Hadamard. We build BB84, a hash-based Layer 2 rollup on Ethereum. Its accounts are one-time addresses built from hash commitments, not ECDSA keys. Designs like this depend directly on the hash function underneath. SHA-1 is the clearest example of why that hash’s security has to be tracked over decades: it went from a theoretical break to an attack you can rent in about fifteen years.

FAQ

Is SHA-1 still safe for checksums or file integrity checks?

Not if an attacker can choose or influence the inputs. Its collision resistance is broken, so two different files can be made to share a SHA-1 hash. NIST and the Shambles authors both recommend moving to SHA-2 or SHA-3.

How much does it cost to create a SHA-1 collision?

According to the 2020 Shambles research, about $11k in rented GPU time for an identical-prefix collision and about $45k for a chosen-prefix collision. The authors projected that a chosen-prefix collision would cost under $10k by 2025.

Does Git still use SHA-1, and is my repository at risk?

Yes. Since v2.13.0, Git has used a hardened SHA-1 implementation by default, which isn’t vulnerable to the SHAttered attack, though Git’s own documentation still calls SHA-1 weak. Git 3.0 will make SHA-256 the default for new repositories, but it has no release date yet.

What is the difference between an identical-prefix and a chosen-prefix collision?

In an identical-prefix collision, both messages share the same starting content. A chosen-prefix collision lets the attacker pick two different meaningful prefixes, such as two different PGP UserIDs, and still make them collide. That’s why Shambles was more dangerous in practice than SHAttered.

Sources