Considérez ceci: vous créez un fichier qui contient chaque membre de l'ensemble des séquences de 16 octets. Une somme de contrôle MD5 est une séquence de 16 octets, donc par définition ce fichier contient sa propre somme de contrôle MD5. Quelque part.

Théoriquement? Oui.

Pratiquement, cependant, puisque / toute / modification du contenu d'un fichier, quelle que soit la minute, provoque un changement radical dans la somme de contrôle (c'est ainsi que les sommes de contrôle md5 fonctionnent, après tout), vous doivent être en mesure de prédire comment la somme de contrôle changera lorsque vous modifiez le fichier pour inclure la somme de contrôle - à toutes fins utiles, ce n'est pas très différent de pouvoir casser l'algorithme de hachage md5.

Il n'y a pas de "impossible" en cryptographie, mais la science reconnaît le concept de "pratiquement annulable" ou "statistiquement improbable" et c'est à peu près ce que vous traiter ici, pour le moment.

Mise à jour: en y repensant, j'ai trouvé une méthode qui devrait permettre la construction d'un fichier contenant son propre MD5 beaucoup plus rapidement que ce que j'expliquais au départ. Le nouveau coût devrait être d'environ 2 ⁶⁵ invocations élémentaires de MD5, soit beaucoup moins que les 2 ¹¹⁹ dont je parlais; ce serait même techniquement faisable (avec un budget compté en millions de dollars - mais pas en milliards ). Voir à la fin une description de la nouvelle méthode.

Réponse originale:

Supposons que MD5 est un hachage "parfait" fonction qui peut être modélisée comme un oracle aléatoire. Un oracle aléatoire est une fonction pour laquelle vous ne savez rien de la sortie pour une entrée donnée avant de l'essayer une fois. Pour un oracle aléatoire, la meilleure méthode pour atteindre ce que vous recherchez est l'espoir: vous essayez des messages d'entrée aléatoires jusqu'à ce que vous en trouviez un qui contient son propre hachage. La question est alors: quelle taille de messages d'entrée devez-vous utiliser?

MD5 traite les données en ajoutant quelques bits de remplissage (au moins 65, au plus 576) de sorte que la longueur soit un multiple de 512; puis les données sont divisées en blocs de 512 bits. Le coût de hachage d'un message est directement proportionnel au nombre de tels blocs. C'est à dire. pour un message n bits, le coût est de ceil ((n + 65) / 512) . Un message n bits, par contre, offre des sous-séquences n-127 de 128 bits. Des messages plus longs rendent plus probable la réussite de chaque message (de manière linéaire) mais coûtent plus cher à traiter (linéairement aussi). La longueur du message est donc généralement neutre, sauf que la surcharge impliquée par le remplissage est plus grande lors de l'utilisation de messages courts. Dans l'ensemble, avec des messages aléatoires suffisamment volumineux (par exemple 8 ko), vous trouverez un message qui contient son propre MD5 au coût moyen d'environ 2¹¹⁹ évaluation élémentaire MD5. Une évaluation élémentaire de MD5 utilise quelques centaines de cycles d'horloge sur un processeur récent, et 2¹¹⁹ est totalement irréalisable avec la technologie d'aujourd'hui (et la technologie de demain aussi).

(Le "gros fichier avec toute la séquence de 128 bits" dont parle Graham Lee n'est qu'un cas particulier de cette méthode générique, avec un seul très gros message.)

Maintenant, MD5 est largement connu pour ne pas être un oracle aléatoire - ne serait-ce que parce que les collisions sur MD5 peuvent être calculées efficacement, ce qui n'est pas possible avec un oracle aléatoire. Il est donc concevable que des raccourcis exploitant les faiblesses de la structure MD5 existent. Cependant, je n'ai connaissance d'aucune attaque conduisant à un message contenant son propre MD5; cela ressemble à un problème proche de la résistance pré-image , quelque chose qui est considéré comme beaucoup plus difficile que les collisions.

Nouvelle méthode:

