Zwei Dateien, ein Fingerabdruck: Chosen-Prefix-Kollisionen und wie Hashfunktionen wirklich brechen

Der Aufhänger: Die Unterschrift, die auf das falsche Dokument passt

Am 30. Dezember 2008 stand eine Gruppe von sieben Forschern auf der Bühne des 25. Chaos Communication Congress in Berlin und zeigte ein Zertifikat. Es war kein gestohlenes Zertifikat, keines, das aus einer kompromittierten Datenbank stammte, und niemand hatte einen privaten Schlüssel erbeutet. Es war ein völlig regulär signiertes Zertifikat einer echten, damals weltweit anerkannten Zertifizierungsstelle – mit einem Unterschied: Es erlaubte seinem Besitzer, selbst beliebige weitere Zertifikate auszustellen. Für jede Domain. Für jede Bank. Für jeden Dienst im Internet.

Die Zertifizierungsstelle hatte nie vorgehabt, das zu tun. Sie hatte etwas völlig Harmloses signiert: ein gewöhnliches Serverzertifikat für eine unauffällige Testdomain, bezahlt mit einer Kreditkarte, Gesamtkosten des Projekts 657 US-Dollar. Nur hatte das, was sie signierte, denselben MD5-Hashwert wie das Zertifikat, das die Forscher eigentlich haben wollten. Und eine digitale Signatur unterschreibt nicht das Dokument. Sie unterschreibt seinen Hashwert.

Das ist der Kern dieses Artikels, und es ist eine Erkenntnis, die in der Praxis immer noch regelmäßig verfehlt wird. Jede digitale Signatur, jeder Software-Nachweis, jeder Git-Commit, jede Integritätsprüfung beruht auf einer stillen Annahme: dass zwei verschiedene Dinge nicht denselben Fingerabdruck haben können. Diese Annahme ist keine mathematische Gewissheit. Sie ist eine Rechenannahme – eine Behauptung darüber, wie teuer es ist, ein Gegenbeispiel zu finden. Und der Preis dieses Gegenbeispiels fällt, Jahr für Jahr, mit jeder Veröffentlichung und jeder Generation von Grafikkarten.

Was diesen Artikel lohnend macht, ist nicht die Nachricht "MD5 ist kaputt" – die ist seit zwei Jahrzehnten alt. Es ist die Frage, die darunter liegt: Was genau bricht eigentlich, wenn eine Hashfunktion bricht? Denn zwischen "jemand hat zwei Zufallsdateien mit gleichem Hash gefunden" und "jemand kann ein beliebiges Dokument fälschen" liegen mehrere Angriffsklassen mit völlig unterschiedlichen Konsequenzen. Wer sie nicht unterscheiden kann, trifft bei jeder Migrationsentscheidung die falsche Risikoabschätzung – in beiden Richtungen.

Teil 1: Was eine Hashfunktion verspricht – und was davon zählt

Drei Eigenschaften, drei Schwierigkeitsgrade

Eine kryptographische Hashfunktion H nimmt eine Eingabe beliebiger Länge und erzeugt eine Ausgabe fester Länge – 128 Bit bei MD5, 160 Bit bei SHA-1, 256 Bit bei SHA-256. Von ihr werden drei Eigenschaften erwartet, und es ist entscheidend, sie auseinanderzuhalten, weil sie unterschiedlich schwer zu brechen sind und unterschiedliche Angriffe ermöglichen.

Preimage-Resistenz (Einwegeigenschaft): Zu einem gegebenen Hashwert h ist es praktisch unmöglich, irgendeine Eingabe m mit H(m) = h zu finden. Das ist die Eigenschaft, die Passwort-Hashes schützt.

Second-Preimage-Resistenz: Zu einer gegebenen Nachricht m₁ ist es praktisch unmöglich, eine andere Nachricht m₂ ≠ m₁ mit demselben Hashwert zu finden. Das ist die Eigenschaft, die man braucht, wenn ein fremdes, bereits existierendes Dokument gefälscht werden soll.

Kollisionsresistenz: Es ist praktisch unmöglich, irgendein Paar (m₁, m₂) mit m₁ ≠ m₂ und H(m₁) = H(m₂) zu finden. Hier darf der Angreifer beide Nachrichten frei wählen – und genau das macht diese Eigenschaft zur schwächsten der drei.

Der praktisch wichtigste Punkt dieses Abschnitts lautet: Alle bekannten praktischen Angriffe auf MD5 und SHA-1 brechen ausschließlich die Kollisionsresistenz. Weder MD5 noch SHA-1 sind preimage-gebrochen. Niemand kann aus einem gegebenen MD5-Hash ein passendes Dokument rekonstruieren, und niemand kann zu einem bereits existierenden Vertrag ein zweites, abweichendes Dokument mit gleichem Hash erzeugen. Das klingt beruhigend und ist in Teilen auch beruhigend – es ist der Grund, warum alte, bereits vor dem Angriff existierende MD5-Signaturen nicht nachträglich fälschbar sind. Nur ist es gleichzeitig irrelevant für das, was Angreifer tatsächlich tun: Sie erzeugen beide Dokumente selbst, lassen sich das harmlose signieren und tauschen es gegen das gefährliche aus.

Die Geburtstagsschranke: warum die halbe Ausgabelänge zählt

Kollisionsresistenz hat eine prinzipielle, unüberwindbare Obergrenze. Bei einer Ausgabe von n Bit gibt es 2ⁿ mögliche Hashwerte. Man könnte naiv erwarten, dass man etwa 2ⁿ Versuche braucht, um eine Kollision zu finden. Das ist falsch, und zwar um die Quadratwurzel.

