Warum sind Kollisionen mathematisch zwangsläufig?

Wegen des Pigeon-Hole-Prinzips. Eine Hash-Funktion bildet unendlich viele mögliche Eingaben auf eine endliche Anzahl von Ausgaben ab. SHA-256 hat 2^256 mögliche Ausgaben, aber eine Eingabe kann beliebig lang sein, es gibt also weitaus mehr Eingaben als Ausgaben. Deshalb müssen mehrere Eingaben denselben Hash teilen. Was zählt, ist die rechnerische Schwierigkeit, eine solche Kollision zu finden. SHA-256 ist so konstruiert, dass diese Suche praktisch unmöglich ist.

Was sagt das Geburtstagsparadox über Hash-Kollisionen?

Bei n möglichen Hash-Werten findet man mit hoher Wahrscheinlichkeit eine zufällige Kollision nach etwa sqrt(n) Versuchen. Für einen 256-Bit-Hash sind das 2^128 Versuche. Für 128-Bit-MD5 wären es 2^64 Versuche, was 1992 noch unerreichbar war, heute aber in Spezialfällen machbar wird. Die Faustregel: Ein n-Bit-Hash bietet effektiv n/2 Bit Kollisions-Sicherheit. Wer 128 Bit echte Sicherheit will, braucht einen mindestens 256-Bit-Hash. Deshalb ist SHA-256 der Standard.

Was ist eine Chosen-Prefix-Kollision und warum ist sie schlimmer?

Bei einer Identical-Prefix-Kollision konstruiert der Angreifer zwei Nachrichten mit identischem Anfang und konstruierten Differenz-Suffixen. Das ist akademisch interessant, aber begrenzt nützlich. Bei einer Chosen-Prefix-Kollision wählt der Angreifer zwei verschiedene Präfixe (etwa zwei verschiedene Zertifikats-Header) und konstruiert dann Suffixe, sodass beide Gesamt-Dateien denselben Hash haben. Das ermöglicht praktische Angriffe auf reale Strukturen wie X.509-Zertifikate oder Code-Signing-Zertifikate.

Sind Passwort-Hashes durch Kollisionen gefährdet?

Bei gesalteten Passwort-Hashes sind Kollisionen nicht das Hauptproblem. Eine Kollision zwischen zwei Passwörtern eines Nutzers existiert immer, aber der Angreifer kennt die Hashes nicht im Voraus, sondern muss bruteforcen. Das eigentliche Problem ist die Bruteforce-Geschwindigkeit: Eine moderne GPU rechnet Milliarden SHA-256 pro Sekunde. Deshalb sind spezielle Passwort-Funktionen (bcrypt, scrypt, Argon2) Pflicht, die absichtlich langsam sind und Memory verbrauchen, nicht einfache Hashes.

Wie nah sind wir an SHA-256-Kollisionen?

Praktisch nicht in der Nähe. SHA-256 hat 256 Bit Output, also 2^128 Birthday-Bound für Kollisionen. Selbst alle Computer der Welt zusammen brauchen dafür viele Milliarden Jahre. Grovers Quantenalgorithmus halbiert das nur (gibt 2^85 Operationen für Kollisionen, immer noch unerreichbar). Reine Brute-Force ist also keine Bedrohung. Was zählt sind strukturelle Schwächen im Algorithmus, und die wurden bei SHA-256 trotz intensiver 20-jähriger Kryptanalyse nicht gefunden.

Hash-Kollisionen: wie schlimm sie wirklich sind

Drei Begriffe, drei Schweregrade

Wer “Hash-Kollision” sagt, meint je nach Kontext drei sehr unterschiedliche Dinge. Die Unterscheidung entscheidet darüber, ob ein Algorithmus für eine konkrete Anwendung noch tragbar ist oder nicht.

Zufällige Kollision (Random Collision): Zwei beliebige verschiedene Eingaben haben zufällig denselben Hash. Der Aufwand ist 2^(n/2) Hashings nach dem Geburtstagsparadox, wobei n die Output-Länge in Bit ist. Für SHA-256 sind das 2^128, für MD5 nur 2^64. Random Collisions sind die schwächste Form, weil der Angreifer die Inputs nicht kontrolliert.

Identical-Prefix-Kollision: Zwei Inputs beginnen mit denselben gewählten Bytes und unterscheiden sich nur in konstruierten Differenz-Blöcken. Das ist eine gerichtete Kollision, in der der Angreifer einen Teil der Inhalte vorgibt. Wang Xiaoyuns MD5-Kollision 2004 war von diesem Typ.

