Comment se fait-il que les valeurs de hachage MD5 ne soient pas réversibles?

91

Un concept sur lequel je me suis toujours posé des questions est l'utilisation de fonctions et de valeurs de hachage cryptographiques. Je comprends que ces fonctions peuvent générer une valeur de hachage unique et pratiquement impossible à inverser, mais voici ce que je me suis toujours demandé:

Si sur mon serveur, en PHP je produis:

md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"

Lorsque vous exécutez cette même chaîne via une fonction MD5, vous obtenez le même résultat sur votre installation PHP. Un processus est utilisé pour produire une certaine valeur, à partir d'une 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 dans ces fonctions?

barfoon
la source
54
Un exemple simple de valeur non réversible par exemple est modulo. Par exemple 10% 3 = 1, mais vous ne pouvez pas inverser le 1 à 10 car cela pourrait aussi être 4
Gab Royer
57
Si vous pouviez reconstruire les données, vous auriez l'algorithme de compression sans perte le plus efficace qui soit :)
Dan Diplo

Réponses:

204

Le matériau d'entrée peut être d'une longueur infinie, où la sortie est toujours longue de 128 bits. Cela signifie qu'un nombre infini de chaînes d'entrée générera la même sortie.

Si vous choisissez un nombre aléatoire et que vous le divisez par 2 mais que vous n'écrivez que le reste, vous obtiendrez un 0 ou un 1 - pair ou impair, respectivement. Est-il possible de prendre ce 0 ou 1 et d'obtenir le numéro d'origine?

Cody Brocious
la source
4
C'est-à-dire que ni nombre -> reste ni chaîne -> md5 ne sont des "fonctions injectives".
Federico A. Ramponi
Federico, vous voulez sûrement dire que les fonctions bijectives non plus? Ils sont tous les deux injectifs.
Mihai Limbășan
10
moocha: Injective signifie 1 à 1. Le MD5 n'est certainement pas 1 à 1, car le domaine est plus grand que la plage. Un autre point à noter est que, étant donné une somme de contrôle MD5, il est très difficile de trouver ne serait-ce qu'une chaîne qui la hache. Cela pourrait valoir la peine d’ajouter à la réponse pour clarification.
biozinc
4
Il est impossible d'avoir une fonction de hachage qui génère des valeurs uniques. Vous mappez un nombre infini de valeurs en un nombre fini de valeurs, ce qui garantit des collisions.
Cody Brocious
4
Je suggérerais que votre réponse n'aborde pas le point clé. Comme l'a mentionné biozinc, ce qui est important pour un hachage de mot de passe sécurisé, c'est que vous ne pouvez trouver aucune entrée qui crée la sortie, pas que vous ne pouvez pas trouver l'entrée d'origine. Sur cette note, MD5 n'est pas nécessairement aussi sûr qu'il pourrait l'être ( en.wikipedia.org/wiki/MD5#Collision_vulnerabilities ).
Mike Pelley
53

Si les fonctions de hachage telles que MD5 étaient réversibles, cela aurait été un événement décisif dans l'histoire des algorithmes de compression de données! Il est facile de voir que si MD5 était réversible, alors des morceaux arbitraires de données de taille arbitraire pourraient être représentés par seulement 128 bits sans aucune perte d'information. Ainsi, vous auriez pu reconstruire le message d'origine à partir d'un nombre de 128 bits quelle que soit la taille du message d'origine.

Autocrate
la source
9
pensez à quelle vitesse il serait de télécharger des distributions Linux si vous pouviez simplement obtenir le md5 à la place :)
Colin Pickard
15
@Colin Pickard: nous ne serions pas en cours de téléchargement distros linux plus, nous serions les écrivions . :)
tzot
29

Contrairement à ce que soulignent les réponses les plus positives ici, la non-injectivité (c'est -à- dire qu'il y a plusieurs chaînes de hachage à la même valeur) d'une fonction de hachage cryptographique causée par la différence entre une taille d'entrée importante (potentiellement infinie) et une 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 cette fonction (en notation PHP, comme question):

