Pourquoi les valeurs de hachage MD5 ne sont-elles pas réversibles?
un concept sur lequel je me suis toujours posé est l'utilisation de fonctions et de valeurs de hachage cryptographique. Je comprends que ces fonctions peuvent générer une valeur de hachage qui est unique et pratiquement impossible à inverser, Mais voici ce que j'ai toujours demandé:
si sur mon serveur, en PHP je produis:
md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"
lorsque vous exécutez cette même chaîne à travers une fonction MD5, vous obtenez le même résultat sur votre installation PHP. Un processus est utilisé pour produire de la valeur, d'une certaine valeur de départ.
cela ne signifie-t-il pas qu'il existe un moyen de déconstruire ce qui se passe et d'inverser la valeur de hachage?
Qu'est-ce qui rend les chaînes résultantes impossibles à retracer?
16 réponses
Le matériau d'entrée peut être une longueur infinie, où la sortie est toujours à 128 bits. Cela signifie qu'un nombre infini de chaînes générera la même sortie.
si vous choisissez un nombre aléatoire et le divisez par 2 mais notez seulement le reste, vous obtiendrez soit un 0 ou un 1 -- pair ou impair, respectivement. Est-il possible de prendre ce 0 ou 1 et d'obtenir le nombre original?
si les fonctions de hachage telles que MD5 étaient réversibles, alors il aurait été un événement de bassin versant dans l'histoire des algorithmes de compression de données! Il est facile de voir que si MD5 étaient réversibles alors des morceaux arbitraires de données de taille arbitraire pourraient être représentés par un simple 128 bits sans aucune perte d'information. Ainsi, vous auriez été capable de reconstruire le message original à partir de 128 bits quelle que soit la taille du message original.
contrairement à ce que soulignent les réponses les plus en vogue ici, le non-injectivité (c'est – à-dire qu'il y a plusieurs chaînes qui se cassent à la même valeur) d'une fonction de hachage cryptographique causée par la différence entre la taille d'entrée grande (potentiellement infinie) et la taille de sortie fixe n'est pas le point important - en fait, nous préférons les fonctions de hachage où ces collisions se produisent aussi rarement que possible.
considérez ceci fonction (en notation PHP, comme la question):
function simple_hash($input) {
return bin2hex(substr(str_pad($input, 16), 0, 16));
}
ceci ajoute quelques espaces, si la chaîne est trop courte, et prend alors les 16 premiers octets de la chaîne, puis l'encode comme hexadécimal. Il a la même taille de sortie qu'un hachage MD5 (32 caractères hexadécimaux, ou 16 octets si on omet la partie bin2hex).
print simple_hash("stackoverflow.com");
cette sortie sera:
737461636b6f766572666c6f772e636f6d
cette fonction a aussi la même propriété de non-injectivité comme le souligne la réponse de Cody pour MD5: nous pouvons passer dans des chaînes de n'importe quelle taille (tant qu'elles s'adaptent à notre ordinateur), et il ne sortira que 32 hex-chiffres. Bien sûr, il ne peut pas être injective.
mais dans ce cas, il est trivial de trouver une chaîne qui correspond au même hachage (il suffit d'appliquer hex2bin sur votre hachage, et vous l'avez). Si votre chaîne originale avait la longueur 16 (comme notre exemple), vous obtiendrez même cette chaîne originale. Rien de ce genre devrait être possible pour MD5, même si vous savez que la longueur de l'entrée était assez courte (sauf en essayant toutes les entrées possibles jusqu'à ce que nous en trouvions une qui correspond, par exemple une attaque par la force brute).
les hypothèses importantes pour une fonction de hachage cryptographique sont:
- il est difficile de trouver une chaîne produisant un hachage donné (résistance au préimage)
- il est difficile de trouver une chaîne différente produisant le même hachage qu'un chaîne donnée (deuxième preimage de la résistance)
- il est difficile de trouver n'importe quelle paire de cordes avec le même hachage (résistance à la collision)
de toute évidence, ma fonction simple_hash ne remplit aucune de ces conditions. (En fait, si nous limitons l'espace d'entrée à "16-byte strings", alors ma fonction devient injective, et donc est même prouvable deuxième préimage résistant et résistant à la collision.)
il existe maintenant collision attaques contre MD5 (par exemple, il est possible de produire une paire de cordes, même avec un préfixe donné, qui ont le même hachage, avec un certain travail, mais pas impossible beaucoup de travail), donc vous ne devriez pas utiliser MD5 pour quelque chose de critique. Il n'y a pas encore d'attaque préimage, mais les attaques vont s'améliorer.
pour répondre à la question actuelle:
Qu'est-ce qui fait de ces fonctions résultant des chaînes impossible à retracer?
ce que MD5 (et d'autres fonctions de hachage basées sur la construction de Merkle-Damgard) font effectivement est d'appliquer un algorithme de chiffrement avec le message comme clé et une valeur fixe comme "texte simple", en utilisant le texte chiffré résultant comme hachage. (Avant cela, l'entrée est capitonnée et divisée en blocs, chacun de ces blocs est utilisé pour chiffrer la sortie du bloc précédent, XORed avec son entrée pour empêcher les calculs inversés.)
les algorithmes de chiffrement modernes (y compris ceux utilisés dans les fonctions de hachage) sont conçus de manière à rendre difficile la récupération de la clé, même si elle est fournie à la fois en clair et en chiffrement (ou même si l'adversaire en choisit un). Ils le font généralement en effectuant de nombreuses opérations de mélange de bits de manière à ce que chaque bit de sortie soit déterminé par chaque bit clé (plusieurs fois) et aussi chaque bit d'entrée. De cette façon, vous pouvez facilement retracer ce qui se passe à l'intérieur si vous connaissez la clé complète et en entrée ou en sortie.
pour les fonctions de hachage de type MD5 et une attaque de préimage (avec une chaîne de caractères hachée à bloc unique, pour faciliter les choses), vous n'avez que les entrées et sorties de votre fonction de cryptage, mais pas la clé (c'est ce que vous recherchez).
la réponse de Cody Brocious est la bonne. À proprement parler, vous ne pouvez pas "inverser" une fonction de hachage parce que beaucoup de chaînes sont mappées sur le même hachage. Notez, cependant, que trouver une "chaîne 151920920" qui est mappée à un hachage donné, ou trouver deux "chaînes 151920920" qui sont mappées au même hachage (i.e. a collision ), serait des percées majeures pour un cryptanalyseur. La grande difficulté de ces deux problèmes est raison pourquoi de bonnes fonctions de hachage sont utiles dans la cryptographie.
MD5 ne crée pas une valeur de hachage unique; le but de MD5 est de produire rapidement une valeur qui change de manière significative en fonction d'un changement mineur à la source.
par exemple,
"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"
(évidemment ce n'est pas le cryptage MD5 réel)
la plupart des hashes (si ce n'est Tous) sont également non uniques; plutôt, ils sont uniques assez , donc une collision est hautement improbable, mais encore possible.
Une bonne façon de penser de l'algorithme de hachage est de penser à redimensionner une image dans Photoshop... supposons que vous ayez une image de 5000x5000 pixels et que vous la redimensionniez en 32x32. Ce que vous avez est toujours une représentation de l'image originale mais il est beaucoup plus petit et a efficacement "jeté loin" certaines parties des données d'image pour le faire correspondre à la plus petite taille. Donc si vous deviez redimensionner cette image 32x32 pour la faire remonter à 5000x5000, tout ce que vous obtiendriez serait un désordre flou. Cependant, parce que a 32x32 l'image n'est pas si grande qu'il serait théoriquement concevable qu'une autre image puisse être réduite pour produire exactement les mêmes pixels!
c'est juste une analogie, mais ça aide à comprendre ce qu'un hash fait.
une collision de hachage est beaucoup plus probable que vous ne le pensez. Regardez le "birthday paradox pour mieux comprendre pourquoi.
comme le nombre de fichiers d'entrée possibles est plus grand que le nombre de sorties de 128 bits, il est impossible d'attribuer de façon unique un hachage MD5 à chaque possibilité.
les fonctions de hachage cryptographique sont utilisées pour vérifier l'intégrité des données ou les signatures numériques (le hachage étant signé pour l'efficacité). Changer le document original devrait donc signifier que le hachage original ne correspond pas au document modifié.
ces critères sont parfois utilisés:
- résistance de Préimage: pour une fonction de hachage donnée et pour un hachage donné, il devrait être difficile de trouver une entrée qui possède le hachage donné pour cette fonction.
- Deuxième preimage résistance: pour une fonction de hachage et d'entrée, il doit être difficile de trouver un deuxième, d'entrée avec le même hash.
- résistance à la Collision: pour une fonction a donnée, il devrait être difficile de trouver deux entrées différentes avec le même hachage.
ces critères sont choisis pour rendre difficile de trouver un document qui correspond à un hachage donné, sinon il serait possible de contrefaire des documents en remplaçant l'original par un qui correspond par hachage. (Même si le remplacement est du charabia, le simple remplacement de l'original peut provoquer des perturbations.)
le numéro 3 implique le numéro 2.
comme pour MD5 en particulier, il a été démontré qu'il était défectueux: How pour casser MD5 et autres fonctions de hachage .
mais c'est ici que les tables arc-en-ciel entrent en jeu. Fondamentalement, il est juste une grande quantité de valeurs hachées séparément et puis le résultat est sauvé au disque. Puis l'inversion de bits est "juste" pour faire une recherche dans une très grande table.
Évidemment, cela n'est envisageable que pour un sous-ensemble de toutes les valeurs d'entrée possibles, mais si vous connaissez les limites de la valeur d'entrée, il pourrait être possible de la calculer.
un scientifique chinois a trouvé un moyen appelé "collisions à préfixe choisi" pour créer un conflit entre deux cordes différentes.
voici un exemple: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip
Le code source: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5_source.zip
comme la plupart ont déjà dit MD5 a été conçu pour les flux de données de longueur variable à être hachées à un morceau de longueur fixe de données, de sorte qu'un simple hachage est partagé par de nombreux flux de données d'entrée.
cependant, si vous avez déjà eu besoin de trouver les données originales à partir de la somme de contrôle, par exemple si vous avez le hachage d'un mot de passe et avez besoin de trouver le mot de passe original, il est souvent plus rapide de simplement google (ou tout autre chercheur que vous préférez) le hachage pour la réponse que de forcer il. J'ai trouvé avec succès quelques mots de passe en utilisant cette méthode.
par définition fonction de hachage(hachage cryptographique): ne doit pas être inversible;ne doit pas avoir de collisions(le moins possible).
regd votre question : c'est une façon de hachage. l'entrée (quelle que soit sa longueur) génère une sortie de taille fixe.(il sera capitonné sur la base d'algo(limite de 512 bits pour MD5) ). L'information est compressée (perdue) et pratiquement impossible à générer à partir de la transformation inverse.
informations supplémentaires sur MD5: il est vulnérable pour les collisions. passé par le présent article récemment, http://www.win.tue.nl/hashclash/Nostradamus /
ouvre le code source pour les implémentations de hachage crypto(MD5 et SHA) peut être trouvé dans le code Mozilla. (freebl de la bibliothèque).
maintenant un MD5 jours hashes ou tout autre hashes pour cette matière sont pré-calculés pour toutes les chaînes possibles et stockées pour un accès facile. Bien qu'en théorie MD5 ne soit pas réversible mais en utilisant de telles bases de données, vous pouvez trouver quel texte a abouti à une valeur de hachage particulière.
par exemple, essayez le code de hachage suivant à http://gdataonline.com/seekhash.php pour savoir quel texte j'ai utilisé pour calculer le hachage
aea23489ce3aa9b6406ebb28e0cda430
f(x) = 1 est irréversible. Les fonctions de hachage ne sont pas irréversibles.
c'est en fait requis pour eux de remplir leur fonction de déterminer si quelqu'un possède une copie non corrompue des données hachées. Cela rend vulnérable aux attaques par la force brute, qui sont assez puissantes de nos jours, en particulier contre MD5.
il y a aussi de la confusion ici et ailleurs parmi les gens qui avoir des connaissances en mathématiques mais peu de connaissances en cryptographie. Plusieurs chiffreurs XORENT simplement les données avec le keystream, et donc vous pouvez dire qu'un cryptexte correspond à tous les textes simples de cette longueur parce que vous pourriez avoir utilisé n'importe quel keystream.
cependant, ceci ignore qu'un texte clair raisonnable produit à partir de la graine password est beaucoup, beaucoup plus probable qu'un autre produit par la graine Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6o dans la mesure où quiconque prétendant que la seconde était une possibilité serait moqué de moi.
de la même manière, si vous essayez de décider entre les deux mots de passe potentiels password et Wsg5Nm^bkI4EgxUO , ce n'est pas aussi difficile à faire que certains mathématiciens voudraient vous faire croire.
la meilleure façon de comprendre ce que toutes les réponses les plus votées signifiaient est d'essayer de revenir sur l'algorithme MD5. Je me souviens que j'ai essayé d'Inverser l'algorithme MD5crypt il y a quelques années, non pas pour récupérer le message original parce qu'il est clairement impossible, mais juste pour générer un message qui produirait le même hachage que le hachage original. Cela, au moins théoriquement, me fournirait un moyen de me connecter à un périphérique Linux qui a stocké l'utilisateur: mot de passe dans le /etc / passwd fichier en utilisant le message généré (mot de passe) au lieu d'utiliser le message original. Puisque les deux messages auraient le même hachage résultant, le système reconnaîtrait mon mot de passe (généré à partir du hachage original) comme valide. Qui ne travaillent pas du tout. Après plusieurs semaines, si je me souviens bien, l'utilisation de sel dans le message initial m'a tué. J'ai dû produire non seulement un message initial VALIDE, mais un message initial valide salé, ce que je n'ai jamais pu faire. Mais le savoir que j'ai tiré de cette expérience était agréable.
j'aime tous les différents arguments. Il est évident que la valeur réelle des valeurs hachées est simplement de fournir des placeholders humains-illisibles pour les chaînes de caractères telles que les mots de passe. Il n'a pas amélioré la sécurité. En supposant qu'un attaquant ait eu accès à une table avec des mots de passe hashés, il/elle peut:
- hachez un mot de passe de son choix et placez les résultats à l'intérieur de la table des mots de passe s'il a les droits d'écriture/édition à la table.
- génère des valeurs hachées de mots de passe communs et teste l'existence de valeurs hachées similaires dans la table de mots de passe.
dans ce cas, les mots de passe faibles ne peuvent pas être protégés par le simple fait qu'ils sont hachés.