Chosen-Prefix-Kollision: Zwei Inputs beginnen mit zwei beliebigen, verschiedenen Präfixen, und der Angreifer konstruiert passende Suffixe, sodass die kompletten Inputs denselben Hash haben. Das ist die gefährlichste Form, weil sie sich gegen reale Strukturen wie Zertifikate richten lässt. Der Flame-Angriff 2012 und der SHAttered-Angriff 2017 waren Chosen-Prefix.

Preimage-Angriff: Gegeben ein Hash-Wert, finde irgendeinen Input, der diesen Hash erzeugt. Aufwand für SHA-256 wäre 2^256 Operationen. Für keine etablierte kryptografische Hash-Funktion ist je ein praktischer Preimage-Angriff demonstriert worden. Wenn das gelänge, wäre die Funktion vollständig zerstört.

Das Pigeon-Hole-Prinzip in einem Satz

Eine kryptografische Hash-Funktion bildet eine unendliche Eingabemenge auf eine endliche Ausgabemenge ab. SHA-256 hat 2^256 mögliche Ausgaben, etwa 10^77, mehr als Atome im beobachtbaren Universum. Aber Eingaben sind beliebig lang. Wenn Sie alle 2^257 möglichen Inputs von Länge 257 Bit ausprobieren, müssen mindestens zwei denselben SHA-256-Hash haben.

Kollisionen existieren also mathematisch, sie sind unvermeidbar. Die kryptografische Frage ist nur: Wie schwer ist es, eine zu konstruieren? Eine Funktion gilt als “kollisions-resistent”, wenn sich keine effizientere Methode finden lässt als blindes Probieren bis zur Geburtstagsgrenze.

Für SHA-256 bedeutet das: Auch nach 2^128 zufälligen Probier-Versuchen ist die Wahrscheinlichkeit, eine Kollision zu treffen, nur etwa 50 Prozent. Und 2^128 Operationen entsprechen, mit jeder denkbaren Hardware-Annahme, vielen Milliarden Jahren Rechenzeit. Selbst alle Bitcoin-Miner der Welt zusammen, die derzeit etwa 2^88 SHA-256-Operationen pro Jahr schaffen, bräuchten 2^40 Jahre, das sind etwa eine Billion Jahre.

Das Geburtstagsparadox: warum n/2 statt n

Das Geburtstagsparadox erklärt, warum der Aufwand für eine Kollision nur sqrt(2^n) ist, nicht 2^n. In einer Gruppe von 23 Personen ist die Wahrscheinlichkeit, dass zwei am selben Tag Geburtstag haben, schon über 50 Prozent. Intuitiv überraschend, mathematisch sauber: Bei 23 Personen gibt es C(23,2) = 253 Paare, von denen jedes mit Wahrscheinlichkeit 1/365 einen Geburtstags-Match hat.

Übertragen auf Hashes: Bei einem n-Bit-Hash gibt es 2^n mögliche Werte. Wenn Sie sqrt(2^n) = 2^(n/2) zufällige Inputs hashen, ist die Wahrscheinlichkeit, dass irgendwo eine Kollision auftritt, bei etwa 50 Prozent. Für SHA-256 (n=256) sind das 2^128 Inputs. Für SHA-1 (n=160) sind es 2^80, was 2017 die SHAttered-Forscher in Reichweite gebracht hat.

Praktische Konsequenz: Wer 128 Bit Sicherheit gegen Kollisionen will, braucht einen mindestens 256-Bit-Hash. NIST SP 800-107 macht das explizit: “Wenn die Anwendung eine Kollisionsresistenz von s Bit erfordert, sollte die Hash-Funktion eine Output-Länge von mindestens 2s Bit haben.”

Drei Kollisions-Typen mit aufsteigender Gefährlichkeit. Random ist akademisch, Chosen-Prefix ist Praxis-Bedrohung.

SHAttered: SHA-1 fällt 2017 praktisch

Im Februar 2017 veröffentlichten Marc Stevens (CWI Amsterdam), Elie Bursztein (Google), Pierre Karpman, Ange Albertini und Yarik Markov die erste praktische SHA-1-Kollision. Das Projekt hieß SHAttered und produzierte zwei verschiedene PDF-Dateien mit identischem SHA-1-Hash.

Der rechnerische Aufwand: rund 9.000.000.000.000.000.000 SHA-1-Operationen, was Google auf einem internen GPU-Cluster in etwa 110 GPU-Jahren bewältigte. Ein einzelner Angreifer auf AWS hätte damals etwa 110.000 USD bezahlt für dieselbe Kollision. Heute (2026) liegt der Preis bei unter 30.000 USD.

Die Bedeutung: SHA-1 war damit für sicherheitskritische Anwendungen endgültig untragbar. Git, das SHA-1 als Object-ID verwendet, musste eine Hardening-Schicht einführen (SHA-1 Collision Detection von Marc Stevens, jetzt Default in Git). Zertifikate mit SHA-1-Signatur wurden von Browsern komplett abgewiesen, was bereits 2017 in Chrome und Firefox vollzogen war. TLS-Verbindungen mit SHA-1-Hashes in der Kette werden seit 2017 als unsicher markiert.