Das Geburtstagsparadox liefert die korrekte Schranke: Zieht man etwa 2^(n/2) Zufallswerte, liegt die Wahrscheinlichkeit, dass zwei von ihnen übereinstimmen, bereits über 50 Prozent. Der Grund ist, dass die Anzahl der Paare in einer Menge von k Elementen quadratisch mit k wächst – bei k Werten gibt es k(k−1)/2 Paare, und jedes einzelne hat die Chance 2⁻ⁿ, eine Kollision zu sein.

Für MD5 bedeutet das: Kollisionsresistenz war von Anfang an nur auf 2⁶⁴ Operationen ausgelegt, nicht auf 2¹²⁸. Für SHA-1: 2⁸⁰, nicht 2¹⁶⁰. Diese Zahlen sind nicht Schwächen der Konstruktion, sie sind die Decke, die die Ausgabelänge setzt. Jeder Angriff, der unter dieser Decke bleibt, ist eine echte kryptanalytische Leistung; jeder, der sie erreicht, ist bloß Brute Force mit viel Hardware.

Daraus folgt die wichtigste Entwurfsregel überhaupt: Die Sicherheit gegen Kollisionen ist halb so groß, wie die Ausgabelänge suggeriert. Eine 256-Bit-Hashfunktion bietet 128 Bit Kollisionssicherheit. Wer im Entwurf eine 128-Bit-Ausgabe wählt, weil "128 Bit doch sicher ist", hat in Wahrheit 64 Bit Kollisionssicherheit gewählt – und das ist seit Jahren im Bereich dessen, was Rechenzentren an einem Wochenende erledigen.

Merkle–Damgård: die Konstruktion, die Kollisionen fortsetzbar macht

MD5, SHA-1 und die gesamte SHA-2-Familie teilen eine innere Struktur, die Merkle–Damgård-Konstruktion. Die Nachricht wird in Blöcke fester Länge zerlegt (512 Bit bei MD5 und SHA-1). Es gibt einen internen Zustand, der mit einem festen Anfangswert (IV) startet. Dann wird Block für Block eine Kompressionsfunktion angewendet: Sie nimmt den aktuellen Zustand und den nächsten Nachrichtenblock und erzeugt den neuen Zustand. Am Ende ist der Zustand der Hashwert.

Diese Konstruktion hat eine Eigenschaft, die für unser Thema alles entscheidet. Nehmen wir an, es gibt zwei verschiedene Nachrichten m₁ und m₂, die nach ihrer Verarbeitung denselben internen Zustand erzeugen. Dann gilt für jeden beliebigen Anhang s:

H(m₁ ‖ s) = H(m₂ ‖ s)

Denn sobald der Zustand identisch ist, verarbeitet die Funktion das Suffix in beiden Fällen gleich und kann die Vorgeschichte nicht mehr unterscheiden. Eine Kollision ist also kein Punktereignis, sondern eine Weiche: zwei Pfade, die zusammenlaufen und danach beliebig gemeinsam fortgesetzt werden können.

Das ist der Mechanismus hinter praktisch allen realen Kollisionsangriffen. Man findet keine zwei vollständigen, fertigen Dokumente mit gleichem Hash. Man findet zwei kurze, unterschiedliche Kollisionsblöcke – meist wenige hundert Byte Binärmüll – und hängt an beide denselben, beliebig langen Rest an. Deshalb sahen die beiden PDFs im SHAttered-Angriff von 2017 unterschiedlich aus und hatten dennoch denselben SHA-1-Wert: Der Unterschied steckte in wenigen Blöcken, die ein JPEG-Objekt innerhalb der PDF-Struktur steuerten.

Die zweite, verwandte Schwäche derselben Konstruktion ist die Längenerweiterung (length extension): Wer H(m) und die Länge von m kennt, kann ohne Kenntnis von m den Wert H(m ‖ padding ‖ s) für ein selbstgewähltes s berechnen – weil der Hashwert eben der interne Zustand ist. MD5, SHA-1 und SHA-256 sind davon betroffen; genau deshalb ist ein naives H(geheimnis ‖ nachricht) als Nachrichtenauthentifizierung ein Fehler und HMAC die richtige Antwort. SHA-3 (Keccak, standardisiert als FIPS 202 im Jahr 2015) verwendet stattdessen eine Schwammkonstruktion und ist nicht längenerweiterbar; SHA-512/256, also die abgeschnittene Variante, ebenfalls nicht.

Teil 2: Die Taxonomie des Bruchs – vier Angriffsklassen

Hier liegt der eigentliche Erkenntnisgewinn, und hier wird in der Praxis am meisten durcheinandergeworfen. "Die Hashfunktion ist gebrochen" ist keine binäre Aussage. Es gibt eine Leiter von Angriffsklassen, die exponentiell teurer und zugleich exponentiell nützlicher werden.

Identical-Prefix-Kollision

Der Angreifer wählt einen gemeinsamen Anfang P – oder akzeptiert einen leeren Anfang – und findet dann zwei unterschiedliche Fortsetzungen C₁ ≠ C₂, sodass H(P ‖ C₁) = H(P ‖ C₂). Beide Dokumente beginnen zwangsläufig identisch.

Das reicht für aufsehenerregende Demonstrationen: zwei PDFs, die verschiedene Inhalte zeigen, zwei PostScript-Dateien, zwei Programme mit unterschiedlichem Verhalten. Der Trick ist stets derselbe: Man baut ein Dateiformat so, dass der gemeinsame Präfix einen Weichenschalter enthält, dessen Wert in den Kollisionsblöcken liegt, und platziert danach beide Varianten des Inhalts im gemeinsamen Suffix. Das Format entscheidet dann, welche Variante angezeigt wird.

Für Angriffe auf Zertifikate oder auf von anderen signierte Dokumente reicht es nicht. Denn dort bestimmt nicht der Angreifer den Anfang des Dokuments, sondern die Zertifizierungsstelle oder das Format.

Chosen-Prefix-Kollision – der eigentliche Hebel

