← Blog

PNG che mostra il proprio digest MD5: The Arma Of Efe hashquine

Come abbiamo costruito un PNG che scrive il proprio digest MD5 nei propri pixel, senza usare un modello pronto? MD5, chiavi di collisione, livelli PNG e la ricerca efe23…23efe con una RTX 5070, con spiegazioni interattive.

L’immagine qui sopra non è un semplice logo. Sull’arco a destra, dall’alto verso il basso, è scritto efe235ae1b88c53e73d1c11515623efe, ed è il digest MD5 del file stesso. Se scaricate l’immagine ed eseguite md5sum, vedrete le stesse 32 cifre.

File di questo tipo si chiamano hashquine. L’esempio più famoso in circolazione è il PNG con il drago di retr0id, e molti usano quel modello già pronto. Noi, senza usare alcun modello, lo abbiamo costruito da zero con il nostro logo (The Arma Of Efe), il nostro link al blog e un digest personalizzato che inizia e finisce con efe. Qui sotto racconto passo dopo passo, come è andata, per tentativi.

L’hashquine PNG con il drago di Retr0id, che mostra il proprio MD5

L’hashquine PNG di David “Retr0id” Buchanan, MD5 1337e2ef42b9bee8de06a4d223a51337. Immagine: Retr0id, tramite corkami/collisions.

Cos’è un hash e perché cambia a ogni lettera?

Un hash (digest) è un’impronta digitale di lunghezza fissa ricavata dal contenuto di un file. MD5 è una funzione di digest progettata da Ronald Rivest nel 1991: che l’input sia di 1 byte o di 50 GB, l’output è sempre di 128 bit, cioè 32 cifre composte dai caratteri 0-9 e a-f.

La proprietà fondamentale delle funzioni di digest è l’effetto valanga: la più piccola modifica dell’input cambia l’output dall’inizio alla fine. Provate a scrivere qualcosa qui sotto:

Il problema dell’uovo e della gallina

A causa dell’effetto valanga, un’immagine che contiene al proprio interno il proprio MD5 sembra a prima vista impossibile:

  1. Disegnate l’immagine e calcolatene l’MD5, ad esempio 4a8c91e0….
  2. Scrivete quel codice sull’immagine e salvatela.
  3. Poiché i pixel sono cambiati, l’MD5 del file è ora un altro, ad esempio 9f02d71a….
  4. Scrivete il nuovo codice, e il digest cambia ancora.

Per spezzare questo ciclo bisogna guardare dentro l’MD5.

L’idea che rompe il ciclo: chiavi che non alterano l’MD5

MD5 non elabora il file in un colpo solo. Lo divide in blocchi da 64 byte e li elabora in sequenza: lo stato iniziale (IV) si combina con il primo blocco e produce uno stato intermedio (IHV). Questo stato intermedio si combina con il blocco successivo, e così via fino alla fine del file. L’ultimo stato intermedio è l’MD5 di 32 cifre.

Il punto chiave è questo: possono esistere due diversi frammenti di dati da 128 byte (A e B), allineati al limite di 64 byte, che producono lo stesso stato intermedio. Si chiama collisione a prefisso comune, e strumenti come FastColl la producono in poco tempo. Poiché ogni blocco successivo a quel frammento vede lo stesso stato intermedio:

  • se nel file compare il frammento A, sullo schermo appare un segmento di linea; se compare B, non appare nulla,
  • ma l’MD5 finale del file non cambia mai.

Quindi ogni coppia di collisione è una chiave che si apre e si chiude senza alterare l’MD5. Prima si calcola l’MD5 del file, poi si regolano le chiavi in modo che disegnino proprio quel digest. Poiché il digest non cambia, il ciclo si spezza.

Come è stato disegnato l’arco, lettera per lettera

Nel nostro file, 32 caratteri sono disposti dall’alto verso il basso lungo una curva che segue l’arco del logo. Ogni carattere è una cifra a sette segmenti e ogni segmento è disegnato da una chiave separata: in totale 224 chiavi. Con il cursore potete seguire come il digest si dispone sull’arco:

Poiché non abbiamo usato alcun modello pronto, il PNG doveva superare contemporaneamente quattro livelli di verifica:

  1. Allineamento a 64 byte: ogni chiave deve cadere esattamente sul limite offset % 64 == 0 del file. Abbiamo allineato ogni chiave aggiungendo blocchi vuoti di lunghezza zero al flusso di compressione DEFLATE.
  2. Filtri Sub e Up di PNG: abbiamo colorato di nero gli indici della tavolozza 0..254 e di bianco il solo indice 255. Le due parti di una collisione si distinguono nel bit più alto di alcuni byte. Nella riga con filtro Sub questa differenza sposta di 128 i pixel che seguono e diventa una linea orizzontale; le righe con filtro Up la spostano verso il basso. I byte dopo la chiave sono stati scelti in modo che la linea sia di un bianco pieno (255) in uno dei due casi e nero nell’altro.
  3. Compensazione Adler-32 dello zlib: in fase di decompressione i dati compressi passano per il checksum Adler-32, e ogni chiave sposta questa somma di alcune centinaia di unità. Abbiamo inserito 160 chiavi di compensazione nelle righe nere, scegliendo il sottoinsieme che riporta esattamente la somma con la programmazione dinamica e una ricerca meet-in-the-middle.
  4. Verifica CRC-32 dei blocchi IDAT: alla fine di ogni blocco IDAT c’è un CRC-32 a 32 bit. Subito dopo il flusso compresso abbiamo inserito 40 blocchi extra e, risolvendo con l’eliminazione di Gauss un sistema di equazioni lineari su GF(2), abbiamo fissato il valore di CRC-32 a 0x1807EFE0.

Digest personalizzato: ogni cifra moltiplica il lavoro per 16

Non bastava che il file mostrasse il proprio MD5: volevamo che il digest iniziasse con efe e finisse con efe. Per questo abbiamo modificato il blocco di nonce da 64 byte alla fine del file, provando miliardi di digest.

Poiché ogni cifra può assumere 16 valori diversi, ogni cifra fissata in più moltiplica per 16 il numero medio di tentativi: per N cifre fisse servono in media 16^N tentativi. Un semplice ciclo in C, sul processore a 24 core, prova 177 milioni di MD5 al secondo. Facendo lo stesso lavoro con OpenCL sulla scheda grafica RTX 5070 del portatile, la velocità sale a 3,54 miliardi al secondo, circa 20 volte di più. Per efe23…23efe servono in media 1.100 miliardi di tentativi; il nostro è arrivato al novantesimo miliardo, in circa 25 secondi.

Muovete il cursore per cambiare il numero di cifre; i risultati che abbiamo trovato davvero sono indicati dai punti contrassegnati:

Verificatelo da soli

Scaricate l’immagine ed eseguitela nel terminale. Su Windows potete usare certutil -hashfile file.png MD5, su macOS md5 file.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

Le 32 cifre dell’output coincidono esattamente con il codice che scorre sull’arco dall’alto verso il basso.

Il codice che genera l’immagine è interamente su GitHub: the-arma-of-owl/the-arma-of-efe-hashquine. Poiché anche lo scheletro delle collisioni è nel repository, potete generare un nuovo hashquine con il vostro valore di nonce.

Fonti: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