Attaque de collisions
# Attaque de collisions

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 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

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 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 $2^{50}$ é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.

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, les autorités de certification étaient toujours prêtes à signer des certificats MD5 (vérifié en décembre 2008).

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^,.$

Une attaque de collisions avec préfixes choisis contre la fonction de hachage cryptographique SHA-1 a été publiée en février 2017 par une équipe composée de chercheurs de Google et du CWI, permettant de forger deux documents PDF différents ayant la même valeur de hachage $SHA-1^,.$

