Ein PNG, das seinen eigenen MD5-Hash zeigt: The Arma Of Efe hashquine
Wie wir ein PNG erzeugt haben, das seinen eigenen MD5-Hash in die eigenen Pixel schreibt, ganz ohne fertige Vorlage? Mit MD5, Kollisionsschlüsseln, PNG-Schichten und der Suche nach efe23…23efe auf einer RTX 5070, erklärt in einer interaktiven Darstellung.

Das Bild oben ist kein gewöhnliches Logo. Auf dem Bogen rechts steht von oben nach unten efe235ae1b88c53e73d1c11515623efe, und das ist der MD5-Hash der Datei selbst. Wenn du das Bild herunterlädst und md5sum ausführst, erhältst du dieselben 32 Zeichen.
Solche Dateien nennt man Hashquine. Das bekannteste Beispiel im Netz ist das PNG mit dem Drachen von retr0id, und die meisten nehmen diese fertige Vorlage. Wir haben dagegen nichts vorgefertigt übernommen, sondern alles von Grund auf mit unserem eigenen Logo (The Arma Of Efe), unserem eigenen Blog-Link und einem eigenen Hash gebaut, der mit efe beginnt und mit efe endet. Im Folgenden erkläre ich Schritt für Schritt, was wir dabei ausprobiert haben.