Hier wird es ernst. Der Angreifer gibt sich zwei verschiedene, frei gewählte Präfixe P₁ und P₂ vor und findet Kollisionsblöcke C₁, C₂ mit:

H(P₁ ‖ C₁) = H(P₂ ‖ C₂)

Der Unterschied ist qualitativ, nicht quantitativ. Jetzt darf der Angreifer beide Anfänge beliebig mit Inhalt füllen – etwa mit zwei völlig unterschiedlichen Zertifikatsfeldern, zwei unterschiedlichen PGP-Identitäten, zwei unterschiedlichen Dateiköpfen. Danach läuft alles zusammen und bleibt für immer gleich. Genau das macht eine signierte Aussage über das eine Dokument automatisch zu einer gültigen Signatur für das andere.

Die Rogue-CA-Demonstration von 2008 und der Flame-Angriff von 2012 beruhen beide darauf. Und sie erklären, warum die Fachwelt nach dem Erscheinen von SHA-1 is a Shambles im Januar 2020 deutlich nervöser reagierte als nach SHAttered 2017: Nicht weil SHA-1 "noch kaputter" geworden wäre, sondern weil erst die Chosen-Prefix-Variante aus einer Kuriosität ein Werkzeug macht.

Freestart-Kollision – das Frühwarnsignal

Eine Zwischenstufe, die praktisch nichts erlaubt, aber analytisch viel aussagt: Der Angreifer darf nicht nur die Nachrichtenblöcke, sondern auch den internen Anfangszustand frei wählen, der im echten Algorithmus festgelegt ist. Das ist ein Angriff auf die Kompressionsfunktion, nicht auf die Hashfunktion. Er erzeugt keine kollidierenden Dateien. Aber er zeigt, dass die differentiellen Pfade funktionieren, und erlaubt eine belastbare Kostenschätzung für den echten Angriff. Die SHAppening-Veröffentlichung von Stevens, Karpman und Peyrin im Oktober 2015 war genau das – und sie war der Grund, weshalb die Browserhersteller ihre Zeitpläne für den SHA-1-Ausstieg vorzogen.

Second Preimage – die Stufe, die bis heute nicht gefallen ist

Zu einem gegebenen, fremden Dokument ein zweites mit gleichem Hash finden. Für MD5 und SHA-1 ist das praktisch unerreicht; die bekannten Angriffe liefern es nicht. Diese Grenze ist der Grund, weshalb Aussagen wie "jedes MD5-signierte Dokument ist fälschbar" falsch sind. Richtig ist: Jedes Dokument, das ein Angreifer selbst mitgestalten durfte, bevor es signiert wurde, ist kompromittierbar.

Die Angriffsklassen im Überblick

Die Tabelle enthält die eigentliche Handlungsanweisung für jede Risikobewertung. Die Frage ist nie "ist MD5 oder SHA-1 im Einsatz", sondern: Darf ein Angreifer irgendeinen Teil der Daten mitgestalten, bevor sie gehasht und signiert werden? Lautet die Antwort ja, ist der Einsatz unhaltbar. Lautet sie nein – etwa bei einer Prüfsumme über eine Datei, die vollständig unter eigener Kontrolle entstanden ist und deren Hash man zum Vergleich mit einer selbst erstellten Referenz nutzt –, ist das Risiko deutlich geringer, als die Schlagzeilen vermuten lassen. Es verschwindet nur nicht, denn die Geschichte zeigt eine klare Richtung.

Teil 3: MD5 – die Chronik eines angekündigten Todes

1993 bis 1996: Die Warnungen, die niemand hören wollte

MD5 wurde 1992 von Ronald Rivest spezifiziert (RFC 1321) und war innerhalb weniger Jahre die Standard-Hashfunktion des Internets. Die ersten Risse zeigten sich früh. Bert den Boer und Antoon Bosselaers fanden 1993 eine Pseudo-Kollision, also eine Kollision der Kompressionsfunktion unter zwei verschiedenen Startzuständen. 1996 veröffentlichte Hans Dobbertin eine Kollision für die Kompressionsfunktion selbst – eine Freestart-Kollision in der Terminologie von oben.

Die Reaktion der Fachwelt war die richtige: Dobbertins Ergebnis galt als deutliche Warnung, MD5 wurde für neue Entwürfe nicht mehr empfohlen. Die Reaktion der Praxis war die übliche: MD5 blieb überall, weil nichts kaputt war, was man anfassen konnte. Zwischen "Kryptographen halten es für nicht mehr vertretbar" und "es gibt eine kollidierende Datei, die man vorzeigen kann" lagen acht Jahre. In diesen acht Jahren wurde MD5 in Zehntausende Produkte, Protokolle und Datenbankschemata eingebaut.

2004/2005: Wang und Yu

Auf der CRYPTO 2004 kündigte Xiaoyun Wang eine echte MD5-Kollision an; die ausgearbeitete Methode erschien 2005 als How to Break MD5 and Other Hash Functions von Xiaoyun Wang und Hongbo Yu auf der EUROCRYPT 2005 (LNCS 3494, S. 19–35, DOI 10.1007/11426639_2). Die Arbeit beschreibt eine differentielle Kryptanalyse mit handkonstruierten Differenzpfaden und gibt den Rechenaufwand nicht als Operationszahl, sondern schlicht als Zeit an: etwa 15 Minuten bis eine Stunde auf damaliger Hardware.

Das war der Moment, in dem MD5 als Kollisionsfunktion endete. Nicht in der Praxis – in der Praxis dauerte es noch Jahre –, aber als vertretbare Annahme.

2007 bis 2008: Von der Kollision zur Rogue CA

