Skip to Main content Skip to Navigation
Conference papers

From Collisions to Chosen-Prefix Collisions: Application to Full SHA-1

Abstract : A chosen-prefix collision attack is a stronger variant of a collision attack, where an arbitrary pair of challenge prefixes are turned into a collision. Chosen-prefix collisions are usually significantly harder to produce than (identical-prefix) collisions, but the practical impact of such an attack is much larger. While many cryptographic constructions rely on collision-resistance for their security proofs, collision attacks are hard to turn into a break of concrete protocols, because the adversary has limited control over the colliding messages. On the other hand, chosen-prefix collisions have been shown to threaten certificates (by creating a rogue CA) and many internet protocols (TLS, SSH, IKE). In this article, we propose new techniques to turn collision attacks into chosen-prefix collision attacks. Our strategy is composed of two phases: first a birthday search that aims at taking the random chaining variable difference (due to the chosen-prefix model) to a set of pre-defined target differences. Then, using a multi-block approach, carefully analysing the clustering effect, we map this new chaining variable difference to a colliding pair of states using techniques developed for collision attacks. We apply those techniques to MD5 and SHA-1, and obtain improved attacks. In particular, we have a chosen-prefix collision attack against SHA-1 with complexity between 2 66.9 and 2 69.4 (depending on assumptions about the cost of finding near-collision blocks), while the best-known attack has complexity 2 77.1. This is within a small factor of the complexity of the classical collision attack on SHA-1 (estimated as 2 64.7). This represents yet another warning that industries and users have to move away from using SHA-1 as soon as possible.
Document type :
Conference papers
Complete list of metadata

Cited literature [37 references]  Display  Hide  Download

https://hal.inria.fr/hal-02424900
Contributor : Gaëtan Leurent <>
Submitted on : Saturday, December 28, 2019 - 8:20:42 PM
Last modification on : Thursday, January 7, 2021 - 3:38:03 PM
Long-term archiving on: : Sunday, March 29, 2020 - 1:36:19 PM

File

SHA1_EC19.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Gaëtan Leurent, Thomas Peyrin. From Collisions to Chosen-Prefix Collisions: Application to Full SHA-1. Eurocrypt 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 2019, Darmstadt, Germany. pp.527-555, ⟨10.1007/978-3-030-17659-4_18⟩. ⟨hal-02424900⟩

Share

Metrics

Record views

59

Files downloads

520