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

Question

Un concept auquel je me suis toujours posé la question 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 la 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 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 ces chaînes impossibles à retracer dans ces fonctions?

Answer 1

Le matériau en entrée peut avoir une longueur infinie, la sortie étant toujours 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 notez uniquement le reste, vous obtiendrez respectivement 0 ou 1 - pair ou impair. Est-il possible de prendre ce 0 ou 1 et d’obtenir le numéro original?

Answer 2

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, des morceaux de données arbitraires de taille arbitraire pourraient être représentés par 128 bits à peine, sans aucune perte d’information. Ainsi, vous auriez pu reconstituer le message d'origine à partir d'un nombre de 128 bits, quelle que soit la taille du message d'origine.

Answer 3

Contrairement à ce que soulignent les réponses les plus citées ici, la non-injectivité (c’est-à-dire qu’il existe plusieurs chaînes de hachage à la même valeur) d’une fonction de hachage cryptographique provoquée par la différence entre les valeurs de grande taille (potentiellement infinie) et la taille de sortie fixe n'est pas le point important & # 8211; En fait, nous préférons les fonctions de hachage où ces collisions se produisent aussi rarement que possible.

Considérons cette fonction (en notation PHP, sous forme de question):

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

Ceci ajoute des espaces, si la chaîne est trop courte, puis prend les 16 premiers octets de la chaîne, puis l'encode au format 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");

Ceci produira:

737461636b6f766572666c6f772e636f6d

Cette fonction a également la même propriété de non-injectivité que celle soulignée 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 ne générer que 32 digits hexadécimaux. Bien sûr, cela ne peut pas être injectif.

Mais dans ce cas, il est facile de trouver une chaîne qui mappe sur le même hachage (appliquez simplement hex2bin sur votre hachage, et vous l’avez bien). Si votre chaîne d'origine avait la longueur 16 (comme dans 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 la saisie est 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 les suivantes:

• 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 (seconde résistance à la pré-image)
• il est difficile de trouver une paire de chaînes avec le même hachage (résistance à la collision)

Évidemment, ma fonction simple_hash ne remplit aucune de ces conditions. (En fait, si nous limitons l’espace d’entrée à des "chaînes de 16 octets", ma fonction devient alors injective et résiste même à la preuve de la deuxième pré-image et de la résistance 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, qui ont le même hachage, avec beaucoup de travail, mais pas beaucoup de travail), N'utilisez pas MD5 pour des tâches critiques. Il n'y a pas encore d'attaque de pré-image, mais les attaques vont s'améliorer.

Pour répondre à la question:

  

En quoi ces fonctions rendent-elles les   les chaînes résultantes sont impossibles à retracer?