Die entscheidende Weiterentwicklung war nicht schneller, sondern struktureller. Marc Stevens, Arjen Lenstra und Benne de Weger zeigten 2007, wie man Chosen-Prefix-Kollisionen für MD5 konstruiert und damit kollidierende X.509-Zertifikate für verschiedene Identitäten erzeugt. Erst dieser Schritt macht aus einem Laborergebnis einen Angriff auf eine Vertrauensinfrastruktur.

Die Demonstration folgte im Dezember 2008. Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik und Benne de Weger beantragten bei RapidSSL – einer Verisign-Marke, die damals noch mit MD5 signierte – ein gewöhnliches Serverzertifikat. Der Antrag war so konstruiert, dass der zu signierende Teil des echten Zertifikats mit dem eines zweiten, von ihnen gebauten CA-Zertifikats kollidierte. Die Signatur der echten CA ließ sich anschließend auf das Rogue-Zertifikat kopieren und blieb gültig.

Was diesen Angriff lehrreich macht, ist nicht die Kryptographie, sondern alles andere daneben. Ein Chosen-Prefix-Angriff braucht Vorhersagbarkeit: Der Angreifer muss den exakten Inhalt kennen, den die CA signieren wird, bevor er die Kollision berechnet. Dazu gehörten zwei Felder, die man normalerweise nicht als Sicherheitsparameter betrachtet:

• Die Seriennummer. RapidSSL zählte sequenziell. Die Forscher behandelten das als Fernzähler, analysierten 9.251 Zertifikate, stellten fest, dass von Donnerstagnacht bis Sonntagnacht typischerweise 800 bis 1.000 Zertifikate ausgestellt wurden, und kauften gezielt Zertifikate, um den Zähler knapp unter den Zielwert zu schieben.
• Der Gültigkeitszeitraum. RapidSSL stellte Zertifikate exakt sechs Sekunden nach Bestätigung des Kaufs aus. Wer sechs Sekunden vor der gewünschten Startzeit klickte, bekam genau den vorhergesagten Zeitstempel.

Gerechnet wurde auf einem Cluster von mehr als 200 PlayStation 3 im "PlayStation Lab" der EPFL in Lausanne. Die Birthday-Phase brauchte etwa 18 Stunden und rund 30 GB Speicher, verteilt über die Konsolen; die zweite Phase lief auf einem Quad-Core-PC in drei bis zehn Stunden. Drei Versuche scheiterten an der Zeitvorhersage, der vierte gelang. Weil ein Zertifikat bis zu zwanzig Mal kostenlos neu ausgestellt werden konnte, blieben die Gesamtkosten bei 657 US-Dollar. Die Arbeit erhielt auf der CRYPTO 2009 den Best-Paper-Award. Das Rogue-CA-Zertifikat war absichtlich auf 2004 zurückdatiert und damit abgelaufen, bevor es jemand missbrauchen konnte.

Ich bin der Meinung, dass dieser Angriff bis heute das lehrreichste Beispiel für die Grenzen von Bedrohungsmodellierung ist: Die Schwachstelle war nicht MD5 allein, sondern MD5 in Kombination mit einer vorhersagbaren Seriennummer und einem vorhersagbaren Zeitstempel. Jedes einzelne dieser drei Details galt für sich genommen als unkritisch. Für diese Bewertung gibt es keinen Beweis, aber die drei Faktoren sind in der Veröffentlichung sauber dokumentiert.

2012: Flame – als es jemand ernst meinte

Alles bisher Beschriebene war Forschung mit Ankündigung. 2012 wurde in der Schadsoftware Flame ein gefälschtes Microsoft-Zertifikat gefunden, mit dem sich Schadcode über Windows Update verteilen ließ – ein Angriff auf einen der sensibelsten Signaturpfade überhaupt.

Marc Stevens analysierte das Zertifikat mit einer Technik, die er Counter-Cryptanalysis nannte: Man prüft eine Nachricht auf die Spuren, die ein Kollisionsangriff zwangsläufig hinterlässt. Das Ergebnis war bemerkenswert: Das Zertifikat war durch eine Chosen-Prefix-Kollision entstanden – aber durch eine Variante, die zu diesem Zeitpunkt in der Literatur nicht veröffentlicht war. Eine Rekonstruktion in der Masterarbeit von Max Fillinger (ILLC/CWI, 2013, betreut von Marc Stevens und Christian Schaffner) schätzte den erwarteten Aufwand des Angriffs auf mindestens 2⁴⁶·⁶ Aufrufe der MD5-Kompressionsfunktion.

Die Lehre daraus ist unangenehm und wird selten so deutlich ausgesprochen: Zum Zeitpunkt von Flame existierte eine praktisch einsetzbare Chosen-Prefix-Methode, die der öffentlichen Forschung nicht bekannt war. Die veröffentlichten Angriffskosten sind also eine Obergrenze für das, was Angreifer können, nie eine Untergrenze. Wer seine Migrationsplanung an der jeweils letzten Konferenzveröffentlichung ausrichtet, plant systematisch zu spät.

Teil 4: SHA-1 – derselbe Film, in Zeitlupe

SHA-1 wurde 1995 standardisiert (FIPS 180-1), 160 Bit Ausgabe, Geburtstagsschranke 2⁸⁰. Die Geschichte seines Bruchs ist dieselbe wie bei MD5, nur über zwanzig Jahre gestreckt – was sie besonders gut dokumentiert.

2005 – die Theorie. Xiaoyun Wang, Yiqun Lisa Yin und Hongbo Yu veröffentlichten auf der CRYPTO 2005 Finding Collisions in the Full SHA-1 (LNCS 3621, S. 17–36, DOI 10.1007/11535218_2): ein Angriff mit weniger als 2⁶⁹ Hashoperationen, der erste unterhalb der 2⁸⁰-Schranke für das vollständige 80-Runden-SHA-1. Theoretisch gebrochen, praktisch unerreichbar. NIST sprach 2011 die Deprecation aus.