function simple_hash($input) {
     return bin2hex(substr(str_pad($input, 16), 0, 16));
}

Cela ajoute des espaces, si la chaîne est trop courte, puis prend les 16 premiers octets de la chaîne, puis l'encode en hexadécimal. Il a la même taille de sortie qu'un hachage MD5 (32 caractères hexadécimaux, ou 16 octets si nous omettons la partie bin2hex).

print simple_hash("stackoverflow.com");

Cela produira:

737461636b6f766572666c6f772e636f6d

Cette fonction a également la même propriété de non-injectivité que celle mise en évidence par la réponse de Cody pour MD5: Nous pouvons passer des chaînes de toute taille (tant qu'elles tiennent dans notre ordinateur), et elle ne produira que 32 chiffres hexadécimaux. Bien sûr, cela ne peut pas être injectif.

Mais dans ce cas, il est trivial de trouver une chaîne qui correspond au même hachage (il suffit de l'appliquer hex2binsur votre hachage, et vous l'avez). Si votre chaîne d'origine avait la longueur 16 (comme notre exemple), vous obtiendrez même cette chaîne d'origine. Rien de ce genre ne 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 corresponde, par exemple une attaque par 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 à la pré-image)
  • il est difficile de trouver une chaîne différente produisant le même hachage qu'une chaîne donnée (deuxième résistance de pré-image)
  • il est difficile de trouver une paire de chaînes avec le même hachage (résistance aux collisions)

Evidemment mon simple_hash fonction ne remplit aucune de ces conditions. (En fait, si nous limitons l'espace d'entrée aux "chaînes de 16 octets", alors ma fonction devient injective, et est donc même prouvable résistante à la deuxième pré-image et aux collisions.)

Il existe maintenant des attaques par collision contre MD5 (par exemple, il est possible de produire une paire de chaînes, même avec un même préfixe donné, qui ont le même hachage, avec pas mal de travail, mais pas impossible beaucoup de travail), donc vous ne devriez pas utiliser MD5 pour tout ce qui est critique. Il n'y a pas encore d'attaque pré-image, mais les attaques s'amélioreront.

Pour répondre à la question réelle:

Qu'est-ce qui rend les chaînes résultantes impossibles à retracer dans ces fonctions?

Ce que MD5 (et d'autres fonctions de hachage s'appuient sur la construction Merkle-Damgard) fait effectivement, c'est appliquer un algorithme de chiffrement avec le message comme clé et une valeur fixe comme "texte brut", en utilisant le texte chiffré résultant comme hachage. (Avant cela, l'entrée est complétée et divisée en blocs, chacun de ces blocs est utilisé pour crypter la sortie du bloc précédent, XORed avec son entrée pour éviter les calculs inverses.)