Ce que MD5 (et d’autres fonctions de hachage reposant sur la construction Merkle-Damgard) fait en réalité consiste à appliquer un algorithme de chiffrement avec le message en tant que clé et une valeur fixe en tant que "texte brut", en utilisant le texte chiffré obtenu en tant que hachage. . (Avant cela, l'entrée est complété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 inverses.)

Les algorithmes de chiffrement modernes (y compris ceux utilisés dans les fonctions de hachage) sont conçus de manière à rendre la récupération de la clé difficile, même en présence d'un texte en clair et d'un texte chiffré (ou même lorsque l'adversaire en choisit une). 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 de clé (plusieurs fois) et également par chaque bit d'entrée. De cette façon, vous ne pouvez facilement retracer ce qui se passe à l'intérieur que si vous connaissez la clé complète et que vous saisissez entrée ou sortie.

Pour les fonctions de hachage de type MD5 et une attaque de type préimage (pour faciliter la tâche, avec une chaîne de hachage à bloc unique), vous n’avez que les entrées et les sorties de votre fonction de chiffrement, mais pas la clé (c’est ce que vous cherchez. pour).

Answer 4

La réponse de Cody Brocious est la bonne. Strictement parlant, vous ne pouvez pas "inverser" une fonction de hachage car plusieurs chaînes sont mappées sur le même hachage Notez cependant que la recherche de une chaîne mappée sur un hachage donné ou de la recherche de deux chaînes mappées sur le même hachage (c.-à-d. Une collision / em>), constitueraient des avancées majeures pour un cryptanalyst. La grande difficulté de ces deux problèmes explique pourquoi de bonnes fonctions de hachage sont utiles en cryptographie.

Answer 5

MD5 ne crée pas une 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"

(Évidemment, ce n'est pas le cryptage MD5 actuel)

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

Answer 6

Un bon moyen de penser à un algorithme de hachage consiste à redimensionner une image dans Photoshop ... Supposons que vous ayez une image de 5000 x 5000 pixels et que vous la redimensionniez ensuite à 32 x 32 seulement. Ce que vous avez est toujours une représentation de l’image originale, mais celle-ci est beaucoup plus petite et a effectivement été "jetée". certaines parties des données d'image pour l'adapter à la taille la plus petite. Donc, si vous redimensionniez cette image 32x32 à une taille de 5000x5000, vous obtiendrez un désordre flou. Cependant, comme une image 32x32 n’est pas très grande, il serait théoriquement possible de réduire la taille d’une autre image afin de produire exactement les mêmes pixels!

C'est juste une analogie, mais cela aide à comprendre ce que fait un hachage.

Answer 7

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

Answer 8

Le nombre de fichiers d'entrée possibles étant supérieur au nombre de sorties 128 bits, il est impossible d'assigner 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é). Changer le document original doit donc signifier que le hachage original ne correspond pas au document modifié.

Ces critères sont parfois utilisés:

1. Résistance à la pré-image: pour une fonction de hachage donnée et donnée, il devrait être difficile de trouver une entrée ayant le hachage donné pour cette fonction.
2. Deuxième résistance à la pré-image: pour une fonction de hachage et une entrée données, il devrait être difficile de trouver une deuxième entrée différente avec le même hachage.
3. Résistance à la collision: pour une fonction donnée, il devrait être difficile de trouver deux entrées différentes avec le même hash.

Ces critères sont choisis de manière à rendre difficile la recherche d’un document correspondant à un hachage donné, sinon il serait possible de falsifier des documents en remplaçant l’original par un qui correspondait à un 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.

En ce qui concerne MD5 en particulier, il a été démontré qu’il était défectueux: Comment interrompre MD5 et d’autres fonctions de hachage .

Answer 9

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. Le bit d’inversion est alors "juste". faire une recherche dans un très grand tableau.

Évidemment, 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, vous pourrez peut-être la calculer.

Answer 10

Un scientifique chinois a trouvé un moyen appelé "collisions avec préfixe choisi" créer un conflit entre deux chaînes 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

Answer 11

Comme beaucoup l'ont déjà dit, MD5 a été conçu pour que les flux de données de longueur variable puissent être hachés en un bloc de données de longueur fixe, de sorte qu'un même hachage est partagé par de nombreux flux de données d'entrée.

Toutefois, si vous avez besoin de connaître les données d'origine à partir de la somme de contrôle, par exemple si vous avez le hash d'un mot de passe et devez le trouver, il est souvent plus rapide de rechercher simplement Google (ou le moteur de recherche que vous préférez). ) le hash pour la réponse que pour le forcer brutalement. J'ai découvert quelques mots de passe avec cette méthode.

Answer 12

Le meilleur moyen de comprendre le sens de 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 l’algorithme MD5crypt il y a quelques années, non pour récupérer le message d'origine, car il est clairement impossible, mais pour générer un message produisant le même hachage que celui d'origine. Ceci, du moins théoriquement, me fournirait un moyen de me connecter à un périphérique Linux qui stockerait le nom d'utilisateur: mot de passe dans le fichier / etc / passwd en utilisant le message généré (mot de passe) au lieu de celui d'origine. Les deux messages ayant le même résultat de hachage, le système reconnaîtra mon mot de passe (généré à partir du hachage d'origine) comme valide. Cela n'a pas fonctionné du tout. 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.

Answer 13

par définition Fonction de hachage (hachage cryptographique): ne devrait pas être inversible ni avoir de collisions (le moins possible).

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

informations supplémentaires sur le MD5: il est vulnérable aux collisions. passé en revue cet article récemment, http://www.win.tue.nl/hashclash/Nostradamus/

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

Answer 14

Désormais, les hachages MD5 ou autres de ce nombre sont précalculés pour toutes les chaînes possibles et sont stockés pour en faciliter l’accès. Bien qu'en théorie, MD5 ne soit pas réversible, mais en utilisant de telles bases de données, vous pouvez savoir quel texte a généré une valeur de hachage particulière.

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

aea23489ce3aa9b6406ebb28e0cda430

Answer 15

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

C’est en fait requis qu’ils remplissent leur fonction qui consiste à déterminer si une personne possède une copie non corrompue des données hachées. Cela crée une susceptibilité 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 chez les personnes qui ont des connaissances en mathématiques mais peu de connaissances en cryptographie. Plusieurs chiffreurs simplement XOR 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 clair raisonnable généré à partir du germe mot de passe est beaucoup plus probable qu'un autre produit sur le germe Wsg5Nm ^ bkI4EgxUOhpAjTmTjOOF! % BX% 9! NnG% 32ftud% YkBO $ U6o dans la mesure où quiconque affirmerait que la seconde possibilité était envisageable se moquait de lui.

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 avez-vous croire.

Answer 16

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

• Hachez un mot de passe de votre choix et placez les résultats dans le tableau des mots de passe s'il dispose des droits d'écriture / d'édition sur le tableau.
• Générez des valeurs hachées pour les mots de passe communs 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.