2015 – SHAppening. Stevens, Karpman und Peyrin zeigten eine Freestart-Kollision; die Git-Dokumentation beziffert diesen Angriff mit 2⁵⁷ Operationen. Keine Dateien, aber eine belastbare Hochrechnung – und die Erkenntnis, dass die Kosten eines echten Angriffs niedriger lagen als allgemein angenommen. Die Zertifikatsökosysteme zogen daraufhin ihre SHA-1-Ausstiegsfristen vor.

2017 – SHAttered. Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini und Yarik Markov präsentierten The first collision for full SHA-1 (CRYPTO 2017; ePrint 2017/190): zwei unterschiedlich aussehende PDF-Dateien mit identischem SHA-1-Wert. Aufwand: etwa 2⁶³·¹ Aufrufe der Kompressionsfunktion, entsprechend rund 6.500 CPU-Jahren und 100 GPU-Jahren – nach Angabe der Autoren mehr als 100.000-mal schneller als Brute Force. Es war eine Identical-Prefix-Kollision; die chosen-prefix-Variante fehlte noch.

2019 – die Brücke. Gaëtan Leurent und Thomas Peyrin zeigten auf der EUROCRYPT 2019 in From Collisions to Chosen-Prefix Collisions – Application to Full SHA-1, wie man von einer gewöhnlichen Kollision zu einer Chosen-Prefix-Kollision kommt: Aufwand zwischen 2⁶⁶·⁹ und 2⁶⁹·⁴ je nach Annahme über die Kosten der Near-Collision-Blöcke, gegenüber zuvor bestbekannten 2⁷⁷·¹. Die Autoren schlossen mit der Empfehlung, SHA-1 so schnell wie möglich aufzugeben.

2020 – Shambles. Dieselben Autoren implementierten den Angriff und veröffentlichten auf dem 29. USENIX Security Symposium SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust (S. 1839–1856). Gemessen in SHA-1-Äquivalenten auf einer Nvidia GTX 970 sanken die Kosten einer Identical-Prefix-Kollision von etwa 2⁶⁴·⁷ auf 2⁶¹·² und die einer Chosen-Prefix-Kollision von etwa 2⁶⁷·¹ auf 2⁶³·⁴. Bei gemieteter GPU-Kapazität entsprach das rund 11.000 US-Dollar für eine Kollision und rund 45.000 US-Dollar für eine Chosen-Prefix-Kollision. Der tatsächlich durchgeführte Angriff lief zwei Monate auf 900 Nvidia GTX 1060.

Die Anwendung traf das PGP-Vertrauensnetz. Die Autoren erzeugten zwei PGP-Schlüssel mit unterschiedlichen Identitäten, deren SHA-1-Zertifikate kollidierten: Eine Zertifizierung des ersten Schlüssels ließ sich auf den zweiten übertragen – eine funktionierende Identitätsfälschung innerhalb des Web of Trust. Der ältere GnuPG-Zweig verwendete für Identitätszertifizierungen noch standardmäßig SHA-1; nach der Meldung weist der moderne Zweig SHA-1-Signaturen zurück. Das Problem wurde als CVE-2019-14855 geführt.

Der Kostenverfall in einer Tabelle

Fünfzehn Jahre, in denen ein Angriff von "theoretisch denkbar" auf "Preis eines Mittelklassewagens" fiel. Und die Kurve wird nicht durch neue Mathematik dominiert, sondern zur Hälfte durch Hardware, die ohne jedes Zutun der Kryptanalyse billiger wird. Jede Hashfunktion, deren Kollisionssicherheit heute bei 64 Bit liegt, ist damit auf absehbare Zeit erledigt – unabhängig davon, ob jemand weiter daran forscht.

Teil 5: Warum "veraltet" nicht "entfernt" heißt

Zwischen der kryptographischen Bewertung und dem tatsächlichen Verschwinden eines Algorithmus liegen in der Praxis regelmäßig fünfzehn bis dreißig Jahre. Für MD5 lief die Uhr ab 1996 und läuft noch; für SHA-1 ab 2005, und NIST hat als Enddatum für den eigenen Gebrauch den 31. Dezember 2030 gesetzt (Ankündigung vom 15. Dezember 2022). Bis dahin soll FIPS 180-5 erscheinen, das die SHA-1-Spezifikation entfernt, SP 800-131A und weitere Publikationen sollen überarbeitet und eine Übergangsstrategie für die Validierungsprogramme CMVP und CAVP veröffentlicht werden.

Die Gründe für diese Zähigkeit sind strukturell, nicht nachlässig:

Hashwerte sind Identifikatoren, nicht nur Prüfsummen. In Git ist der SHA-1-Hash der Name eines Objekts. Ein Algorithmuswechsel ist dort kein Konfigurationsschalter, sondern eine Umbenennung der gesamten Geschichte. Dasselbe gilt für Deduplizierungsschlüssel in Speichersystemen, für Cache-Keys und für jede Datenbankspalte, in der ein Hash als Primärschlüssel steht.

Signaturen sind rückwärtsgerichtet. Ein Artefakt, das 2009 mit SHA-1 signiert wurde, kann man nicht nachträglich neu signieren, ohne den ursprünglichen Schlüssel zu haben. Verifizierer müssen alte Verfahren also unterstützen, auch wenn sie neue längst nicht mehr erzeugen – und jede solche Unterstützung ist ein potenzieller Downgrade-Pfad.

Die Kosten sind vollständig sichtbar, der Nutzen nicht. Eine Migration verursacht messbaren Aufwand und potenzielle Ausfälle. Der Nutzen besteht in Vorfällen, die nicht eintreten. Dieses Muster – sichtbare Kosten gegen unsichtbaren Nutzen – ist dasselbe, das bei der Post-Quanten-Migration wirkt, nur dort mit einem noch weiter entfernten Stichtag.

Counter-Cryptanalysis: die Gegenmaßnahme, die niemand merkt

