Nytro Posted May 14, 2019 Report Share Posted May 14, 2019 From Collisions to Chosen-Prefix Collisions Application to Full SHA-1 Ga ̈etan Leurent1and Thomas Peyrin2,31Inria, France2Nanyang Technological University, Singapore3Temasek Laboratories, Singaporegaetan.leurent@inria.fr,thomas.peyrin@ntu.edu.sg Abstract.A chosen-prefix collision attack is a stronger variant of acollision attack, where an arbitrary pair of challenge prefixes are turnedinto a collision. Chosen-prefix collisions are usually significantly harderto produce than (identical-prefix) collisions, but the practical impact ofsuch an attack is much larger. While many cryptographic constructionsrely on collision-resistance for their security proofs, collision attacks arehard to turn into a break of concrete protocols, because the adversary haslimited control over the colliding messages. On the other hand, chosen-prefix collisions have been shown to break certificates (by creating arogue CA) and many internet protocols (TLS, SSH, IPsec).In this article, we propose new techniques to turn collision attacks intochosen-prefix collision attacks. Our strategy is composed of two phases:first a birthday search that aims at taking the random chaining variabledifference (due to the chosen-prefix model) to a set of pre-defined tar-get differences. Then, using a multi-block approach, carefully analysingthe clustering effect, we map this new chaining variable difference to acolliding pair of states using techniques developed for collision attacks.We apply those techniques toMD5andSHA-1, and obtain improved at-tacks. In particular, we have a chosen-prefix collision attack againstSHA-1with complexity between 266.9and 269.4(depending on assump-tions about the cost of finding near-collision blocks), while the best-known attack has complexity 277.1. This is within a small factor of thecomplexity of the classical collision attack onSHA-1(estimated as 264.7).This represents yet another warning that industries and users have tomove away from usingSHA-1as soon as possible. Sursa: https://eprint.iacr.org/2019/459.pdf Quote Link to comment Share on other sites More sharing options...