PRESS RELEASE
From: Centrum Wiskunde & Informatica (CWI) in Amsterdam, the Netherlands,
Google Research in the U.S.A. and Switzerland
Thursday 23 February 2017
CWI and Google announce first collision for Industry Security Standard SHA-1
'Industry deprecation proved to be too slow'
Today, researchers at the Dutch research institute CWI and Google jointly
announce that they 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".
Signature forgeries
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.
Cryptanalytic advances
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".
Historic lessons
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.
Defense
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.
The team
This 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.
About CWI
Founded in 1946, Centrum Wiskunde & Informatica (CWI) is the national research
institute for mathematics and computer science in the Netherlands. It is
located at Amsterdam Science Park and is part of the Netherlands Organisation
for Scientific Research (NWO). The institute is internationally focused and
renowned. Over 150 researchers conduct pioneering research and share their
acquired knowledge with society. Over 30 researchers are also employed as
professors at universities. The institute has generated twenty-four spin-off
companies.
The groundbreaking research by Marc Stevens was done in the CWI Cryptology
group, which is headed by Prof. Ronald Cramer. This group investigates
fundamental cryptographic questions from a broad scientific perspective,
particularly from mathematics, computer science and physics.
----
Note for the press, not for publication:
More details about the SHA1 attack, how to detect it and the research paper
detailing the attack is available at https://shattered.io. For questions please ;
contact the combined research team, e-mail info@xxxxxxxxxxxx.
More information about dr. ir. Marc Stevens' work:
- 2015 SHA-1 collision lower cost estimation & warning:
https://sites.google.com/site/itstheshappening/; paper: Freestart collision for ;
full SHA-1, Marc Stevens, Pierre Karpman, Thomas Peyrin, EUROCRYPT 2016,
Lecture Notes in Computer Science, vol. 9665, Springer, 2016, pp. 459-483
- 2013 counter-cryptanalysis
https://www.cwi.nl/news/2013/cwi-releases-software-detection-of-forged-digital-signatures;
paper: Counter-cryptanalysis, Marc Stevens, CRYPTO 2013, Lecture Notes in
Computer Science, vol. 8042, Springer, 2013, pp. 129-146 – Winner of the CRYPTO
2013 Best Young Researcher Paper Award
- 2012 SHA-1 collision cost estimation & warning
https://www.schneier.com/blog/archives/2012/10/when_will_we_se.html; paper: New ;
collision attacks on SHA-1 based on optimal joint local-collision analysis,
Marc Stevens, EUROCRYPT 2013, Lecture Notes in Computer Science, vol. 7881,
Springer, 2013, pp. 245-261
- 2012 MD5 Flame:
https://www.cwi.nl/news/2012/cwi-cryptanalist-discovers-new-cryptographic-attack-variant-in-flame-spy-malware;
see ‘Counter-cryptanalysis’ and its follow-up paper: Reverse-engineering of
the cryptanalytic attack used in the Flame super-malware, Max Fillinger, and
Marc Stevens, ASIACRYPT 2015, Lecture Notes in Computer Science, vol. 9453,
Springer, 2015, pp. 586-611.
https://arstechnica.com/security/2012/06/flame-crypto-breakthrough/
- 2009 MD5 Rogue Certification Authority:
https://www.win.tue.nl/hashclash/rogue-ca; paper: Short chosen-prefix ;
collisions for MD5 and the creation of a rogue CA certificate, Marc Stevens,
Alexander Sotirov, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne
Osvik, Benne de Weger, CRYPTO 2009, Lecture Notes in Computer Science, vol.
5677, Springer, 2009, pp. 55-69 – Winner of the CRYPTO 2009 Best Paper Award.
- Marc Stevens of the CWI Cryptology research group has been awarded the Google
Security Privacy and Anti-abuse Applied Award, news item of 19 December 2016:
https://www.cwi.nl/news/2016/cryptology-researcher-marc-stevens-awarded-google-research-prize
- Handled by: Annette Kik, communications advisor at CWI, Annette.Kik@xxxxxx,
phone +31 (0)20 – 592 4248 (Mon, Wed, Thu) or +31 (0)6 51574891, Centrum
Wiskunde & Informatica, Science Park 123, NL-1098 XG Amsterdam, The
Netherlands, www.cwi.nl and by Aaron Stein, Security and Privacy Global
Communications and Public Affairs at Google, e-mail steina@xxxxxxxxxx.