Es gibt eine elegante Antwort für den Fall, dass man SHA-1 noch nicht entfernen kann. Marc Stevens und Dan Shumow beschrieben 2017 in Speeding up detection of SHA-1 collision attacks using unavoidable attack conditions (USENIX Security 2017; ePrint 2017/173), wie sich erkennen lässt, ob eine Nachricht aus einem Kollisionsangriff stammt. Grundlage sind "unvermeidbare Bedingungen": Eigenschaften, die jeder praktikable Angriff einer bestimmten Klasse erfüllen muss. Fehlt eine solche Bedingung, lässt sich die Nachricht sofort als unbedenklich einordnen.

Die Zahlen machen das Verfahren alltagstauglich: Die verbesserte Erkennung ist etwa 16-mal schneller als die Variante ohne unvermeidbare Bedingungen, und SHA-1 mit Kollisionserkennung ist im Durchschnitt nur noch etwa das 1,96-Fache von reinem SHA-1 – ein Faktor unter zwei für die Gewissheit, dass ein Objekt nicht aus einem Kollisionsangriff stammt. Die Implementierung sha1collisiondetection (sha1dc) wurde unter anderem von Git und von GitHub übernommen; genau deshalb konnten Git-Hoster die SHAttered-PDFs ablehnen, ohne ihre Objektnamen zu ändern.

Das ist konzeptionell bemerkenswert: Man repariert nicht die Hashfunktion, sondern man erkennt die Angriffe. Die Grenze dieses Ansatzes ist zugleich offensichtlich und wird im Paper benannt: Die Bedingungen gelten für bekannte Angriffsklassen, abgeleitet aus einer Konjektur über differenzielle Pfade. Flame hat gezeigt, dass Angreifer Klassen verwenden können, die noch nicht publiziert sind. Counter-Cryptanalysis kauft Zeit; sie ersetzt die Migration nicht.

Git: die Migration, die man live beobachten kann

Git ist der sichtbarste Fall. Die offizielle Dokumentation zu Breaking Changes benennt für Git 3.0 die Umstellung: "The default hash function for new repositories will be changed from 'sha1' to 'sha256'." Als Begründung werden die NIST-Deprecation von 2011 und ausdrücklich die vier Angriffe genannt – SHAppening (2⁵⁷), SHAttered (2⁶³), Birthday-Near-Collision 2019 (2⁶⁸ für Chosen-Prefix) und Shambles (2⁶³ für Chosen-Prefix).

Zwei Details dieser Ankündigung sind für die Praxis wichtiger als die Schlagzeile. Erstens ist dort kein Releasedatum genannt; das Projekt formuliert ausdrücklich, dass Voraussetzung die Bereitschaft des Ökosystems ist – Bibliotheken, Werkzeuge und Forges müssen das SHA-256-Objektformat unterstützen. Zweitens heißt es explizit: "There is no plan to deprecate the 'sha1' object format at this point in time." Die Begründung ist ebenfalls bemerkenswert ehrlich formuliert: Man habe Schutzmaßnahmen gegen bekannte Angriffe, erwarte aber weitere, und es sei "only a matter of time" bis SHA-1 vollständig als gebrochen gelte.

Das ist, nebenbei, ein gutes Modell für jede eigene Migration: Standard umstellen für Neues, Altes weiter lesen können, Erkennung für die Übergangszeit einbauen, und das Enddatum von der Reife des Umfelds abhängig machen statt von einem Wunschtermin.

Teil 6: Was man 2026 konkret tun kann

Die eine Frage, die jedes Inventar ordnet

Ein Hash-Inventar, das nur Algorithmen auflistet, ist fast wertlos, weil es jedes Vorkommen gleich behandelt. Nützlich wird es, wenn zu jedem Vorkommen drei Angaben stehen:

1. Welcher Algorithmus?
2. Darf ein Angreifer die gehashten Daten mitgestalten, bevor sie gehasht werden? (Das ist die Frage aus Teil 2 – sie entscheidet, ob eine Kollision überhaupt zu einem Angriff wird.)
3. Wird auf dem Hash eine Vertrauensentscheidung getroffen oder nur eine Übertragungsprüfung?

Erst diese Kombination ergibt eine Priorität. Ein MD5-Wert, der eine heruntergeladene Datei gegen eine Prüfsumme desselben Anbieters über denselben TLS-Kanal vergleicht, schützt gegen Übertragungsfehler und ist dafür ausreichend – er leistet nur nichts gegen einen Anbieter oder einen Spiegelserver, der beide Werte kontrolliert. Ein SHA-1-Wert in einem Signaturpfad für Software, Zertifikate oder Identitäten gehört dagegen in die oberste Dringlichkeitsstufe, weil dort alle drei Bedingungen zusammenkommen.

Entscheidungsmatrix nach Einsatzzweck

Die letzte Zeile ist wichtig, weil sie den häufigsten Kategorienfehler enthält: Für Passwörter ist nicht die Kollisionsresistenz das Thema, sondern die Rechenkosten pro Versuch. SHA-256 ist dort keine Verbesserung, sondern dasselbe Problem mit anderer Ausgabelänge.

Welche Nachfolger – und die Frage der Längenerweiterung

Für Neuentwürfe sind drei Optionen vertretbar, und die Wahl zwischen ihnen hat einen konkreten technischen Grund:

• SHA-256 / SHA-384 (SHA-2-Familie): breit implementiert, hardwarebeschleunigt auf praktisch jeder aktuellen CPU, 128 bzw. 192 Bit Kollisionssicherheit. Nachteil: Merkle–Damgård, also längenerweiterbar.
• SHA-512/256: die auf 256 Bit abgeschnittene SHA-512-Variante. Nicht längenerweiterbar, auf 64-Bit-Hardware ohne Hash-Beschleunigung oft schneller als SHA-256.
• SHA-3 / SHAKE (FIPS 202, 2015): Schwammkonstruktion, strukturell andere Bauart, nicht längenerweiterbar. In Software ohne Beschleunigung meist langsamer als SHA-2.

