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 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:
- Disegnate l’immagine e calcolatene l’MD5, ad esempio
4a8c91e0…. - Scrivete quel codice sull’immagine e salvatela.
- Poiché i pixel sono cambiati, l’MD5 del file è ora un altro, ad esempio
9f02d71a…. - 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 compareB, 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:
- Allineamento a 64 byte: ogni chiave deve cadere esattamente sul limite
offset % 64 == 0del file. Abbiamo allineato ogni chiave aggiungendo blocchi vuoti di lunghezza zero al flusso di compressione DEFLATE. - Filtri
SubeUpdi PNG: abbiamo colorato di nero gli indici della tavolozza0..254e di bianco il solo indice255. Le due parti di una collisione si distinguono nel bit più alto di alcuni byte. Nella riga con filtroSubquesta differenza sposta di 128 i pixel che seguono e diventa una linea orizzontale; le righe con filtroUpla 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. - Compensazione
Adler-32dello zlib: in fase di decompressione i dati compressi passano per il checksumAdler-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. - Verifica
CRC-32dei blocchiIDAT: alla fine di ogni bloccoIDATc’è unCRC-32a 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 diCRC-32a0x1807EFE0.
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.

- Tentativi medi
- CPU a 24 core, 177 milioni al secondo
- RTX 5070 Laptop, 3,54 miliardi al secondo
Quello che abbiamo trovato
efe…efe: trovato sulla GPU in un terzo di secondo (1,06 miliardi di tentativi).
Quello che abbiamo trovato
efe23…23efe: circa 1.100 miliardi di tentativi in media; il nostro è arrivato dopo 90 miliardi, in circa 25 secondi.
Quello che abbiamo trovato
efe1807…1807efe: solo calcolato, mai cercato.
the-arma-of-owl/the-arma-of-efe-hashquine
Il generatore delle immagini di questo articolo: scheletro delle collisioni, cifre a sette segmenti, correzione dei checksum e ricerca del nonce sulla GPU.
Fonti: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗
