International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Gaëtan Leurent
Thomas Peyrin
Download:
DOI: 10.1007/978-3-030-17659-4_18
Search ePrint
Search Google
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 break of concrete protocols, because the adversary has a limited control over the colliding messages. On the other hand, chosen-prefix collisions have been shown to break certificates (by creating a rogue CA) and many internet protocols (TLS, SSH, IPsec).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.
Video from EUROCRYPT 2019
Video provided under Creative Commons / CC BY 3.0
BibTeX
@article{eurocrypt-2019-29396,
  title={From Collisions to Chosen-Prefix Collisions Application to Full SHA-1},
  booktitle={Advances in Cryptology – EUROCRYPT 2019},
  series={Advances in Cryptology – EUROCRYPT 2019},
  publisher={Springer},
  volume={11478},
  pages={527-555},
  doi={10.1007/978-3-030-17659-4_18},
  author={Gaëtan Leurent and Thomas Peyrin},
  year=2019
}