Ich würde SHA-256 als Standard nehmen und SHA-3 dort, wo eine strukturelle Diversifizierung gegenüber SHA-2 ausdrücklich gewollt ist. Es gibt gegen SHA-2 keine ernsthaften Kollisionsangriffe – die besten bekannten Ergebnisse betreffen reduzierte Rundenzahlen –, aber die Geschichte aus Teil 3 und 4 legt nahe, dass Algorithmus-Agilität selbst der eigentliche Schutz ist. Konkret heißt das: Hashwerte nie nackt speichern, sondern mit Algorithmuskennung (das Multihash-Muster sha256:…), und jede Verifikationsfunktion so schreiben, dass ein zweiter Algorithmus parallel unterstützt werden kann, ohne das Datenmodell zu ändern.

Was nicht funktioniert

Drei verbreitete Scheinlösungen sollte man kennen, weil sie regelmäßig als Workaround auftauchen:

Zwei Hashfunktionen aneinanderhängen. MD5(m) ‖ SHA1(m) ist nicht so stark, wie die Summe der Längen suggeriert. Antoine Joux zeigte 2004, dass Merkle–Damgård-Konstruktionen Multikollisionen erlauben, deren Erzeugung kaum teurer ist als die einer einzelnen Kollision – und dass sich daraus die Sicherheit einer Verkettung weitgehend auf die der stärkeren Einzelfunktion reduziert. Eine Verkettung ist deutlich teurer und kaum sicherer.

Mehr Iterationen. MD5(MD5(m)) beseitigt den Kollisionsangriff nicht: Kollidieren m₁ und m₂ schon im ersten Durchgang, kollidieren sie auch im zweiten.

Den Hash abschneiden oder verlängern, um "anders" zu sein. Eine Kollision der vollen Ausgabe ist auch eine Kollision jedes Präfixes der Ausgabe. Abschneiden reduziert die Sicherheit, es erhöht sie nie.

Teil 7: Das übergeordnete Denkprinzip

Der Bruch von MD5 und SHA-1 ist kein kryptographisches Spezialthema. Er ist das sauberste dokumentierte Beispiel für eine Klasse von Risiken, die in jeder Architektur vorkommt: Annahmen, deren Gültigkeit von einem Preis abhängt, der monoton fällt.

Eine Hashfunktion verspricht nie "unmöglich". Sie verspricht "zu teuer". Dieser Preis sinkt aus zwei unabhängigen Richtungen: durch Kryptanalyse, die sprunghaft und unvorhersehbar kommt, und durch Hardware, die stetig und vorhersehbar billiger wird. Der zweite Faktor allein erledigt jede 64-Bit-Sicherheitsmarge – ganz ohne neue Erkenntnisse. Wer eine Sicherheitsannahme trifft, trifft damit immer auch eine implizite Aussage über ein Verfallsdatum, und in den meisten Systemen ist dieses Datum nirgends aufgeschrieben.

Daraus folgt eine Entwurfshaltung, die über Hashfunktionen hinausreicht. Ein System soll nicht versuchen, den richtigen Algorithmus zu wählen – das ist auf zwanzig Jahre nicht möglich. Es soll so gebaut sein, dass der Wechsel des Algorithmus eine Routineoperation ist. Der eigentliche Fehler bei MD5 war nicht, es 1995 einzusetzen; damals war es Stand der Technik. Der Fehler war, es so einzusetzen, dass der Ausstieg zwanzig Jahre später eine Migration des Datenmodells erfordert.

Erkenntnis zum Mitnehmen

Die tragende Einsicht dieses Artikels ist nicht "MD5 und SHA-1 sind gebrochen", sondern: Eine Kollision wird erst dann zu einem Angriff, wenn der Angreifer Teile der Daten mitgestalten durfte, bevor sie gehasht wurden. Diese eine Frage – nicht der Algorithmusname – trennt das akute Problem vom technischen Schuldposten.

Daraus folgen vier Schritte, die man in jedem Projekt gehen kann. Erstens: Inventarisiere alle Stellen, an denen ein Hash eine Vertrauensentscheidung trägt – Signaturprüfung, Zertifikatskette, Artefaktfreigabe, Identitätszuordnung – und notiere zu jeder, ob ein Externer Eingabeteile beisteuert. Diese Liste, nicht die Algorithmusliste, ist die Prioritätenliste. Zweitens: Entferne MD5 und SHA-1 vollständig aus allen Signatur- und Zertifizierungspfaden; wo dort noch SHA-1 verifiziert werden muss, aktiviere Kollisionserkennung (sha1dc) und protokolliere jeden Treffer als Sicherheitsvorfall. Drittens: Speichere ab jetzt keinen Hashwert mehr ohne Algorithmuskennung und schreibe jede Verifikation so, dass sie zwei Algorithmen parallel akzeptieren kann – das ist der Schritt, der die nächste Migration von einem Projekt zu einem Konfigurationswechsel macht. Viertens: Prüfe, ob irgendwo eine Hashausgabe von 128 Bit oder weniger eine Kollisionsannahme trägt; 64 Bit Kollisionssicherheit sind keine Sicherheitsmarge mehr, sondern eine Frist.

Eine Frage zum Nachdenken

Die Rogue-CA-Demonstration von 2008 funktionierte nicht, weil MD5 schwach war. Sie funktionierte, weil MD5 schwach war und die Seriennummer sequenziell und der Zeitstempel sekundengenau vorhersagbar. Jedes dieser drei Details war in seiner jeweiligen Zuständigkeit als harmlos eingeordnet – und zwar vollkommen zu Recht, solange man es isoliert betrachtete. Der Angriff entstand in den Lücken zwischen drei korrekten Einzelbewertungen.

