Comment se fait les valeurs de hachage MD5 ne sont pas réversibles ?

Question

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

Si sur mon serveur, en PHP, j'produire:

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

Lorsque vous exécutez la même chaîne par une fonction MD5, vous obtenez le même résultat sur votre installation de PHP. Un processus est utilisé pour produire de la valeur, d'une certaine valeur de départ.

N'est-ce pas dire qu'il n'y est une certaine façon de déconstruire ce qui se passe et d'inverser la valeur de hachage?

Quel est-il de ces fonctions qui transforme l'cordes impossible de retracer?

Answer 1

Le matériel d’entrée peut être une longueur infinie, où la sortie est toujours longueur de 128 bits. Cela signifie qu’un nombre infini de chaînes d’entrée génère le même résultat.

Si vous saisissez un nombre aléatoire et le divisez par 2, mais seulement d’écrire vers le bas le reste, vous obtiendrez un 0 ou 1--pair ou impair, respectivement. Est-il possible de prendre que 0 ou 1 et obtenir le numéro d’origine ?

Answer 2

Si les fonctions de hachage comme MD5 sont réversibles alors il aurait été un événement dans l’histoire des algorithmes de compression de données ! Est facile de voir que si MD5 sont réversibles alors arbitraires des blocs de données de taille arbitraire peut être représenté par un simple 128 bits sans aucune perte d’information. Donc vous aurait été en mesure de reconstituer le message d’origine d’un nombre de 128 bits quelle que soit la taille du message original.

Answer 3

Contrairement à ce que la plupart des upvoted réponses ici souligner, la non-injectivity d'une fonction de hachage cryptographique causée par la différence entre les grands (potentiellement infinie) taille d'entrée et de sortie fixe la taille n'est pas le point important.

Prenons cette fonction (en notation PHP, comme la question):

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

Ceci ajoute quelques places, si la chaîne est trop courte, et prend alors les 16 premiers octets de la chaîne, puis la code que hexadécimal. Il a la même taille de sortie comme un hachage MD5 (32 caractères hexadécimaux, ou 16 octets si nous omettons le bin2hex partie).

print simple_hash("stackoverflow.com");

Cela permettra de sortie:

737461636b6f766572666c6f772e636f6d

Cette fonction a également le même non-injectivity bien que mis en évidence par Cody réponse pour MD5: Nous pouvons passer dans les cordes de n'importe quelle taille (tant qu'ils s'inscrivent dans notre ordinateur), et il sera de sortie n'est que de 32 chiffres hexadécimaux. Bien sûr, il ne peut pas être injective.

Mais dans ce cas, il est trivial de trouver une chaîne de caractères qui correspond à la même table de hachage (il suffit d'appliquer hex2bin sur votre table de hachage, et vous l'avez). Si votre chaîne d'origine avait la longueur de 16 (notre exemple), vous obtiendrez cette chaîne d'origine. Rien de ce genre devrait être possible pour le MD5, même si vous savez que la longueur de l'entrée est assez courte (autres qu'en essayant toutes les entrées possibles jusqu'à ce que nous trouver celui qui correspond, 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 de production d'un hash (preimage résistance)
• il est difficile de trouver une autre chaîne de produire le même hachage comme une chaîne de caractères (deuxième preimage résistance)
• il est difficile de trouver une paire de chaînes de caractères avec le même hash (collision de la résistance)

Évidemment, ma simple_hash fonction remplit aucune de ces conditions. (En fait, si l'on restreint l'espace d'entrée "de 16 octets chaînes", puis ma fonction est injective, et donc est même prouvable deuxième preimage résistant et résistant à la collision.)

Il existe maintenant des attaques par collision contre MD5 (par exemple, il est possible de produire une paire de chaînes de caractères, même avec un même préfixe, qui ont le même hash, avec très peu de travail, mais pas impossible, beaucoup de travail), de sorte que vous ne devriez pas utiliser MD5 pour tout ce qui est critique. Il n'y a pas encore un preimage attaque, mais les attaques va aller mieux.

Answer 4

Réponse de Cody Brocious est la bonne. À proprement parler, vous ne pouvez pas « inverser » une fonction de hachage car beaucoup de chaînes sont mappés au même hachage. Notez, toutefois, que soit trouver une chaîne qui obtient le mappage à un hachage donné, ou trouver deux chaînes qui sont mappées au même hachage (c'est-à-dire une collision), seraient des percées majeures pour un décrypteur. La grande difficulté de ces problèmes est la raison pour laquelle les fonctions de hachage bonne sont utiles en cryptographie.

Answer 5

MD5 ne crée pas une valeur de hachage unique ; le but du MD5 est pour produire rapidement une valeur significativement, les modifications sont basées sur une modification mineure à la source.

Par exemple,

(Évidemment ce n’est pas réels chiffrement MD5)

Hachages la plupart (sinon tous) sont également non uniques ; au contraire, ils sont uniques assez, donc une collision est hautement improbable, mais toujours possible.