Deux chaînes différentes peuvent-elles générer le même code de hachage MD5?
pour chacun de nos actifs binaires, nous produisons 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?
11 réponses
pour un ensemble de milliards d'actifs, les chances de collisions aléatoires sont négligeables -- rien qui devrait vous inquiéter. Si l'on considère le birthday paradox , avec un ensemble de 2^64 (soit 18.446.744.073.709.551.616) actifs, la probabilité de collision un seul MD5 à l'intérieur de cet ensemble est de 50%. À cette échelle, vous battriez probablement Google en termes de capacité de stockage.
cependant, parce que la fonction de hachage MD5 a été cassée (elle est vulnérable à une collision attack ), tout attaquant déterminé peut produire 2 Biens de collision dans une valeur de quelques secondes de la puissance CPU. Donc, si vous voulez utiliser MD5, assurez-vous qu'un tel attaquant ne compromettrait pas la sécurité de votre application!
aussi, considérer les ramifications si un attaquant pourrait forger une collision à un actif existant dans votre base de données. Bien qu'il n'y ait pas de telles attaques connues ( preimage attacks ) contre MD5 (à partir de 2011), cela pourrait devenir possible en prolongeant les recherches actuelles sur les attaques de collision.
si cela s'avère être un problème, je suggère de regarder la série SHA-2 de fonctions de hachage (SHA-256, SHA-384 et SHA-512). L'inconvénient est qu'il est légèrement plus lente et plus hachage de sortie.
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 cordes (de n'importe quelle longueur), cependant, est certainement illimité donc, il s'ensuit logiquement qu'il doit être collisions.
Oui, c'est possible. Il s'agit en fait d'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.
Oui, bien sûr: les hachures MD5 ont une longueur finie, mais il y a 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 la chaîne hex:
$ 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 cordes sont très similaires, il est donc difficile de trouver la différence entre eux.
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: collision à bloc simple pour MD5 , 2012; il explique sa méthode, avec le code source ( lien alternatif au papier ).
un autre essai:
$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
756f3044edf52611a51a8fa7ec8f95e273f21f82 -
cee9a457e790cf20d4bdaa6d69f01e41
$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
6d5294e385f50c12745a4d901285ddbffd3842cb -
cee9a457e790cf20d4bdaa6d69f01e41
SHA-1 somme différente, le 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: construire des Collisions MD5 En utilisant un seul bloc de Message , 2010.
Related:
Oui, c'est possible. Il est appelé un collision de hachage .
cela dit, des algorithmes tels que MD5 sont conçus pour minimiser la probabilité d'une collision.
L'entrée Wikipédia sur MD5 explique certaines vulnérabilités dans MD5, dont vous devriez être conscient.
Juste pour être plus informatif.
D'un point de vue mathématique, les fonctions de hachage ne sont pas injective .
Cela signifie qu'il n'est pas un 1 à 1 (mais d'une façon) relation entre le jeu et le résultat.
EDIT: pour être complet injective fonctions de hachage existe: ça s'appelle "1519110920 Parfait" hachage .
Oui, ça l'est! La Collision sera être une possibilité (bien que le risque est très faible). Sinon, vous auriez une méthode de compression assez efficace!
EDIT : comme le dit Konrad Rudolph: un ensemble potentiellement illimité d'entrées converties en un ensemble fini de sortie (32 caractères hexadécimaux) will se traduit par un nombre infini de collisions.
Comme d'autres personnes l'ont dit, oui, il peut y avoir des collisions entre deux entrées différentes. Cependant, dans votre cas, je ne vois pas de problème. Je doute fortement que vous rencontriez des collisions-J'ai utilisé MD5 pour relever les empreintes de centaines de milliers de fichiers image d'un certain nombre de formats image (JPG, bitmap, PNG, raw) lors d'un précédent travail et je n'ai pas eu de collision.
cependant, si vous essayez d'identifier une sorte de données, peut-être que vous pourriez utiliser deux algorithmes de hachage - les chances d'une entrée résultant dans la même sortie de deux algorithmes différents est quasi impossible.
je pense que nous devons faire attention à choisir l'algorithme de hachage conformément à nos exigences, 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 hash dans mon projet. J'utilise l'enveloppe de 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
il a causé un problème de cache très délicat dans le système, puis j'ai finalement trouvé que c'est une collision de hachage.
je me rends compte que c'est vieux, mais j'ai pensé que je contribuerais ma solution. Il existe 2^128 combinaisons de hachage possibles. Et donc 2^64 probabilité d'un paradoxe d'anniversaire. Bien que la solution ci-dessous n'éliminera pas la possibilité de collisions, elle réduira sûrement le risque de façon très importante.
2^64 = 18,446,744,073,709,500,000 possible combinations
ce que j'ai fait est que j'ai mis quelques hachures ensemble basées sur la chaîne de saisie pour obtenir une chaîne résultante beaucoup plus longue que vous considérez votre hachage...
donc mon pseudo-code pour ceci est:
Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string))
, c'est-à-dire à l'improbabilité pratique d'une collision. Mais si vous voulez être super paranoïaque et ne pouvez pas que cela arrive, 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 donne maintenant beaucoup plus de jeu avec la façon dont rarement vous tomberez dans une collision. Au point que je pourrais supposer l'impossibilité dans tous réaliste les sens du terme.
Pour mon bien, je pense que la possibilité d'une collision est suffisamment rares que je vais réfléchir à pas "infaillible" mais tellement improbable qu'il convient à la nécessité.
maintenant les combinaisons possibles augmente considérablement. Tandis que vous pourriez passer un long moment sur combien de combinaisons cela pourrait vous obtenir, je dirai en théorie il vous atterrit beaucoup plus que le nombre cité ci-dessus de
2^64 (or 18,446,744,073,709,551,616)
Probablement par une centaine de chiffres. Le max théorique que cela pourrait vous donner serait
nombre Possible de chaînes résultantes:
528294531135665246352339784916516606518847326036121522127960709026673902556724859474417255887657187894674394993257128678882347559502685537250538978462939576908386683999005084168731517676426441053024232908211188404148028292751561738838396898767036476489538580897737998336