Drei Jahre später (USENIX Security 2020) zeigten Gaëtan Leurent und Thomas Peyrin mit “SHA-1 is a Shambles” eine Chosen-Prefix-Kollision in SHA-1 für etwa 45.000 USD Cloud-Kosten. Damit war SHA-1 nicht mehr nur theoretisch tot, sondern praktisch angreifbar in Kontexten, die Chosen-Prefix erlauben (Zertifikate, GPG-Schlüssel, Code-Signaturen).

Passwort-Hashes: Kollisionen sind nicht das Hauptproblem

Bei gesalteten Passwort-Hashes ist die Kollisionsanfälligkeit zweitrangig. Wenn ein Nutzer das Passwort “geheim” hat und gehashed wird zu 5ebe2294ecd0e0f08eab7690d2a6ee69 (MD5), ist eine theoretische Kollision (ein anderes Passwort mit demselben Hash) für einen Angreifer wenig hilfreich. Er kennt den Hash zunächst gar nicht, denn er steht in der Datenbank, die er erst erbeuten müsste.

Das eigentliche Passwort-Problem ist Bruteforce-Geschwindigkeit. Eine moderne GPU rechnet etwa 10 Milliarden MD5 pro Sekunde, etwa 1 Milliarde SHA-256 pro Sekunde. Bei einem 8-stelligen Passwort mit Buchstaben+Zahlen (62^8 = 218 Billionen Möglichkeiten) ist der komplette Suchraum in einigen Stunden durchprobiert.

Deshalb sind für Passwörter spezielle Hash-Konstruktionen Pflicht, die absichtlich langsam sind: bcrypt, scrypt, Argon2. Argon2id mit OWASP-Empfehlung (19 MiB Memory, t=2, p=1) braucht pro Hashing einige hundert Millisekunden auf einer Standard-CPU. Eine GPU bringt hier keinen Vorteil, weil die Memory-Hardness GPU-parallelisierung ausbremst.

Kollisionen bei Passwort-Hashes haben also einen anderen Stellenwert: Sie sind theoretisch existent, praktisch aber nicht der Angriffsvektor. Der Angriffsvektor ist die Geschwindigkeit der Hash-Funktion, nicht ihre Kollisionsanfälligkeit.

SHA-256 ist nicht in Kollisions-Reichweite

Trotz 20 Jahren intensiver Kryptanalyse hat niemand eine Schwäche in SHA-256 gefunden, die unter der Birthday-Grenze von 2^128 Operationen liegt. Die besten bekannten Angriffe auf reduzierte SHA-256-Varianten erreichen 31 von 64 Runden (Mendel et al. 2013), volle SHA-256 bleibt unberührt.

Quantencomputer ändern das Bild nur marginal. Grovers Algorithmus halbiert effektiv die Output-Länge gegen Preimage-Angriffe und reduziert Kollisionen auf 2^(n/3) (Brassard, Høyer, Tapp 1997). Für SHA-256 wären das 2^85 Operationen, was selbst mit projizierten Quantencomputern nicht in Reichweite ist. NIST hält SHA-256 deshalb auch im Post-Quanten-Kontext für ausreichend, wenn man mindestens 256-Bit-Output verwendet.

Praktisch bedeutet das: Wer heute eine Anwendung mit SHA-256 oder SHA-3 baut, hat keinen absehbaren Kollisions-Druck. Sorgenkinder sind nur MD5 (tot seit 2004) und SHA-1 (tot seit 2017). Wer Hash-Werte auf hash-generieren.de berechnet, sollte SHA-256 oder SHA-512 als Default wählen, MD5 und SHA-1 nur zur Verifikation alter Werte aus Legacy-Systemen. Die Methodik-Seite und die Autorenseite Jan-Tristan dokumentieren den Hintergrund.

Was hängenbleibt

Kollisionen sind mathematisch garantiert, aber praktisch sehr unterschiedlich gefährlich. Random Collision ist akademisch, Identical Prefix mittelgefährlich, Chosen Prefix der Praxis-Angriff. MD5 fällt seit 2004, SHA-1 seit 2017 unter den Chosen-Prefix-Hammer. SHA-256 bleibt unauffällig, mit 2^128 Birthday-Bound außerhalb aller realistischen Rechenleistungen. Für Passwörter zählen nicht Kollisionen, sondern Bruteforce-Geschwindigkeit, weshalb bcrypt, scrypt und Argon2 die richtige Wahl sind, nicht reines SHA-256.