← Blog

Un PNG qui affiche son propre hash MD5 (hashquine) : « The Arma Of Efe » créé de zéro

Comment produire une image PNG qui inscrit son propre hash MD5 dans ses pixels, sans modèle prêt à l'emploi ? Collisions MD5, couches du PNG, recherche efe23…23efe sur RTX 5070, avec des explications interactives.

Ce visuel n’est pas un simple logo. Sur la courbe à droite, de haut en bas, est écrit efe235ae1b88c53e73d1c11515623efe, et c’est le hash MD5 du fichier lui-même. Si vous téléchargez l’image et exécutez md5sum, vous obtiendrez exactement les mêmes 32 caractères.

Ce type de fichier s’appelle un hashquine. L’exemple le plus connu est le PNG au dragon de retr0id, que beaucoup de gens réutilisent tel quel. Nous, nous n’avons utilisé aucun modèle : nous sommes partis de zéro avec notre propre logo (The Arma Of Efe), notre propre lien de blog et un hash spécifique qui commence et finit par efe. Je détaille ci-dessous, étape par étape, la démarche suivie et les essais qui l’ont jalonnée.

Le hashquine PNG au dragon de Retr0id, qui affiche son propre MD5

Le hashquine PNG de David « Retr0id » Buchanan, MD5 1337e2ef42b9bee8de06a4d223a51337. Image : Retr0id, via corkami/collisions.

Qu’est-ce qu’un hash et pourquoi change-t-il à chaque lettre ?

Un hash (empreinte) est une suite de longueur fixe extraite du contenu d’un fichier, une sorte d’empreinte digitale. MD5 est une fonction de hachage conçue par Ronald Rivest en 1991 : que l’entrée fasse 1 octet ou 50 Go, la sortie fait toujours 128 bits, soit 32 chiffres composés de 0-9 et a-f.

La propriété essentielle de ces fonctions est l’effet avalanche : la moindre modification de l’entrée change l’intégralité de la sortie. Essayez d’écrire quelque chose dans le champ ci-dessous :

Le paradoxe de la poule et de l’œuf

À cause de l’effet avalanche, une image qui porterait son propre MD5 semble d’abord impossible :

  1. On dessine l’image et on calcule son MD5, par exemple 4a8c91e0….
  2. On écrit ce code dans l’image et on enregistre.
  3. Les pixels ayant changé, le MD5 du fichier devient autre chose, par exemple 9f02d71a….
  4. On écrit le nouveau code, et l’empreinte change encore.

Pour sortir de cette boucle, il faut agir sur le fonctionnement interne de MD5.

L’idée qui brise la boucle : des clés qui ne modifient pas le MD5

MD5 ne traite pas le fichier d’un seul bloc. Il le découpe en blocs de 64 octets et les traite dans l’ordre : l’état initial (IV) se combine au premier bloc et produit un état intermédiaire (IHV). Cet état se combine ensuite au bloc suivant, et ainsi de suite jusqu’à la fin du fichier. Le dernier état intermédiaire constitue le MD5 de 32 caractères.

Le point clé : il existe deux morceaux de données différents (A et B), de 128 octets chacun et alignés sur la limite de 64 octets, qui aboutissent au même état intermédiaire. C’est une collision à préfixe identique, et des outils comme FastColl savent la produire en peu de temps. Comme chaque bloc suivant voit le même état, le résultat est le suivant :

  • si le morceau A est placé, un petit trait apparaît à l’écran ; si c’est B, il disparaît,
  • mais le MD5 final ne change jamais.

Chaque paire de collision est donc une clé qui s’active ou se désactive sans altérer le MD5. On calcule d’abord le MD5 du fichier, puis on règle les clés pour qu’elles dessinent exactement cette empreinte. Le MD5 restant inchangé, la boucle est rompue.

Comment l’arc a été dessiné lettre par lettre ?

Dans notre fichier, 32 caractères suivent la courbe du logo, de haut en bas. Chaque caractère est un chiffre à sept segments, et chaque segment est dessiné par sa propre clé : au total 224 clés. Le curseur permet de suivre la façon dont l’empreinte se place sur l’arc :

Comme nous n’avons utilisé aucun modèle, le PNG devait passer simultanément quatre niveaux de vérification :

  1. Alignement sur 64 octets : chaque clé doit tomber exactement sur la limite décalage % 64 == 0 du fichier. Nous avons inséré dans le flux de compression DEFLATE des blocs vides de longueur nulle pour aligner chaque clé sur cette limite.
  2. Filtres Sub et Up du PNG : nous avons rendu noirs les indices 0..254 de la palette et seul l’indice 255 blanc. Les deux morceaux d’une paire de collision diffèrent par le bit de poids fort de quelques octets. Dans une ligne filtrée en Sub, cette différence décale de 128 les pixels qui suivent et devient un trait horizontal ; les lignes filtrées en Up le font descendre. Nous avons choisi les octets suivant la clé de sorte que le trait soit exactement 255 (blanc) dans un état et noir dans l’autre.
  3. Compensation Adler-32 du zlib : à la décompression, les données compressées passent par une somme de contrôle Adler-32, et chaque clé fait varier cette somme de plusieurs centaines d’unités. Nous avons placé 160 clés de compensation dans les lignes noires ; le sous-ensemble qui rétablit exactement la somme a été choisi par programmation dynamique et recherche meet-in-the-middle.
  4. Vérification CRC-32 des IDAT : chaque segment IDAT se termine par un CRC-32 de 32 bits. Nous avons ajouté 40 blocs supplémentaires juste après le flux compressé, puis résolu un système d’équations linéaires sur GF(2) par élimination de Gauss afin de fixer le CRC-32 à 0x1807EFE0.

Hash personnalisé : chaque caractère fixé multiplie le travail par 16

Il ne suffisait pas que le fichier affiche son propre MD5 : nous voulions que le hash commence et finisse par efe. Pour cela, nous avons modifié le bloc nonce de 64 octets en fin de fichier et essayé des milliards de hash.

Comme chaque chiffre peut prendre 16 valeurs, chaque nouveau chiffre fixé multiplie en moyenne le nombre d’essais par 16 : pour N chiffres fixés, il faut en moyenne 16^N essais. Une simple boucle C sur le processeur 24 cœurs teste 177 millions de MD5 par seconde. Avec OpenCL sur la carte graphique portable RTX 5070, la cadence atteint 3,54 milliards par seconde, soit environ 20 fois plus. Pour efe23…23efe, il faut en moyenne 1,1 trillion d’essais ; le nôtre est apparu au 90 milliardième essai, en 25 secondes environ.

Changez le nombre de chiffres fixés avec le curseur ; les résultats réellement trouvés apparaissent sur les points marqués :

Vérifiez par vous-même

Téléchargez l’image et exécutez la commande dans un terminal. Sous Windows, utilisez certutil -hashfile fichier.png MD5 ; sous macOS, md5 fichier.png.

$ md5sum the-arma-of-efe-23-hashquine.png the-arma-of-efe-hashquine.png
efe235ae1b88c53e73d1c11515623efe  the-arma-of-efe-23-hashquine.png
efe8d2bee9dc7b5815f72581e5c17efe  the-arma-of-efe-hashquine.png

Les 32 chiffres affichés correspondent exactement au code écrit de haut en bas sur l’arc.

Le code qui génère l’image est entièrement disponible sur GitHub : the-arma-of-owl/the-arma-of-efe-hashquine. Le squelette des collisions y figure aussi, vous pouvez donc produire un nouveau hashquine avec votre propre valeur de nonce.

Références: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