MD5, comme la plupart des fonctions de hachage (sinon toutes), est streamé : lorsqu'il traite une longue entrée, il le fait en un seul passage, en gardant un petit état de fonctionnement de taille fixe. Pour MD5 en particulier, l'état d'exécution a une taille de 128 bits (16 octets) et les données sont traitées par blocs de 512 bits (64 octets). Une conséquence importante est la suivante: si vous avez des entrées m et m || x ("||" indique la concaténation), et que vous voulez calculer à la fois MD5 ( m ) et MD5 ( m || x ), alors le surcoût nécessaire pour calculer le second est proportionnel à la taille de x , mais PAS à la taille de m . En d'autres termes, si vous avez une entrée de 1 gigaoctet m , calculez MD5 ( m ), puis voulez calculer le MD5 de m suivi par une bande-annonce de 20 octets x , alors ce deuxième MD5 peut réutiliser une grande partie du travail effectué pour le premier, et sera presque gratuit.

Cela conduit à l'algorithme suivant pour trouver un message m contenant son propre MD5:

1. Commencez par une valeur m.
2. Calculez MD5 ( m ). S'il fait partie de m , alors quittez (nous avons trouvé notre message).
3. Remplacez m par m || x où x est tel que la séquence des 128 derniers bits de m || x n'apparaît nulle part dans m .
4. Boucle vers 2.

