Attaque de collisions

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En cryptographie, une attaque de collisions est une attaque sur une fonction de hachage cryptographique qui tente de trouver deux entrées de cette fonction qui produisent le même résultat (appelé valeur de hachage), c'est-à-dire qui résultent en une collision. Dans une attaque de collisions, contrairement à une attaque d'image inverse (en) (en anglais : preimage attack), la valeur de hachage n'est pas précisée.

Il existe deux types principaux d'attaques de collisions :

  • l'attaque de collisions classique : cette attaque consiste à trouver deux messages m1 et m2 différents, tels que hachage (m1) = hachage (m2) ;
  • l'attaque de collisions avec préfixes choisis : étant donné deux préfixes différents P1 et P2, cette attaque consiste à trouver deux suffixes S1 et S2 tels que hachage (P1 ∥ S1) = hachage ( P2 ∥ S2) (où ∥ est l'opération de concaténation).

Attaque de collisions avec préfixes choisis[modifier | modifier le code]

Une variante de l'attaque de collisions classique est une attaque de collisions avec préfixes choisis qui est spécifique aux fonctions de hachage de Merkle-Damgaård. Dans ce cas, l'attaquant choisit deux documents différents, puis concatène deux valeurs calculées différentes aux documents de façon à ce que les deux documents résultants aient la même valeur de hachage. Cette attaque est beaucoup plus puissante qu’une attaque de collisions classique.

En 2007, un article rapportait qu'une attaque de collisions avec préfixes choisis avait été réussie contre la fonction de hachage cryptographique MD5. L'attaque nécessitait environ 250 évaluations de la fonction MD5. Le même article mentionnait aussi deux certificats X.509 pour différents noms de domaine ayant la même valeur de hachage. Cela signifie qu'une autorité de certification pourrait être invitée à signer un certificat pour un domaine, puis ce certificat pourrait être utilisé pour usurper l'identité d'un autre domaine[1].

Une attaque de collisions avec préfixes choisis contre la fonction de hachage cryptographique MD5 dans le monde réel a été publiée en décembre 2008 quand un groupe de chercheurs en sécurité a publié un certificat de signature X.509 forgé qui pourrait être utilisé pour usurper l'identité d'une autorité de certification. Cela signifie qu'un attaquant pourrait usurper l'identité d'un site Web sécurisé SSL comme un homme du milieu, trompant ainsi la validation des certificats intégrée dans tous les navigateurs Web pour protéger le commerce électronique. Le certificat contrefait pouvait ne pas être révocable par les autorités de certification légitimes et pouvait aussi avoir une date d'expiration arbitraire. Même s'il était connu que MD5 était très faible depuis 2004[2], les autorités de certification étaient toujours prêtes à signer des certificats MD5 (vérifié en décembre 2008)[3].

En 2012, le malware Flame utilisait avec succès une variante d'une attaque de collisions avec préfixes choisis pour usurper une signature de code de Microsoft qui utilisait encore l'algorithme MD5[4],[5].

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Collision attack » (voir la liste des auteurs).

  1. (en) Marc Stevens, Arjen Lenstra et Benne de Weger, « Chosen-prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities »,‎
  2. (en) Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, Cryptology ePrint Archive Report 2004/199, 16 Aug 2004, revised 17 Aug 2004. Retrieved July 27, 2008.
  3. (en) Alexander Sotirov, « Creating a rogue CA certificate », 12 30 2008
  4. (en) « Microsoft releases Security Advisory 2718704 », Microsoft, (consulté le 4 juin 2012)
  5. (en) Marc Stevens, « CWI Cryptanalist Discovers New Cryptographic Attack Variant in Flame Spy Malware », Centrum Wiskunde & Informatica, (consulté le 9 juin 2012)