We Have Broken SHA-1 in Practice

By Shattered.io
Hosted at: EmbeddedSw - Security News

This industry cryptographic hash function standard is used for digital signatures and file integrity verification, and protects a wide spectrum of digital assets, including credit card transactions, electronic documents, open-source software repositories and software updates.

It is now practically possible to craft two colliding PDF files and obtain a SHA-1 digital signature on the first PDF file which can also be abused as a valid signature on the second PDF file.

For example, by crafting the two colliding PDF files as two rental agreements with different rent, it is possible to trick someone to create a valid signature for a high-rent contract by having him or her sign a low-rent contract.

Isn't SHA-1 deprecated?

Today, many applications still rely on SHA-1, even though theoretical attacks have been known since 2005, and SHA-1 was officially deprecated by NIST in 2011. We hope our practical attack on SHA-1 will increase awareness and convince the industry to quickly move to safer alteratives, such as SHA-256.

What types of systems are affected?

Any application that relies on SHA-1 for digital signatures, file integrity, or file identification is potentially vulnerable. These include:

Are TLS/SSL certificates at risk?

Any Certification Authority abiding by the CA/Browser Forum regulations is not allowed to issue SHA-1 certificates anymore. Furthermore, it is required that certificate authorities insert at least 64 bits of randomness inside the serial number field. If properly implemented this helps preventing a practical exploitation.

Is GIT affected?

GIT strongly relies on SHA-1 for the identification and integrity checking of all file objects and commits. It is essentially possible to create two GIT repositories with the same head commit hash and different contents, say a benign source code and a backdoored one. An attacker could potentially selectively serve either repository to targeted users. This will require attackers to compute their own collision.

Is SVN affected?

Yes - please exercise care, as SHA-1 colliding files are currently breaking SVN repositories. Subversion servers use SHA-1 for deduplication and repositories become corrupted when two colliding files are committed to the repository. This has been discovered in WebKit's Subversion repository and independently confirmed by us. We noticed that in some cases, due to the corruption, further commits are blocked.

How do I patch/upgrade my system?

Consider using safer alternatives, such as SHA-256, or SHA-3.

How do I detect this attack?

You can use the online tool above to submit files and have them checked for a cryptanalytic collision attack on SHA-1. The code behind this was developed by Marc Stevens (CWI) and Dan Shumow (Microsoft) and is publicly available on GitHub.

It is based on the concept of counter-cryptanalysis and it is able to detect known and unknown SHA-1 cryptanalytic collision attacks given just a single file from a colliding file pair.

How widespread is this?

As far as we know our example collision is the first ever created.

Has this been abused in the wild?

Not as far as we know.

Is Hardened SHA-1 vulnerable?

No, SHA-1 hardened with counter-cryptanalysis (see 'how do I detect the attack') will detect cryptanalytic collision attacks. In that case it adjusts the SHA-1 computation to result in a safe hash. This means that it will compute the regular SHA-1 hash for files without a collision attack, but produce a special hash for files with a collision attack, where both files will have a different unpredictable hash.

Who is capable of mounting this attack?

This attack required over 9,223,372,036,854,775,808 SHA1 computations. This took the equivalent processing power as 6,500 years of single-CPU computations and 110 years of single-GPU computations.

How does this attack compare to the brute force one?

The SHAttered attack is 100,000 faster than the brute force attack that relies on the birthday paradox. The brute force attack would require 12,000,000 GPU years to complete, and it is therefore impractical.

Who is the team behind this research?

This result is the product of a long term collaboration between the Cryptology Group at Centrum Wiskunde & Informatica (CWI) - 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, who leads the Google's anti-abuse research team, began collaborating on making Marc's cryptanalytic attacks against SHA-1 practical by leveraging Google expertise and infrastructure. Since then many CWI researchers and Googlers have helped make this project possible, including Pierre Karpman 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, Alex Petit-Bianco implemented the collision detector to protect Google users, Luca Invernizzi who created the online file checker, and Clement Blaisse who oversaw the reliability of the computations.