La recherche de la bonne valeur " x " à chaque étape peut être effectuée en utilisant une séquence De Bruijn. Utilisez B (2, 128) comme séquence de base si chaque x est un seul bit. Si vous voulez une solution orientée octets (le message m doit être composé d'un nombre entier d'octets, et MD5 ( m ) doit apparaître entre m à une limite d'octet), puis utilisez B (256, 16) .

Pour calculer le nombre moyen d'itérations nécessaires pour trouver un hit, considérez qu'à l'itération n , le message m contient n sous-séquences distinctes de 128 bits (ou 16 octets), le nombre total cumulé de comparaisons sera donc n ( n +1) / 2. En supposant que MD5 soit un oracle aléatoire, alors chaque comparaison a une probabilité 2 ^-128 d'être un hit, donc n devra, en moyenne, être tel que n ( n +1) / 2 = 2 ¹²⁸ - ce qui se traduit par n = 2 ^64,5 itérations.

Cependant, chaque itération implique le calcul d'un MD5 ( m || x ) où x est très petit (un bit ou un octet ) et MD5 ( m ) a été calculé; cela ne nécessitera généralement qu'un seul calcul MD5 élémentaire supplémentaire (traitement d'un seul bloc de 64 octets). (Si x sont des bits, une seule itération sur 512 nécessitera le traitement de deux blocs; si x sont des octets, cela devient une itération sur 64. )

Quoi qu'il en soit, le plus dur sera la recherche. Obtenir toutes les sous-séquences d'un index correctement triées pour une recherche rapide nécessitera énormément de RAM rapide, ce qui serait probablement beaucoup plus cher que de calculer le 2 ^64.5 MD5. Cependant, certaines séquences De Bruijn permettent un décodage rapide et sans stockage. Ainsi, avec cet algorithme, on peut trouver un message m contenant son propre MD5 pour un coût proche de 2 ⁶⁵ calculs de MD5. Le message résultant aura une longueur d'environ 3,3 * 10 ¹⁸ octets, soit environ un million de disques durs modernes (huit fois plus si nous voulons une solution orientée octets).

Il On notera que l'algorithme peut être démarré avec un message arbitraire m , de toute taille. Ce point de départ apparaîtra au début du fichier self-MD5 produit par l'algorithme.

(Dans ma réponse initiale, l'erreur était dans cette phrase: "Les messages plus longs rendent plus probable la réussite de chaque message (de manière linéaire) mais coûtent plus cher à traiter (linéairement aussi)." Comme expliqué ci-dessus, plus les messages peuvent encore être traités très efficacement tant que nous les générons en réutilisant un préfixe commun, comme dans mon nouvel algorithme.)

Sur le plan cryptographique, l'attaque que vous décrivez est en fait plus difficile que de trouver une première pré-image , peut-être même plus difficile que de trouver une deuxième pré-image .

Ce n'est pas possible étant donné la puissance de calcul d'aujourd'hui et les attaques cryptographiques d'aujourd'hui.

Les attaques actuelles sur MD5 ne sont même pas près de trouver des pré-images - nous parlons de quelque chose de complètement différent des diverses attaques par collisions qui ont été démontrées (et sont la raison pour laquelle MD5 est considéré comme quelque peu peu sûr). L'attaque qui serait nécessaire pour créer un fichier avec son MD5 n'a rien à voir avec des collisions.

Je dirais qu'une telle attaque, car comme je l'ai mentionné est encore plus difficile qu'une attaque de préimage, est très improbable de nos jours.

(Copier mon commentaire d'origine comme réponse :)

Vous feriez mieux de créer une section du fichier pour le md5 / hachage, et une section séparée pour le contenu.

D'un autre côté, puisque n'importe qui peut recréer la partie de hachage, quelle valeur de sécurité obtiendriez-vous?
Vous pourriez obtenir une protection contre les falsifications à partir d'une signature numérique (ou peut-être via HMAC), mais un simple hachage ne vous aidera pas.
Ou essayez-vous de faire autre chose?

Ce que vous demandez, c'est l'existence d'un point fixe de la composition de deux fonctions: la fonction md5 , et une fonction ( appelons-le f , et appelons l'ensemble de toutes ces fonctions F ) qui prend un md5 et produit votre fichier. Autrement dit, X = f (md5 (X)) .

Comme le dit l'article de Wikipédia, toutes les fonctions n'ont pas de point fixe.

Pour certains triviaux fonctions dans F , la réponse est oui. Par exemple, une fonction qui rejette toujours l'entrée et sort toujours un fichier de zéro octet fera évidemment que sa composition avec md5 aura un point fixe. De toute évidence, ces cas ne sont pas ce que vous voulez - vous ne pouvez pas dire avec un visage impassible qu'il "contient sa somme md5 à l'intérieur". Alors, affinons notre définition.

Limitons pour l'instant notre ensemble F à toutes les fonctions qui produisent la concaténation d'un préfixe, l'entrée, et un suffixe. Autrement dit, f (X) = pre∥X∥post . Avec cela, la totalité de la somme md5 doit apparaître quelque part dans le fichier, intacte, en binaire et exactement une fois. C'est beaucoup plus restrictif que votre définition (qui autoriserait le md5sum sous forme de texte, divisé en parties, répété, voire prononcé sous forme de fichier .wav !), Mais cela évite les fonctions dégénérées qui inclure la somme md5 ou n'en inclure qu'une partie.

Il est également facile de voir que, si f (md5 (X)) a un point fixe, md5 (f (X)) a également un point fixe, et vice versa.

Maintenant, jetez un œil à cette question de stackoverflow: Y a-t-il un point fixe MD5 où md5 (x) == x ?. En particulier, jetez un œil à la réponse d'Adam Rosenfield. On y voit qu'il y a une probabilité de 63,21% que md5 (X) ait un point fixe (bien sûr, le point fixe existe ou n'existe pas; c'est une probabilité bayésienne, qui mesure notre conviction qu'il existe).

Le même argument utilisé dans cette réponse peut être appliqué à md5 (f (X)) , et donc à f (md5 (X)) . Il y a donc 63,21% de probabilité que, pour un préfixe et un suffixe donnés (c'est-à-dire pour une fonction f donnée), un fichier contenant sa propre somme md5 à l'intérieur existe, et 36,79% de probabilité qu'il n'existe le fichier existe. Encore une fois, c'est la probabilité bayésienne.

Il est facile de voir, comme mentionné dans cette réponse, que le même argument s'appliquera également à tout fichier qui dépend suffisamment de sa sortie md5. Pour les fichiers qui ne dépendent que de quelques bits de la sortie md5, ou qui n'en dépendent pas du tout (y compris celui de la réponse de @Graham Lee, qui dépend de 0 bits de la sortie md5), la réponse sera différente.

Vous pouvez le faire en utilisant un flux de données alternatif, même si les informations peuvent ne pas être transférées correctement entre certains systèmes de fichiers ou OS. Certaines applications peuvent également gérer (ou ne pas les gérer) différemment.

En bref, les flux de données alternatifs sont une forme de métadonnées attachées à des fichiers dans certains systèmes de fichiers (NTFS en est un) qui n'apparaissent pas facilement lors de la visualisation le contenu d'un répertoire. Même avec le système configuré pour afficher les "fichiers cachés" et ces "fichiers du système d'exploitation protégés" toujours critiques, vous ne verrez toujours pas de "fichier" ADS dans la plupart des gestionnaires de fichiers.

De plus, le "hôte" le fichier lui-même n'apparaîtra pas du tout modifié. La taille du fichier restera la même, et même le hachage MD5 (ou tout autre, d'ailleurs) sera le même. Vous pouvez même stocker un "fichier" ADS plus volumineux que son fichier hôte - bien que vous ne puissiez bien sûr pas en stocker un si grand qu'il dépasse la capacité physique de votre disque.

Dans les systèmes Windows avec NTFS , Les fichiers ADS sont plus facilement accessibles via la ligne de commande. Donc, pour File1.ext, si vous souhaitez stocker le hachage MD5 dans un ADS, procédez comme suit:

• Calculez le MD5 de File1.ext avec l'outil de votre choix.
• Ouvrez une fenêtre CMD et accédez au dossier contenant File1.ext
• Exécutez le bloc-notes sur le fichier, mais ajoutez un ADS à la fin avec un séparateur deux-points (aucun espace de chaque côté des deux-points ) comme ceci:
  • notepad File1.ext: MD5.txt
  • (Assurez-vous de le faire à partir de l'invite de commande et en travaillant dans le même dossier comme fichier - ou indiquez le chemin complet du fichier.)
• Le bloc-notes avertira que File1.ext: MD5.txt n’existe pas. Dites au Bloc-notes que oui, vous voulez créer un nouveau fichier.
• Collez votre hachage MD5 dans MD5.txt, fermez et enregistrez le fichier.
• Relancez votre hachage MD5 contre File1.ext pour vérifier qu'il n'a pas changé.
• Relancez le Bloc-notes comme ci-dessus, pour vérifier la présence de l'ADS.

Encore une fois, les ADS sont gérés différemment par différents systèmes d'exploitation et systèmes de fichiers. Il est donc peu probable qu'ils traversent très bien Internet (ou même certains LAN ou sneakernets). Mais c'est une façon de faire ce que vous semblez vouloir faire.

Pour plus de détails, instructions ou utilitaires, consultez Google.

Dans le cas général, non, car l'ajout de la somme MD5 modifierait le fichier lui-même et donc sa somme MD5, la plupart du temps ...

Cependant, pour les fichiers spécialement conçus, cela pourrait être possible, en utilisant une attaque par collision.

Il y a un exemple d'attaques par collision où deux fichiers PostScript sont conçus pour avoir la même somme MD5 ici (il y a aussi des références papier): http: // th .informatik.uni-mannheim.de / people / lucks / HashCollisions /

Vous pourrez peut-être utiliser la même approche pour générer un deuxième fichier qui contiendrait le contenu original, sa somme MD5 , et du contenu supplémentaire pour faire la collision.

Vous pourriez avoir quelque chose comme un format wrapper avec le MD5 dans une partie du fichier et le contenu réel dans une autre partie de celui-ci.

Cela serait inutile car si l'attaquant peut changer le contenu, il peut également changer le MD5 pour qu'il corresponde au nouveau contenu.

En pensant un peu en dehors de la boîte, vous pouvez coder une variable pour stocker le md5 d'un fichier (le fichier exact) et ainsi, tandis que le md5 réel du fichier dans le texte plan ne sera pas inclus dans le fichier lui-même, si le fichier était du code exécutable qu'il pouvait être programmé pour stocker une valeur de son propre md5 en tant que variable.

Pour améliorer encore une telle idée (afin de lui donner une sorte de valeur utilisable), vous pouvez stocker le md5 dans un fichier séparé (créé à la fin) et sécurisez ce second fichier de telle manière que seul le premier fichier contienne une méthode raisonnable pour y accéder et pour le comparer avec la variable md5 précédemment calculée.

Le réel L'utilité d'une telle idée est probablement limitée uniquement à la capacité de vérifier que le fichier lui-même n'a pas été modifié et d'alerter d'une faille de sécurité qui s'est déjà produite plutôt que d'en empêcher une de se produire en premier lieu.

Si vous n'avez pas besoin que les bits soient en séquence , alors bien sûr, c'est assez simple.

Ce fichier fonctionnera:

  1 0 0 1 0 1 1 0 1 0 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 00 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 00 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 0 10 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0  

(Le fichier est affiché en binaire.)

Le md5sum de celui-ci est 5FADE2F41E1B9759DB92E54DB9519365 , ou en binaire:

  0 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 11 1 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 1 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 1 0 0 1 0 0 1 1 0 1 1 0 0 1 0 1  

La somme md5 est à l'intérieur du fichier (mais pas dans l'ordre). C'est le même fichier que ci-dessus, avec le md5sum affiché tel quel, tandis que les autres contenus sont remplacés par -:

  - 0 - 1 0 1 1 - 1 - 1 - 1 - - 1 - 0 1 0 - 1 - 1 0 1 - 1 1 - 1 0 0 - 0 1 - 0 1 - - 1 - 1 - 1 - 0 1 0 - 0 0 - - 0 - 0 - 1 1 - 1 - 1 - 0 0 - - 0 - 0 1 - - 1 - 0 1 - - 1 1 0 - 0 1 0 1 - - 1 1 0 - 1 - 0 1 - - 1 0 - 0 1 1 - - 1 - 0 1 - 1 0 - 1 1 - - 1 - 0 - 0- 1 0 - - 0 - 1 0 1 1 - - 1 0 - - 0 1 0 1 0 1 0 - 0 1 - 1 0 - 1 1 0 1 - 1 - - 1 - 0 - 0 - 1 - 0 - 1 0 1 - 0 0 - - 0 1 - 1 0 0 10 - 0 1 1 0 1 - - 1 - 0 0 1 0 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  

Bien sûr, ce fichier fonctionnerait aussi:

  0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1  

La somme md5 est DB4C2CAB0A3E4320AB6CA03127F20937 . En binaire:

  1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 01 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 1  

Et voici le md5sum vu dans le fichier:

  - 1 - 1 0 1 - 1 0 1 - 1 0 1 0 - 0 1 - 1 0 - 0 - 0 - 0 1 0 1 - 1 0 - 0 1 0 1 0 1 0 1 - 1 0 - 0 - 0 - 0 1 0 1 0 - 0 - 0 1 - 1 - 1- 1 - 1 0 - 0 1 0 - 0 - 0 - 0 1 - 1 0 - 0 1 0 - 0 - 0 - 0 - 0 1 0 1 0 1 0 1 - 1 0 1 - 1 0 1 - 1 0 - 0 1 0 1 0 - 0 - 0 - 0 - 0 - 0 - 0 1 - 1 0 - 0 - 0 1 0 - 0 1 0 - 0 1 - 1 - 1 - 1 - 1 - 1 - 1 0 - 0 1 0 - 0 - 0 - 0 - 0 1 0 - 0 1 0 - 0 1 - 1 0 1 - 1 - 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  

[Est-il] possible de créer un fichier qui a sa somme md5 à l'intérieur ainsi que d'autres contenus.

Oui, et il est trivialement prouvable.

MD5 produit un espace fini [16 octets, ou 128 bits] de hachages de sortie possibles. Il prend, en entrée, un ensemble potentiellement infini de documents possibles contenant des valeurs de hachage MD5 potentielles, chacun produisant une valeur de hachage dans cet espace fini.

Par le principe de casier, il doit être un nombre infini de collisions [plusieurs documents avec la même valeur de hachage], et certains d'entre eux doivent contenir ce hachage.

Comme d'autres l'ont souligné, ce n'est pas pratique mais c'est possible.