Les algorithmes de cryptage 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 en utilisant à la fois du texte brut et du texte chiffré (ou même lorsque l'adversaire en choisit un). Ils le font généralement en effectuant de nombreuses opérations de brassage de bits de manière à ce que chaque bit de sortie soit déterminé par chaque bit clé (plusieurs fois) et également chaque bit d'entrée. De cette façon, vous ne pouvez retracer facilement ce qui se passe à l'intérieur que si vous connaissez la clé complète et l'entrée ou la sortie.

Pour les fonctions de hachage de type MD5 et une attaque de pré-image (avec une chaîne hachée à un seul bloc, pour faciliter les choses), vous n'avez que l'entrée et la sortie de votre fonction de cryptage, mais pas la clé (c'est ce que vous recherchez).

Paŭlo Ebermann
la source
4
Oui, je sais que c'est une réponse assez tardive, mais la réponse acceptée ne devrait pas être laissée en suspens.
Paŭlo Ebermann
Je pense que vos critiques ont un certain mérite, mais vous n'avez pas répondu à la question réelle "Qu'est-ce qui rend les chaînes résultantes impossibles à retracer?" Votre réponse se concentre sur les qualités qu'un hachage cryptographique devrait avoir, mais n'a aucune explication sur la façon dont ils sont implémentés par md5. Vous pouvez indiquer ici l'algorithme exact de calcul des sommes MD5 pour montrer comment il n'est pas réversible, mais les autres réponses fournissent une explication plus simple sans entrer dans les détails.
Autodidacte
(suite ...) 2. Ces explications utilisent "Math" pour montrer un problème fondamental en raison duquel de telles opérations perdent des informations et deviennent irréversibles.
Autodidacte
1
@SandeepDatta J'ai ajouté quelques paragraphes à ce sujet.
Paŭlo Ebermann
1
Alors que les autres réponses de ce fil sont plus techniquement correctes, cette réponse est la plus utile. La fonction non-injective f (x) = 1 est non réversible mais sans intérêt. L'utilité du hachage réside dans la résistance de pré-image où il est difficile de trouver une entrée donnant une sortie spécifique.
Justin J Stark
18

La réponse de Cody Brocious est la bonne. À proprement parler, vous ne pouvez pas «inverser» une fonction de hachage car de nombreuses chaînes sont mappées sur le même hachage. Notez, cependant, que trouver une chaîne qui est mappée à un hachage donné, ou trouver deux chaînes qui sont mappées sur le même hachage (c'est-à-dire une collision ), serait une avancée majeure pour un cryptanalyste. La grande difficulté de ces deux problèmes est la raison pour laquelle de bonnes fonctions de hachage sont utiles en cryptographie.

Federico A. Ramponi
la source
12

MD5 ne crée pas de valeur de hachage unique; L'objectif de MD5 est de produire rapidement une valeur qui change de manière significative en fonction d'un changement mineur de la source.

Par exemple,

"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"

(De toute évidence, ce n'est pas un cryptage MD5 réel)

La plupart des hachages (sinon tous) sont également non uniques; plutôt, ils sont assez uniques , donc une collision est hautement improbable, mais toujours possible.

Trevel
la source
8

Une bonne façon de penser à un algorithme de hachage est de penser à redimensionner une image dans Photoshop ... disons que vous avez une image qui fait 5000x5000 pixels et que vous la redimensionnez ensuite à seulement 32x32. Ce que vous avez est toujours une représentation de l'image d'origine, mais elle est beaucoup plus petite et a effectivement «jeté» certaines parties des données d'image pour les faire rentrer dans la plus petite taille. Donc, si vous deviez redimensionner cette image 32x32 jusqu'à 5000x5000, tout ce que vous obtiendriez est un désordre flou. Cependant, comme une image 32x32 n'est pas aussi grande, il serait théoriquement concevable qu'une autre image puisse être réduite pour produire exactement les mêmes pixels!

Ce n'est qu'une analogie, mais cela aide à comprendre ce que fait un hachage.

nbevans
la source
3
Bien que le redimensionnement d'image soit un processus avec perte, il est toujours assez facile de produire une image dans la taille d'origine de 5000 × 5000 qui (lors de la réapplication de la fonction de réduction) se réduira à la même image 32 × 32. Trouver une telle pré-image devrait être difficile pour une bonne fonction de hachage.
Paŭlo Ebermann
4

Une collision de hachage est beaucoup plus probable que vous ne le pensez. Jetez un œil au paradoxe de l' anniversaire pour mieux comprendre pourquoi.

Gamique
la source
1
Il existe 365 valeurs d'anniversaire possibles, comprises entre 2 ^ 8 et 2 ^ 9. Un hachage de 128 bits a 2 ^ 128 valeurs possibles - 2 ^ 120 fois plus. Oui, les collisions sont plus probables que vous ne le pensez, mais elles sont encore astronomiquement improbables.
Tim Keating
Vous aurez besoin d'environ 2 ^ 64 valeurs différentes pour avoir de bonnes chances de collision de hachage. Encore pas mal.
Paŭlo Ebermann
4

Comme le nombre de fichiers d'entrée possibles est supérieur au nombre de sorties 128 bits, il est impossible d'attribuer de manière unique un hachage MD5 à chaque possible.

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 plus d'efficacité). La modification du document original devrait donc signifier que le hachage original ne correspond pas au document modifié.

Ces critères sont parfois utilisés:

  1. Résistance de préimage: pour une fonction de hachage donnée et un hachage donné, il devrait être difficile de trouver une entrée qui a le hachage donné pour cette fonction.
  2. Deuxième résistance de pré-image: pour une fonction et une entrée de hachage données, il devrait être difficile de trouver une seconde entrée différente avec le même hachage.
  3. Résistance aux collisions: pour une fonction 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 la recherche d'un document qui correspond à un hachage donné, sinon il serait possible de falsifier des documents en remplaçant l'original par un qui correspond à un hachage. (Même si le remplacement est du charabia, le simple remplacement de l'original peut causer des perturbations.)

Le numéro 3 implique le numéro 2.

Quant à MD5 en particulier, il s'est avéré défectueux: Comment casser MD5 et d'autres fonctions de hachage .

Géoglyphe
la source
2

Mais c'est là que les tables arc-en-ciel entrent en jeu. Fondamentalement, il s'agit simplement d'une grande quantité de valeurs hachées séparément, puis le résultat est enregistré sur le disque. Ensuite, le bit d'inversion est "juste" pour faire une recherche dans une très grande table.

De toute évidence, cela n'est possible 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 peut être possible de la calculer.

Martinlund
la source
Ahh oui. J'ai aimé lire l'article de Jeff sur les tables de hachage ( codinghorror.com/blog/archives/000949.html ), et ce fil de discussion a aidé à comprendre le concept.
barfoon
1

Comme la plupart l'ont déjà dit, MD5 a été conçu pour que des flux de données de longueur variable soient hachés en un bloc de données de longueur fixe, de sorte qu'un seul 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 d'origine, il est souvent plus rapide de simplement rechercher sur Google (ou quel que soit le chercheur que vous préférez) le hachage pour la réponse que pour le forcer brutalement. J'ai trouvé avec succès quelques mots de passe en utilisant cette méthode.

Tim Matthews
la source
1

La meilleure façon de comprendre ce que signifiaient toutes les réponses les plus votées est d'essayer de rétablir l'algorithme MD5. Je me souviens que j'ai essayé de rétablir le MD5crypt algorithme il y a quelques années, non pas pour récupérer le message d'origine car c'est clairement impossible, mais juste pour générer un message qui produirait le même hachage que le hachage d'origine. Cela, du moins en théorie, me fournirait un moyen de me connecter à un périphérique Linux qui stockait l'utilisateur: mot de passe dans le fichier / etc / passwd en utilisant le message généré (mot de passe) au lieu d'utiliser celui d'origine. Comme 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 d'origine) comme valide. Cela n'a pas du tout fonctionné. Après plusieurs semaines, si je me souviens bien, l'utilisation de sel dans le message initial m'a tué. Je devais produire non seulement un message initial valide, mais un message initial valide salé, ce que je n'ai jamais pu faire. Mais la connaissance que j'ai tirée de cette expérience était agréable.

Vinicius
la source
Si vous pouviez générer une entrée qui produisait la valeur de hachage MD5 donnée de manière raisonnablement efficace, ce serait un gros problème pour la communauté crypto et devrait être publié. C'est complètement indépendant du fait qu'un intrant particulier ait été salé.
Dave L.
0

par définition Fonction Hash (cryptographic Hash): ne doit pas être inversible; ne doit pas avoir de collisions (le moins possible).

regd votre question: c'est un hachage à sens unique. input (quelle que soit la longueur) générera une sortie de taille fixe (elle sera complétée en fonction d'algo (limite de 512 bits pour MD5)). Les informations sont compressées (perdues) et pratiquement impossibles à générer à partir de transformations inverses.

info supplémentaire sur MD5: il est vulnérable aux collisions. parcouru récemment cet article, http://www.win.tue.nl/hashclash/Nostradamus/

ouvre le code source pour les implémentations de hachage crypto (MD5 et SHA) peut être trouvé sur Mozilla code. (bibliothèque freebl).

FL4SOF
la source
0

Désormais, les hachages MD5 ou tout autre hachage sont pré-calculés pour toutes les chaînes possibles et stockés 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 découvrir quel texte a donné une valeur de hachage particulière.

Par exemple, essayez le code de hachage suivant sur http://gdataonline.com/seekhash.php pour savoir quel texte j'ai utilisé pour calculer le hachage

aea23489ce3aa9b6406ebb28e0cda430
Babar
la source
Ah, oui, le hachage d'un mot de 7 lettres banal. Maintenant, utilisez-le pour comprendre cette chanson de 11 mots avec espace et ponctuation: 9f2c08d4e6158bd4854b15be50c8daa8. Rendez-vous dans plusieurs millénaires.
Tim Keating
6fba2bbab8a8366309bf67c7df12c622? Astuce: il peut s'agir de la version OEM d'une version spécifique de Mac OS X!
scherand
@Tim Keating, @scherand: Il suffit de souligner la faiblesse des algorithmes de hachage, car le hachage d'une chaîne est toujours le même, nous n'avons pas nécessairement besoin de casser l'algorithme pour déterminer la chaîne réelle.
Babar
2
Mais ce n'est pas ce que tu as dit. Vous avez dit que les hachages sont "précalculés pour toutes les chaînes possibles et stockés pour un accès facile", ce qui est manifestement faux (l'ensemble de "toutes les chaînes possibles" est infini ... et même l'ensemble de "toutes les chaînes plausibles" est vraiment, vraiment grand ). À mon humble avis, cela déforme à quel point il est facile de faire une attaque par dictionnaire contre une phrase de passe raisonnable.
Tim Keating
0

f (x) = 1 est irréversible. Les fonctions de hachage ne sont pas irréversibles.

Cela est en fait nécessaire pour qu'ils remplissent 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 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 ont des connaissances mathématiques mais peu de connaissances cryptographiques. Plusieurs chiffrements XOR simplement les données avec le flux de clés, et vous pouvez donc dire qu'un texte chiffré correspond à tous les textes en clair de cette longueur, car vous auriez pu utiliser n'importe quel flux de clés.

Cependant, cela ne tient pas compte du fait qu'un texte en clair raisonnable produit à partir de la graine passwordest beaucoup, beaucoup plus probable qu'un autre produit par la graine Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6odans la mesure où quiconque prétend que la seconde est une possibilité serait ridiculisé.

De la même manière, si vous essayez de choisir entre les deux mots de passe potentiels password et Wsg5Nm^bkI4EgxUO, ce n'est pas aussi difficile à faire que certains mathématiciens voudraient vous le faire croire.

Olathe
la source
Où obtenez-vous vos chiffrements Most simplement XOR les données avec la connaissance du flux clé ? Cela est vrai pour les chiffrements de flux, mais il existe également des chiffrements par blocs et ils ne fonctionnent pas de cette façon.
Paŭlo Ebermann
-5

J'aime tous les différents arguments. Il est évident que la valeur réelle des valeurs hachées est simplement de fournir des espaces réservés illisibles par l'homme pour les chaînes telles que les mots de passe. Il n'a aucun avantage de sécurité amélioré spécifique. En supposant qu'un attaquant ait accédé à une table avec des mots de passe hachés, il / elle peut:

  • Hachez un mot de passe de son choix et placez les résultats dans la table des mots de passe s'il a les droits d'écriture / d'édition sur la table.
  • Générez des valeurs hachées des mots de passe courants et testez l'existence de valeurs hachées similaires dans la table des 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.

webi
la source
La vraie valeur des «valeurs hachées» n'est pas de fournir des espaces réservés illisibles par l'homme. Si 'password1' est haché sur 'newval', cela ne cache- t-il toujours pas la valeur de la même manière, bien que le hachage soit lisible et significatif? De plus, les mots de passe sont un mauvais exemple, car ils ne doivent JAMAIS être hachés. En supposant que l'attaquant ait un accès en écriture à ladite base de données, c'est certainement une possibilité. Cependant, il semble que vous ne faites que rejeter l'utilisation appropriée de ces fonctions de hachage, un exemple est présenté dans les nombreuses réponses ci-dessus: l'intégrité des messages. C'est la raison pour laquelle je suis sur ce fil aujourd'hui, en fait.
Shane