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 and (depending on assumptions about the cost of finding near-collision blocks), while the best-known attack has complexity . This is within a small factor of the complexity of the classical collision attack on SHA1 (estimated as ). 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.