Paper 2019/459

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

Gaëtan Leurent and Thomas Peyrin

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 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 SHA1, and obtain improved attacks. In particular, we have a chosen-prefix collision attack against SHA1 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 SHA1 (estimated as $2^{64.7}$). This represents yet another warning that industries and users have to move away from using SHA1 as soon as possible.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2019
Keywords
hash functioncryptanalysischosen-prefix collisionSHA1MD5
Contact author(s)
gaetan leurent @ inria fr
thomas peyrin @ ntu edu sg
History
2019-05-22: revised
2019-05-10: received
See all versions
Short URL
https://ia.cr/2019/459
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/459,
      author = {Gaëtan Leurent and Thomas Peyrin},
      title = {From Collisions to Chosen-Prefix Collisions - Application to Full {SHA}-1},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/459},
      year = {2019},
      url = {https://eprint.iacr.org/2019/459}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.