Das PNG-Hashquine von David „Retr0id“ Buchanan, MD5 1337e2ef42b9bee8de06a4d223a51337. Bild: Retr0id, über corkami/collisions.
Was ist ein Hash, und warum ändert er sich bei jedem Buchstaben?
Ein Hash (Prüfsumme) ist ein Fingerabdruck fester Länge, der aus dem Inhalt einer Datei berechnet wird. MD5 ist eine Hash-Funktion, die Ronald Rivest 1991 entworfen hat. Egal ob die Eingabe 1 Byte oder 50 GB groß ist, die Ausgabe ist immer 128 Bit lang, also 32 Zeichen aus 0-9 und a-f.
Die wichtigste Eigenschaft solcher Funktionen ist der Lawineneffekt: Schon die kleinste Änderung der Eingabe verändert die Ausgabe vollständig. Probiere es aus, indem du unten etwas eintippst:
Das Henne-Ei-Problem
Wegen des Lawineneffekts wirkt ein Bild, das seinen eigenen MD5-Hash enthält, zunächst unmöglich:
- Du zeichnest das Bild und berechnest seinen MD5, zum Beispiel
4a8c91e0…. - Du schreibst diesen Code ins Bild und speicherst es.
- Weil sich die Pixel geändert haben, ist der MD5 der Datei jetzt ein anderer, zum Beispiel
9f02d71a…. - Du schreibst den neuen Code hinein, und der Hash ändert sich wieder.
Um diesen Kreislauf zu durchbrechen, muss man in das Innere von MD5 schauen.
Die Idee, die den Kreislauf bricht: Schlüssel, die den MD5 nicht verändern
MD5 verarbeitet eine Datei nicht auf einmal. Sie wird in 64-Byte-Blöcke zerlegt, die nacheinander verarbeitet werden: Der Startzustand (IV) wird mit dem ersten Block verrechnet und ergibt einen Zwischenzustand (IHV). Dieser Zwischenzustand wird mit dem nächsten Block verrechnet, und so weiter bis zum Ende der Datei. Der letzte Zwischenzustand ist der 32-stellige MD5 selbst.
Entscheidend ist: Es gibt zwei unterschiedliche Datenstücke A und B von jeweils 128 Byte, die an der 64-Byte-Grenze ausgerichtet sind und beide im selben Zwischenzustand enden. Das nennt man eine Kollision mit gleichem Präfix, und Werkzeuge wie FastColl erzeugen sie in kurzer Zeit. Da jeder Block nach diesem Stück denselben Zwischenzustand vorfindet:
- Wird
Aeingesetzt, erscheint auf dem Bild ein Strich, wirdBeingesetzt, verschwindet er, - aber der MD5 am Dateiende ändert sich nie.
Jedes Kollisionspaar ist also ein Schlüssel, der sich ein- und ausschalten lässt, ohne den MD5 zu zerstören. Zuerst berechnest du den MD5 der Datei, dann stellst du die Schlüssel so ein, dass genau dieser Hash entsteht. Da der Hash unverändert bleibt, ist der Kreislauf durchbrochen.
Wie wurde der Bogen Buchstabe für Buchstabe gezeichnet?
In unserer Datei stehen 32 Zeichen von oben nach unten auf einem Bogen, der dem Schwung des Logos folgt. Jedes Zeichen ist eine siebensegmentige Ziffer, und jedes Segment wird von einem eigenen Schlüssel gezeichnet: insgesamt 224 Schlüssel. Mit dem Schieberegler kannst du verfolgen, wie der Hash auf dem Bogen platziert ist:
Da wir keine fertige Vorlage verwendet haben, mussten wir alle vier Prüfebenen des PNGs gleichzeitig bestehen:
- Ausrichtung auf 64 Byte: Jeder Schlüssel muss in der Datei genau auf einer Grenze
Offset % 64 == 0liegen. Dafür haben wir in den DEFLATE-Stream leere Blöcke mit der Länge null eingefügt, um jeden Schlüssel auf diese Grenze auszurichten. - PNG-Filter
SubundUp: Die Palettenindizes0..254haben wir schwarz gemacht und nur den Index255weiß. Die beiden Teile eines Kollisionspaars unterscheiden sich in einigen Bytes nur im höchsten Bit. Im ZeilenfilterSubverschiebt dieser Unterschied die folgenden Pixel um 128, sodass daraus eine waagerechte Linie wird; Zeilen mit dem FilterUpübertragen sie nach unten. Die Bytes nach dem Schlüssel haben wir so gewählt, dass die Linie in einem Zustand genau255(weiß) ist und im anderen schwarz. - Ausgleich der Zlib-
Adler-32-Prüfsumme: Beim Entpacken der komprimierten Daten wird dieAdler-32-Prüfsumme kontrolliert, und jeder Schlüssel verschiebt diese Summe um einige hundert Einheiten. Für die schwarzen Zeilen haben wir 160 Ausgleichsschlüssel gesetzt. Die Teilmenge, die die Summe genau wieder herstellt, haben wir mit dynamischer Programmierung und einer Meet-in-the-Middle-Suche gewählt. CRC-32-Prüfung derIDAT-Blöcke: Am Ende jedesIDAT-Blocks steht eine 32-Bit-CRC-32-Prüfsumme. Direkt hinter den komprimierten Stream haben wir 40 zusätzliche Blöcke gesetzt und ein lineares Gleichungssystem über GF(2) mit Gauß-Elimination gelöst. So haben wir denCRC-32-Wert auf0x1807EFE0festgelegt.
Der eigene Hash: Jede Stelle vervielfacht den Aufwand
Es reichte nicht, dass die Datei ihren eigenen MD5 zeigt; der Hash sollte außerdem mit efe beginnen und mit efe enden. Dafür haben wir einen 64 Byte großen Nonce-Block am Dateiende verändert und Milliarden Hashes ausprobiert.
Jede Stelle kann 16 verschiedene Werte annehmen. Jede zusätzlich festgelegte Stelle erhöht daher die durchschnittliche Anzahl der Versuche um den Faktor 16: Für N feste Stellen braucht man im Mittel 16^N Versuche. Auf dem 24-Kern-Prozessor probiert eine einfache C-Schleife 177 Millionen MD5 pro Sekunde. Mit einem OpenCL-Kernel, der direkt über libOpenCL.so auf der Grafikkarte des Laptops RTX 5070 läuft, steigt die Geschwindigkeit auf 3,54 Milliarden pro Sekunde, also etwa das 20-Fache. Für efe23…23efe braucht man im Schnitt 1,1 Billionen Versuche; unserer kam beim 90-milliardsten Versuch, nach rund 25 Sekunden.
Verändere mit dem Schieberegler die Anzahl der Stellen. Die Ergebnisse, die wir tatsächlich gefunden haben, sind an den markierten Punkten zu sehen:
Selbst überprüfen
Lade das Bild herunter und führe es im Terminal aus. Unter Windows kannst du certutil -hashfile dateiname.png MD5 verwenden, unter macOS md5 dateiname.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
Die 32 Zeichen in der Ausgabe sind genau derselbe Code, der von oben nach unten auf dem Bogen steht.
Der Code, der das Bild erzeugt, ist vollständig auf GitHub verfügbar: the-arma-of-owl/the-arma-of-efe-hashquine. Da auch das Kollisionsgerüst im Repository liegt, kannst du mit deinem eigenen Nonce-Wert einen neuen Hashquine erzeugen.

- Durchschnittliche Versuche
- 24-Kern-CPU, 177 Millionen pro Sekunde
- RTX 5070 Laptop, 3,54 Milliarden pro Sekunde
Was wir gefunden haben
efe…efe: auf der GPU in einer Drittelsekunde gefunden (1,06 Milliarden Versuche).
Was wir gefunden haben
efe23…23efe: im Schnitt etwa 1,1 Billionen Versuche; unserer kam nach 90 Milliarden, in etwa 25 Sekunden.
Was wir gefunden haben
efe1807…1807efe: nur berechnet, nie gesucht.
the-arma-of-owl/the-arma-of-efe-hashquine
Der Generator hinter den Bildern in diesem Beitrag: Kollisionsgerüst, Sieben-Segment-Ziffern, Korrektur der Prüfsummen und die Nonce-Suche auf der GPU.
Quellen: Retr0id - MD5 collision with CRC32 preimage ↗ · Ange Albertini - Hashquines ↗