Die Frage, die daraus folgt, ist unbequemer, als sie klingt: In jeder Architektur gibt es Eigenschaften, die niemand als Sicherheitseigenschaft führt – vorhersagbare IDs, präzise Zeitstempel, deterministische Reihenfolgen, stabile Formatierung. Sie stehen in keinem Bedrohungsmodell, weil sie keinem einzelnen Komponentenverantwortlichen gehören. Wer in deinem System prüft eigentlich die Kombinationen, wenn jede einzelne Komponente korrekt bewertet wurde? Denn erfahrungsgemäß wird diese Prüfung nicht in einem Review durchgeführt. Sie wird von einem Angreifer durchgeführt, der als Erster alle drei Teile gleichzeitig ansieht.

Querverweise im Vault

• Der Baum, der die Wahrheit verdichtet: Merkle-Bäume und die Kunst der effizienten Integritätsprüfung – die Konstruktion, die auf genau der hier diskutierten Annahme ruht: ein Merkle-Baum ist nur so stark wie die Kollisionsresistenz seiner Hashfunktion.
• Das Ende des Passworts: Passkeys, WebAuthn und die Anatomie phishing-resistenter Anmeldung – die Signatur über Challenge und Origin setzt eine kollisionsresistente Hashfunktion voraus; das Beispiel für Algorithmus-Agilität im Datenmodell.
• Der Schlüssel, der nach jeder Nachricht stirbt: Das Signal-Protokoll, die Double Ratchet und die Kunst der Ende-zu-Ende-Verschlüsselung – HKDF und HMAC als korrekte Verwendung von Hashfunktionen, im Gegensatz zum naiven H(key ‖ msg).
• Ernte jetzt, entschlüssle später: Post-Quanten-Kryptographie und das Rennen gegen den Quantencomputer – dasselbe Migrationsmuster mit entfernterem Stichtag: sichtbare Kosten, unsichtbarer Nutzen, und Agilität als eigentliche Antwort.
• Die Hintertür im Herzen von Linux: Der XZ-Backdoor und die Anatomie eines Supply-Chain-Angriffs – der Angriff, der die Vertrauenskette verändert, statt die Kryptographie zu brechen; die zweite Hälfte desselben Bedrohungsbilds.
• Beweisen ohne zu verraten: Zero-Knowledge-Beweise von Ali Babas Höhle bis zu zk-SNARKs – Beweissysteme, deren Soundness in der Praxis ebenfalls auf Kollisionsresistenz im Fiat-Shamir-Schritt ruht.
• Wenn der Prozessor zu viel rät: Spectre, Meltdown und die Sünde der spekulativen Ausführung – dieselbe Lektion eine Abstraktionsebene tiefer: eine Annahme, die gilt, bis jemand den Preis ihres Bruchs neu berechnet.

Quellen

• Wang, X., Yu, H. (2005): How to Break MD5 and Other Hash Functions. In: Cramer, R. (Hrsg.), Advances in Cryptology – EUROCRYPT 2005, LNCS 3494, Springer, S. 19–35. DOI: 10.1007/11426639_2. https://link.springer.com/chapter/10.1007/11426639_2
• Wang, X., Yin, Y. L., Yu, H. (2005): Finding Collisions in the Full SHA-1. In: Shoup, V. (Hrsg.), Advances in Cryptology – CRYPTO 2005, LNCS 3621, Springer, S. 17–36. DOI: 10.1007/11535218_2. https://link.springer.com/chapter/10.1007/11535218_2
• Sotirov, A., Stevens, M., Appelbaum, J., Lenstra, A., Molnar, D., Osvik, D. A., de Weger, B. (2008/2009): MD5 considered harmful today – Creating a rogue CA certificate. Präsentiert am 30. Dezember 2008 auf dem 25. Chaos Communication Congress, Berlin; wissenschaftliche Ausarbeitung mit Best-Paper-Award auf der CRYPTO 2009. https://marc-stevens.nl/research/hashclash/rogue-ca/
• Stevens, M., Bursztein, E., Karpman, P., Albertini, A., Markov, Y. (2017): The first collision for full SHA-1. CRYPTO 2017; Cryptology ePrint Archive, Paper 2017/190. https://eprint.iacr.org/2017/190
• Stevens, M., Shumow, D. (2017): Speeding up detection of SHA-1 collision attacks using unavoidable attack conditions. 26th USENIX Security Symposium; Cryptology ePrint Archive, Paper 2017/173. https://eprint.iacr.org/2017/173
• Leurent, G., Peyrin, T. (2019): From Collisions to Chosen-Prefix Collisions – Application to Full SHA-1. EUROCRYPT 2019; Cryptology ePrint Archive, Paper 2019/459. https://eprint.iacr.org/2019/459
• Leurent, G., Peyrin, T. (2020): SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust. 29th USENIX Security Symposium (USENIX Security 20), S. 1839–1856. https://www.usenix.org/conference/usenixsecurity20/presentation/leurent
• Fillinger, M. J. (2013): Reconstructing the Cryptanalytic Attack behind the Flame Malware. Master of Logic Thesis MoL-2013-23, ILLC, Universiteit van Amsterdam / CWI; Betreuer: M. Stevens, C. Schaffner. https://eprints.illc.uva.nl/912
• National Institute of Standards and Technology (2022): NIST Transitioning Away from SHA-1 for All Applications. CSRC News, 15. Dezember 2022. https://csrc.nist.gov/News/2022/nist-transitioning-away-from-sha-1-for-all-apps
• Git-Projekt: Git – BreakingChanges Documentation. Abschnitt zu Git 3.0 und der Umstellung der Standard-Hashfunktion auf SHA-256. https://git-scm.com/docs/BreakingChanges

← All articles