Attaques des anniversaires et collisions

Dans un groupe de 23 personnes, la probabilité que deux personnes aient la même date d'anniversaire dépasse 50 %. Avec 70 personnes, elle dépasse 99,9 %. Mathématiquement, dans un ensemble de taille N, la probabilité d'une collision dépasse 50 % après environ √N échantillons. C'est la borne des anniversaires.

Pour une fonction de hachage sur n bits, une collision (H(m1) = H(m2), m1 ≠ m2) peut être trouvée avec environ 2^{n/2} essais aléatoires. Pour SHA-256 (256 bits), une collision nécessite environ 2^{128} opérations, ce qui est irréalisable sur le plan informatique. Pour MD5 (128 bits), environ 2^{64}, ce qui est presque réalisable.

Recherche générique de collisions : générer 2^{n/2} messages aléatoires, calculer leurs hachages, les trier selon leur valeur de hachage, puis trouver les doublons. Mémoire O(2^{n/2}). L'algorithme rho (détection de cycles de Floyd) réduit la mémoire à O(1) pour le même coût temporel. La recherche parallèle de collisions de van Oorschot-Wiener réduit le temps grâce au matériel.

Des collisions pratiques de MD5 ont été découvertes par Wang et ses collaborateurs (2004) à l'aide de la cryptanalyse différentielle, et non de l'attaque par anniversaire. Deux messages différents de 1024 bits produisent le même hachage MD5 en quelques secondes. Hertzbleed et les collisions à préfixe choisi permettent de créer des collisions de certificats. MD5 est totalement compromis pour la résistance aux collisions.

Plus puissantes : étant donnés deux préfixes arbitraires P1, P2, trouver des suffixes S1, S2 tels que H(P1||S1) = H(P2||S2). Stevens et ses collaborateurs (2017) ont trouvé des collisions MD5 à préfixe choisi. Cette technique a servi à créer un certificat CA malveillant avec une signature MD5 valide. MD5 a ainsi été retiré de l'utilisation pour les certificats.

SHAttered de Google (2017) : première collision pratique de SHA-1. Deux fichiers PDF différents ayant le même hachage SHA-1. L'opération a nécessité 2^{63.1} compressions SHA-1, soit l'équivalent de 6 500 années de calcul CPU et 110 années de calcul GPU. Coût : environ 110 000 $. Les navigateurs ont cessé d'accepter les certificats SHA-1 en 2017.

Pour les fonctions de hachage de Merkle-Damgård (MD5, SHA-1, SHA-2) : si vous connaissez H(m), vous pouvez calculer H(m||padding||m') sans connaître m. Cela compromet les constructions MAC telles que H(secret||message). Correctif : utilisez HMAC (qui utilise un remplissage interne et externe) ou SHA-3 (construction en éponge, résistante aux extensions de longueur).

Résistance aux collisions : trouver deux messages distincts quelconques ayant le même hachage (effort de 2^{n/2}). Résistance à la seconde préimage : étant donné m, trouver m' ≠ m ayant le même hachage (effort de 2^n). Résistance aux préimages : trouver un message correspondant à un hachage donné (effort de 2^n). La résistance aux collisions est toujours la plus faible.

Si un MAC utilise une fonction de hachage vulnérable aux collisions, un attaquant capable de trouver des collisions dans H peut falsifier des MAC. HMAC-MD5 est considéré comme sûr malgré les collisions de MD5, car la construction de HMAC nécessite des attaques par préimage, et pas seulement des collisions. Toutefois, migrez de HMAC-MD5 pour les nouveaux systèmes.

Joux (2004) : pour les fonctions de hachage de Merkle-Damgård, trouver des collisions à 2^k voies (2^k messages ayant le même hachage) ne nécessite que k fois le travail nécessaire pour trouver une seule collision, et non k fois plus. Cela amplifie les vulnérabilités des hachages concaténés (H1(m)||H2(m) n'est pas aussi robuste qu'on pourrait le penser).

Utilisez SHA-256 ou SHA-3 pour un hachage résistant aux collisions. Évitez MD5 et SHA-1 pour tout usage de sécurité. Pour les MAC : HMAC-SHA-256 ou HMAC-SHA-3. Pour le hachage des mots de passe : Argon2 (et non SHA-2 directement). Utilisez toujours SHA-3 lorsqu'une résistance aux extensions de longueur est nécessaire.

Environ combien d'évaluations de hachage sont nécessaires pour trouver une collision dans une fonction de hachage de n bits ?

Une attaque des anniversaires trouve des collisions de hachage avec un effort de 2^{n/2}. MD5 présente des collisions à préfixe choisi réalisables en pratique ; SHA-1 a été cassé en 2017. Les attaques par extension de longueur compromettent les MAC naïfs H(key||msg). Utilisez SHA-256 ou SHA-3, ainsi que HMAC pour l'authentification des messages. Ensuite : les attaques par rencontre au milieu.