Industry Security Standard SHA-1 Broken
February 27, 2017
'Industry deprecation proved to be too slow'
at the Dutch research institute CWI and Google have broken the
SHA-1 internet security standard in practice. This industry
standard is used for digital signatures and file integrity
verification, which secure credit card transactions, electronic
documents, GIT open-source software repositories and software
distribution. CWI cryptanalyst Marc Stevens says: "Many
applications still use SHA-1, although it was officially
deprecated by NIST in 2011 after exposed weaknesses since 2005.
Our result proves that the deprecation by a large part of the
industry has been too slow and that migration to safer standards
should happen as soon as possible".
The joint effort headed by Marc Stevens (CWI) and Elie Bursztein
(Google) started more than two years ago to realize Stevens’
advanced cryptanalytic research in practice with Google’s
computing infrastructure. They now successfully broke the
industry standard SHA-1 using a so-called collision attack.
SHA-1 is a cryptographic algorithm designed by the NSA and was
standardized by NIST in 1995 to securely compute message
fingerprints. These fingerprints are used in the computation of
digital signatures, which are fundamental to Internet security,
such as HTTPS (TLS,SSL) security, electronic banking, signing
documents and software. Collisions – different messages with the
same fingerprint – can lead to forgeries of digital signatures.
For instance, a SHA-1 signature obtained for one file can also
be misused as a valid signature for any other colliding file.
The SHA-1 collision announced today is the culmination of a
research line initiated at CWI more than seven years ago to
develop an optimal practical collision attack against SHA-1.
This previously resulted in the currently best known theoretical
attack by Stevens in 2012 on which the announced result has
built further upon. Elie Bursztein says: “Finding the collision
in practice took a lot of effort both in building the
cryptanalytic attack and in its large scale execution. It
required over 9,223,372,036,854,775,808 SHA1 computations that
took 6,500 years of CPU computation and 100 years of GPU
computations. Yet this is more than 100,000 times faster than a
brute force attack. We used the same infrastructure that powers
many Google AI projects including Alpha Go and Google Photo as
well as Google Cloud”.
Stevens says: “Lessons should have been learned from the
warnings about similar attacks against SHA-1’s predecessor MD5,
such as the creation of a rogue Certification Authority in 2009
by an international team I was part of, and an attack by nation
states in 2012 to craft malicious Windows updates to infect
targeted machines in the Middle-East for espionage, which I
showed to be a – then unknown – cryptographic attack variant.”
In the fall of 2015 Stevens, together with two co-authors,
warned that finding a SHA-1 collision might cost around
$75K-$120K by exploiting low-cost GPU resources on Amazon EC2,
which was significantly cheaper than previously expected.
Forged PDF documents
The team’s collision is used to create two different PDF files
with the same SHA-1 fingerprint but chosen distinct visible
contents, for instance two contracts with substantially
different financial fees. Following the responsible disclosure
process, the team will wait 90 days before releasing a PDF
generator that will allow anyone to create lookalike PDF
document pairs of their choice using the team’s collision.
To help prevent misuse by such forged PDF documents, the team
offers a free online tool to scan for SHA-1 collisions in
documents, which is based on Stevens’ 2013 counter-cryptanalysis
technique to detect whether any given single file has been
created with a cryptanalytic collision attack. It can be found
on: https://shattered.io. The same protection for PDF documents
is now automatic for Gmail and Google Drive users. To defend
against SHA-1 collision attacks systems must migrate to SHA-2 or
SHA-3. In the case of HTTPS, the effort to move from SHA-1
certificates to SHA-2 certificates began in 2015. And starting
this year browsers will mark SHA-1 based certificates as
insecure. Similarly, backup systems and document signatures
systems should be transitioned to SHA-2.
result is the product of a long term collaboration between the
Cryptology Group at Centrum Wiskunde & Informatica – the
national research institute for mathematics and computer science
in the Netherlands - and the Google Research Security, Privacy
and Anti-abuse Group. Two years ago Marc Stevens and Elie
Bursztein, leader of Google’s anti-abuse research team, began
collaborating on making Marc’s cryptanalytic attacks against
SHA-1 practical using Google infrastructure. Since then many CWI
researchers and Googlers have helped make this project possible,
including Pierre Karpman (CWI) who worked on the cryptanalysis
and prototype GPU implementation, and from Google Ange Albertini
who developed the PDF attack, Yarik Markov who took care of the
distributed GPU code and Clement Blaisse who oversaw the
reliability of the computations.