Jump to content
Nytro

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

Recommended Posts

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

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.



×
×
  • Create New...