Deux chaînes différentes peuvent-elles générer le même code de hachage MD5?

Pour chacun de nos actifs binaires, nous générons un hachage MD5. Ceci est utilisé pour vérifier si un certain actif binaire est déjà dans notre application. Mais est-il possible que deux actifs binaires différents génèrent le même hachage MD5. Est-il donc possible que deux chaînes différentes génèrent le même hachage MD5?

Pour un ensemble de plusieurs milliards d'actifs, les chances de collisions aléatoires sont négligeables - rien dont vous devriez vous inquiéter. Compte tenu du paradoxe anniversaire , étant donné un ensemble de 2 ^ 64 (ou 18 446 744 073 709 551 616) actifs, la probabilité d' une seule collision MD5 dans cet ensemble est de 50%. À cette échelle, vous battriez probablement Google en termes de capacité de stockage.

Cependant, comme la fonction de hachage MD5 a été interrompue (elle est vulnérable à une attaque par collision ), tout attaquant déterminé peut produire 2 actifs en collision en quelques secondes de puissance CPU. Donc si vous souhaitez utiliser MD5, assurez-vous qu'un tel attaquant ne compromettrait pas la sécurité de votre application!

Pensez également aux ramifications si un attaquant pouvait créer une collision avec un actif existant dans votre base de données. Bien qu'il n'y ait pas d'attaques connues (attaques de pré-image ) contre MD5 (à partir de 2011), cela pourrait devenir possible en étendant les recherches actuelles sur les attaques par collision.

Si cela s'avère être un problème, je suggère de regarder la série de fonctions de hachage SHA-2 (SHA-256, SHA-384 et SHA-512). L'inconvénient est qu'il est légèrement plus lent et a une sortie de hachage plus longue.

MD5 est une fonction de hachage - donc oui, deux chaînes différentes peuvent absolument générer des codes MD5 en collision.

En particulier, notez que les codes MD5 ont une longueur fixe, de sorte que le nombre possible de codes MD5 est limité. Le nombre de chaînes (de n'importe quelle longueur), cependant, est définitivement illimité, il s'ensuit donc logiquement qu'il doit y avoir des collisions.

Oui c'est possible. C'est en fait un problème d'anniversaire . Cependant, la probabilité que deux chaînes choisies au hasard aient le même hachage MD5 est très faible.

Voir ceci et ces questions pour des exemples.

Oui, bien sûr: les hachages MD5 ont une longueur finie, mais il existe un nombre infini de chaînes de caractères possibles qui peuvent être hachées MD5.

Oui, il est possible que deux chaînes différentes puissent générer le même code de hachage MD5.

Voici un test simple utilisant un message binaire très similaire dans une chaîne hexadécimale:

$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c6b384c4968b28812b676b49d40c09f8af4ed4cc  -
008ee33a9d58b51cfeb425b0959121c9

$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c728d8d93091e9c7b87b43d9e33829379231d7ca  -
008ee33a9d58b51cfeb425b0959121c9

Ils génèrent une somme SHA-1 différente, mais la même valeur de hachage MD5. Deuxièmement, les chaînes sont très similaires, il est donc difficile de trouver la différence entre elles.

La différence peut être trouvée par la commande suivante:

$ diff -u <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2 | fold -w2) <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2 | fold -w2)
--- /dev/fd/63  2016-02-05 12:55:04.000000000 +0000
+++ /dev/fd/62  2016-02-05 12:55:04.000000000 +0000
@@ -33,7 +33,7 @@
 af
 bf
 a2
-00
+02
 a8
 28
 4b
@@ -53,7 +53,7 @@
 6d
 a0
 d1
-55
+d5
 5d
 83
 60

L'exemple de collision ci-dessus est tiré de Marc Stevens: Single-block collision for MD5 , 2012; il explique sa méthode, avec le code source ( lien alternatif vers l'article ).

Un autre test:

$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
756f3044edf52611a51a8fa7ec8f95e273f21f82  -
cee9a457e790cf20d4bdaa6d69f01e41

$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
6d5294e385f50c12745a4d901285ddbffd3842cb  -
cee9a457e790cf20d4bdaa6d69f01e41

Somme SHA-1 différente, même hachage MD5.

La différence est dans un octet:

$ diff -u <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2) <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2)
--- /dev/fd/63  2016-02-05 12:56:43.000000000 +0000
+++ /dev/fd/62  2016-02-05 12:56:43.000000000 +0000
@@ -19,7 +19,7 @@
 03
 65
 9e
-70
+74
 4f
 85
 34
@@ -41,7 +41,7 @@
 a3
 f4
 15
-5c
+dc
 bb
 86
 07

L'exemple ci-dessus est adapté de Tao Xie et Dengguo Feng: Construct MD5 Collisions Using Just A Single Block Of Message , 2010.

En relation:

