SHA-1 and the fix the NSA never explained
On February 23, 2017, researchers at CWI Amsterdam and Google produced two PDF files with different text — different enough that a careful reader would notice immediately — and the same SHA-1 fingerprint. A digital signature over either document would verify the other. The collision had cost roughly 6,500 CPU-years to compute and about $110,000 in cloud time. It was an expensive proof of a point that cryptographers had been making, less expensively, since 2005: SHA-1 was done.
The algorithm at the center of this was published in April 1995 as FIPS PUB 180-1, the Secure Hash Standard. The National Security Agency designed it; NIST handed it down as a federal requirement. SHA-1 took any message of any length — a grocery list, the complete works of Dickens, a firmware update — and reduced it to 160 bits: 40 hexadecimal characters, always exactly 40, produced in the same deterministic fashion regardless of input.
The algorithm’s predecessor had appeared two years earlier, in 1993, and been quietly withdrawn. The NSA replaced it with SHA-1, which differed in exactly one way: a single bitwise rotation buried in the compression function’s message schedule. The NSA said it corrected a flaw. It did not say what flaw. Five years later, in 1998, French cryptographers Florent Chabaud and Antoine Joux published an attack on the 1993 original that exposed a detectable weakness in the compression function — precisely the weakness SHA-1’s rotation had corrected. The NSA had known and fixed it in silence.
Meanwhile SHA-1 had become the load-bearing infrastructure of the internet. SSL and TLS certificates, SSH server fingerprints, PGP signatures, IPsec authentication, and — from 2005 — every object in Linus Torvalds’s new version-control system, Git. Every commit, every file snapshot, every directory listing was identified by its SHA-1 hash. The promise on which all of this rested was one-wayness: given a hash, recovering any message that produces it should require so many operations that the sun would exhaust its hydrogen first.
In February 2005, Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu of Shandong University announced a theoretical attack that would find a SHA-1 collision at roughly a two-thousandth of the expected computational cost. Still no actual collision — just a viable route to one. NIST noted the finding. Most vendors kept shipping SHA-1.
The full collision arrived twelve years later, when Marc Stevens at CWI and Elie Bursztein at Google ran the attack to completion. Two PDFs, one hash. The Git community absorbed the news uneasily: a collision in a repository could silently substitute one object for a different one sharing the same identifier. The migration to SHA-256 object IDs began and is still, years later, not complete.
NIST formally deprecated SHA-1 for digital signatures in 2013. The standard that once held the internet’s trust infrastructure together had been built on a one-bit correction the NSA made and never explained — a single rotation in the message schedule, applied once, classified for five years, and used to secure a planet’s worth of communications for two decades.
There is a difference between a standard being deprecated and a standard being gone. SHA-1 is still the former.
Sources
- SHA-1 — Wikipedia — technical specifications, SHA-0 withdrawal, the Chabaud–Joux 1998 attack, Xiaoyun Wang’s 2005 cryptanalysis, and the full deprecation timeline.
- CWI and Google announce first SHA-1 collision — details of the SHAttered attack: Marc Stevens, Elie Bursztein, the PDF proof-of-concept, and the computational cost.
- FIPS PUB 180-1 — NIST — the original April 1995 NIST publication establishing SHA-1 as a Federal Information Processing Standard.