This article discusses recent warnings that a chosen-prefix collision attack on SHA-1 is now practical and cost-effective for attackers.
A recent report titled “SHA-1 is a Shambles” by Gaetan Leurent of France and Thomas Peyrin of Singapore shows that a chosen-prefix (CP) collision attack on SHA-1, which was considered, in theory, too difficult to practically implement just a few short years ago is now practical and cost-effective for attackers. In their research, Leurent and Peyrin were able to exhibit a practical chosen-prefix collision attack upon SHA-1.
In the attack, the authors were able to perform a CP collision computation at what they considered a reasonable cost of 75k US$. They surmise that over time, that cost will continue to decrease to the point that it will become reasonably inexpensive for hackers to implement.
What follows is what users need to know to prevent their systems and processes from being vulnerable to a chosen-prefix collision attack on SHA-1.
How Chosen-Prefix Collision Attacks Work
For a quick review, SHA-1 is a 160-bit hash function. It follows the Merkle-Damgard paradigm. In a “random” collision attack, the attacker must first find a collision. The challenge in that is because this is done while starting from a random difference in the internal state with a prefix pair that is not under the attacker’s control. This prevents the attacker from directly using collision search techniques for SHA-1 while requiring that he somehow erase that random difference. This is both resource and time-consuming.
The chosen-prefix collision attack is a more practical and powerful approach. What it does is significantly reduce the complexity involved with finding a collision to exploit. Leurent and Peyrin were able to accomplish this by building colliding messages with two arbitrary prefixes. This technique was more of a threat to real protocols. In the first practical chosen-prefix collision attack, there was success in accomplishing a PGP/GnuPG impersonation attack. As a result, it is now known that attacks that have been practical on MD5 are also now practical on SHA-1.
What Implications and Risks Were Discovered with the Chosen-Prefix Collision?
Despite being broken since 2004, SHA-1 remains supported in such secure channel protocols like TLS and SSH and is used for some connections, PGP identity certifications, and the GIT versioning system is built upon it. There may also be a great number of proprietary systems still using SHA-1 but determining what systems and how many would be difficult.
While chosen-prefix collisions have been found to not threaten all the usages of SHA-1, there are several that are directly affected, including:
- TLS and SSH connections that use SHA-1 signatures for handshake authentication could be vulnerable to a SLOTH attack as the result of a quickly-generated chosen-prefix collision.
- When trusted third parties have used SHA-1 to sign identity certificates, there is a risk that PGP identities could be impersonated.
- If certificate authorities have issued SHA-1 certificates with predictable serial numbers, it is possible that X.509 certificates could be broken.
Recommended Actions to Prevent Chosen-Prefix Collisions
Leurent and Peyrin strongly recommend that users remove SHA-1 support from their systems to prevent downgrade attacks even if there is no direct evidence that there are weaknesses that could be exploited.
It is now unadvisable for SHA-1 to be used in security protocols where there is an expectation that the hash function will provide some level of collision resistance.
Using SHA-1 for signatures, certificates, or authenticating handshake messages in SSH or TLS is now much too risky to continue to justify its usage.
References
- Selected Articles on the SHA-1 Attack(2020 - today), by Edlyn Teske, Dawn M. Turner and more
- Selected Articles onCrypto-Agility(2017-today), by Dawn M. Turner,Jasmine Henry,Rob Stubbs, Terry Antonand more
- SHA-1 is a Shambles First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust(2020), by Gaëtan Leurent and Thomas Peyrin
- What is Crypto-Agility?(2018) by Jasmine Henry
- Understanding Hardware Security Modules (HSMs)(2017)
by Peter Smirnoff
- Steps to reach crypto agility to get prepared for quantum computing(2019), by Terry Anton
- Achieving Agile Cryptography Management with Crypto Service Gateway (CSG)(2019), by Rob Stubbs
- What is a Crypto-Abstraction Layer?(2018), by Chris Allen
- Turning Cryptography into a Service - Part 1(2018), by Rob Stubbs
- Study on Cryptography as a Service (CaaS)by Yudi Prayudi and Tri Kunturo Priyambodo, November 2014.
- Cryptomathic Answers Compliance-Driven Call for Crypto-Agilityby Cryptomathic, May 2018.