• Existe-t-il deux chaînes connues qui ont la même valeur de hachage MD5? chez Crypto.SE

Oui c'est possible. Cela s'appelle une collision Hash .

Cela dit, des algorithmes tels que MD5 sont conçus pour minimiser la probabilité d'une collision.

L'entrée Wikipedia sur MD5 explique certaines vulnérabilités dans MD5, dont vous devez être conscient.

Juste pour être plus informatif. D'un point de vue mathématique, les fonctions de hachage ne sont pas injectives .
Cela signifie qu'il n'y a pas de relation 1 à 1 (mais à sens unique) entre le jeu de départ et celui qui en résulte.

Bijection sur wikipedia

EDIT: pour être complet, il existe des fonctions de hachage injectives: cela s'appelle Perfect hashing .

Oui, ça l'est! Une collision sera une possibilité (bien que le risque soit très faible). Sinon, vous auriez une méthode de compression assez efficace!

EDIT : Comme Konrad Rudolph dit: Un ensemble potentiellement illimité d'entrée converti en un ensemble fini de sortie (32 caractères hexadécimaux) seront les résultats dans un nombre infini de collisions.

Comme d'autres l'ont dit, oui, il peut y avoir des collisions entre deux entrées différentes. Cependant, dans votre cas d'utilisation, je ne vois pas cela comme un problème. Je doute fortement que vous rencontriez des collisions - j'ai utilisé MD5 pour prendre des empreintes digitales de centaines de milliers de fichiers image d'un certain nombre de formats d'image (JPG, bitmap, PNG, raw) lors d'un travail précédent et je n'ai pas eu de collision .

Cependant, si vous essayez d'empreinte digitale d'un type de données, vous pourriez peut-être utiliser deux algorithmes de hachage - la probabilité qu'une entrée aboutisse à la même sortie de deux algorithmes différents est presque impossible.

Je me rends compte que c'est vieux, mais j'ai pensé que j'apporterais ma solution. Il existe 2 ^ 128 combinaisons de hachage possibles. Et donc une probabilité de 2 ^ 64 d'un paradoxe d'anniversaire. Bien que la solution ci-dessous n'élimine pas la possibilité de collisions, elle réduira certainement le risque de manière très substantielle.

2^64 = 18,446,744,073,709,500,000 possible combinations

Ce que j'ai fait est de rassembler quelques hachages en fonction de la chaîne d'entrée pour obtenir une chaîne résultante beaucoup plus longue que vous considérez comme votre hachage ...

Donc, mon pseudo-code pour cela est:

Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string))

C'est à l'improbabilité pratique d'une collision. Mais si vous voulez être super paranoïaque et que cela ne peut pas arriver, et l'espace de stockage n'est pas un problème (pas plus que les cycles de calcul) ...

Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string)) 
         & Hash(Reverse(SpellOutLengthWithWords(Length(string)))) 
         & Hash(Rotate13(string)) Hash(Hash(string)) & Hash(Reverse(Hash(string)))

D'accord, ce n'est pas la solution la plus propre, mais cela vous permet désormais de jouer beaucoup plus avec la fréquence à laquelle vous rencontrez une collision. Au point que je pourrais supposer l'impossibilité dans tous les sens réalistes du terme.

Pour moi, je pense que la possibilité d'une collision est assez peu fréquente pour que je considère que cela n'est pas "infaillible", mais si peu probable qu'il se produise que cela convient au besoin.

Maintenant, les combinaisons possibles augmentent considérablement. Bien que vous puissiez passer beaucoup de temps sur le nombre de combinaisons que cela pourrait vous apporter, je dirai qu'en théorie, cela vous rapporte significativement plus que le nombre cité ci-dessus de

2^64 (or 18,446,744,073,709,551,616) 

Probablement par une centaine de chiffres de plus environ. Le maximum théorique que cela pourrait vous donner serait

Nombre possible de chaînes résultantes:

528294531135665246352339784916516606518847326036121522127960709026673902556724859474417255887657187894674394993257128678882347559502685537250538978462939576908386683999005084168731517676426441053024232908211188404148028292751561738838396898767036476489538580897737998336

Je pense que nous devons faire attention en choisissant l'algorithme de hachage selon nos besoins, car les collisions de hachage ne sont pas aussi rares que je m'y attendais. J'ai récemment trouvé un cas très simple de collision de hachage dans mon projet. J'utilise le wrapper Python de xxhash pour le hachage. Lien: https://github.com/ewencp/pyhashxx

s1 = 'mdsAnalysisResult105588'
s2 = 'mdsAlertCompleteResult360224'
pyhashxx.hashxx(s1) # Out: 2535747266
pyhashxx.hashxx(s2) # Out: 2535747266

Cela a causé un problème de mise en cache très délicat dans le système, puis j'ai finalement trouvé qu'il s'agissait d'une collision de hachage.