Existe-t-il un point fixe MD5 où md5(x) == x ?

Question

Existe-t-il un point fixe dans la transformation MD5, c'est-à-dire qu'il existe x tel que md5(x) == x ?

Answer 1

Étant donné qu'une somme MD5 comporte 128 bits, tout point fixe devrait nécessairement comporter 128 bits également. En supposant que la somme MD5 de n'importe quelle chaîne est uniformément distribuée parmi toutes les sommes possibles, la probabilité qu'une chaîne de 128 bits donnée soit un point fixe est de 1/2^128.

Ainsi, la probabilité qu'aucune chaîne de 128 bits ne soit un point fixe est (1 - 1/2^128)^(2^128), donc la probabilité qu'il y ait un point fixe est 1 - (1 - 1/2^128)^(2^128).

Puisque la limite à l'infini de (1 - 1/n)^n est de 1/ e et 2^128 est très certainement un très grand nombre, cette probabilité est presque exactement 1 - 1/. e ≈ 63.21%.

Bien sûr, il n'y a pas de hasard en réalité - soit il y a un point fixe, soit il n'y en a pas. Mais nous pouvons être sûrs à 63,21 % qu'il existe un point fixe. (Notez également que ce nombre ne dépend pas de la taille de l'espace de clé - si les sommes MD5 étaient de 32 bits ou de 1024 bits, la réponse serait la même, tant qu'elle est supérieure à environ 4 ou 5 bits).

Answer 2

Comme le hachage est irréversible, ce serait très difficile à comprendre. La seule façon de résoudre ce problème serait de calculer le hachage sur chaque sortie possible du hachage, et de voir si vous obtenez une correspondance.

Pour élaborer, il y a 16 octets dans un hachage MD5. Cela signifie qu'il existe 2^(16*8) = 3,4 * 10 ^ 38 combinaisons. S'il fallait 1 milliseconde pour calculer un hachage sur une valeur de 16 octets, il faudrait 10790283070806014188970529154,99 ans pour calculer tous ces hachages.

Answer 3

Bien que je n'aie pas de réponse positive ou négative, je pense que oui et qu'il y a peut-être 2^32 points fixes (pour l'interprétation de la chaîne de bits, pas pour celle de la chaîne de caractères). Je travaille activement sur cette question parce qu'elle me semble être un puzzle génial et concis qui nécessitera beaucoup de créativité (si vous ne vous contentez pas d'une recherche par force brute tout de suite).

Mon approche est la suivante : traiter le problème comme un problème de mathématiques. Nous avons 128 variables booléennes et 128 équations décrivant les sorties en fonction des entrées (qui sont censées correspondre). En introduisant toutes les constantes des tables dans l'algorithme et les bits de remplissage, j'espère que les équations peuvent être grandement simplifiées pour produire un algorithme optimisé pour les entrées de 128 bits. Ces équations simplifiées peuvent ensuite être programmées dans un langage agréable pour une recherche efficace, ou traitées de nouveau de manière abstraite, en assignant des bits individuels à la fois, en faisant attention aux contradictions. Il suffit de voir quelques bits de la sortie pour savoir qu'elle ne correspond pas à l'entrée !

Answer 4

C'est une question très intéressante, et un certain nombre de développeurs ont contribué à des programmes de test pour y répondre, sous la direction du génial Elliott Kember. Consultez le site "L'identité Kember" pour plus.

Answer 5

Quelqu'un d'autre recherche également une telle valeur. Voir http://elliottkember.com/kember_identity.html . Si les calculs de la page liée sont corrects, il y a 67 % de chances qu'une telle valeur existe, mais personne ne l'a encore trouvée et une recherche par force brute est infaisable sur le plan informatique.