1. From Collisions to Chosen-Prefix Collisions - Application to Full SHA-1 2019 Attacks Cryptanalysis Eurocrypt Hashing
    Gaëtan Leurent and Thomas Peyrin
    [View PDF on eprint.iacr.org]
    [Show BibTex Citation]

    @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, Report 2019/459},
    year = {2019},
    note = {\url{https://eprint.iacr.org/2019/459}},
    }

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 266.9 and 269.4 (depending on assumptions about the cost of finding near-collision blocks), while the best-known attack has complexity 277.1. This is within a small factor of the complexity of the classical collision attack on SHA1 (estimated as 264.7). This represents yet another warning that industries and users have to move away from using SHA1 as soon as possible.

  1.