Was ist eine Hash Collision?
Eine Hash Collision oder Hash-Kollision entsteht, wenn zwei unterschiedliche Eingaben denselben Hashwert erzeugen.
Vereinfacht:
Eingabe A ──┐
├── Hashfunktion ──→ gleicher Hashwert
Eingabe B ──┘
obwohl gilt:
Eingabe A ≠ Eingabe B
Auf den ersten Blick klingt das nach einem Fehler. Schließlich erwartet man von einer kryptografischen Hashfunktion wie SHA-256, dass unterschiedliche Daten auch unterschiedliche Hashwerte erzeugen.
Tatsächlich sind Kollisionen aber mathematisch unvermeidbar.
Die entscheidende Frage ist deshalb nicht, ob Kollisionen existieren, sondern:
Wie schwierig ist es, eine Kollision zu finden?
Genau hier liegt eine der wichtigsten Sicherheitseigenschaften kryptografischer Hashfunktionen.
Was eine Hashfunktion grundsätzlich macht, erkläre ich im Artikel Was ist eine Hashfunktion?. Wenn du das noch nicht getan hast, lohnt sich ein Blick dorthin, bevor du hier weiterliest.
Warum müssen Hash Collisions existieren?
Eine Hashfunktion kann Eingaben sehr unterschiedlicher Länge verarbeiten.
SHA-256 erzeugt daraus jedoch immer einen Hashwert mit genau 256 Bit.
Damit gibt es für SHA-256 genau
2²⁵⁶
mögliche Hashwerte.
Das ist eine gewaltige Zahl – ungefähr:
1,16 × 10⁷⁷
Trotzdem ist die Anzahl möglicher SHA-256-Hashwerte endlich.
Betrachten wir beispielsweise alle möglichen Eingaben mit genau 257 Bit Länge. Davon gibt es:
2²⁵⁷
Es gibt damit bereits mehr unterschiedliche 257-Bit-Eingaben als mögliche SHA-256-Hashwerte.
Damit können unmöglich alle diese Eingaben einen eigenen Hashwert erhalten. Mindestens zwei unterschiedliche Eingaben müssen denselben Hashwert besitzen.
Dieses Prinzip lässt sich mit dem Schubfachprinzip erklären.
Stell dir vor, du hast mehr Gegenstände als Schubladen. Wenn jeder Gegenstand in eine Schublade gelegt werden muss, muss mindestens eine Schublade mehr als einen Gegenstand enthalten.
Bei einer Hashfunktion entsprechen:
- die Eingaben den Gegenständen,
- die möglichen Hashwerte den Schubladen.
Kollisionen sind daher kein ungewöhnlicher Sonderfall, sondern eine mathematische Konsequenz der festen Ausgabelänge einer Hashfunktion.
Bedeutet das, dass SHA-256 unsicher ist?
Nein.
Dass Kollisionen existieren, sagt zunächst noch nichts darüber aus, ob eine Hashfunktion sicher ist.
Für eine kryptografische Hashfunktion ist entscheidend, dass es praktisch nicht möglich sein soll, gezielt zwei unterschiedliche Eingaben mit demselben Hashwert zu finden.
Diese Eigenschaft nennt man Collision Resistance.
Vereinfacht:
Finde A und B mit
A ≠ B
aber
Hash(A) = Hash(B)
Bei einer kollisionsresistenten Hashfunktion soll diese Aufgabe mit realistisch verfügbaren Rechenressourcen nicht praktikabel lösbar sein.
256 Bit bedeutet nicht 256 Bit Collision Security
SHA-256 besitzt einen Hashwert mit 256 Bit.
Man könnte deshalb zunächst vermuten, dass ungefähr
2²⁵⁶
Versuche erforderlich wären, um eine Kollision zu finden.
Bei einer idealen Hashfunktion ist der generische Aufwand für die Kollisionssuche jedoch wesentlich geringer.
Für eine Hashfunktion mit einer Ausgabelänge von n Bit liegt der relevante Größenbereich aufgrund des sogenannten Birthday Bounds ungefähr bei:
2^(n/2)
Für SHA-256 ergibt sich:
2^(256/2)
= 2^128
SHA-256 wird deshalb laut NIST mit einer Collision-Resistance-Stärke von 128 Bit eingeordnet.
Zum Vergleich:
| Eigenschaft | SHA-256 |
|---|---|
| Hashlänge | 256 Bit |
| generische Preimage-Sicherheit | ungefähr 256 Bit |
| generische Collision-Sicherheit | ungefähr 128 Bit |
Warum sich der Aufwand für Kollisionen so stark von der Preimage-Suche unterscheidet, lässt sich mit dem Geburtstagsproblem erklären.
Was hat eine Hash Collision mit Geburtstagen zu tun?
Das sogenannte Geburtstagsproblem liefert ein überraschendes Ergebnis.
Befinden sich 23 zufällig ausgewählte Personen in einem Raum, liegt die Wahrscheinlichkeit bereits bei rund 50,7 %, dass mindestens zwei von ihnen am selben Kalendertag Geburtstag haben – wenn wir beispielsweise Schaltjahre ignorieren und gleichverteilte Geburtstage annehmen.
Das wirkt zunächst überraschend.
Der Grund ist, dass wir nicht fragen:
Wer hat denselben Geburtstag wie eine bestimmte Person?
Sondern:
Gibt es irgendein Paar von Personen mit demselben Geburtstag?
Mit jeder zusätzlichen Person steigt die Anzahl möglicher Paare stark an.
Ein ähnlicher Effekt tritt bei Hashwerten auf.
Bei einem Kollisionsangriff suchen wir nicht nach einer Eingabe für einen bestimmten vorgegebenen Hashwert.
Wir suchen zwei beliebige unterschiedliche Eingaben, deren Hashwerte identisch sind.
Deshalb wird eine Kollision statistisch wesentlich früher wahrscheinlich, als man beim bloßen Betrachten der Anzahl möglicher Hashwerte zunächst vermuten könnte.
Für einen idealen n-Bit-Hash liegt der relevante Größenbereich ungefähr bei:
2^(n/2)
Dieser Zusammenhang wird häufig als Birthday Bound bezeichnet.
Die Wahrscheinlichkeitsrechnung dahinter erkläre ich ausführlich im Artikel Das Birthday Paradox. Wie sich der Effekt gezielt für eine Kollisionssuche nutzen lässt, zeige ich im Artikel Wie funktioniert ein Birthday Attack?.
Collision ist nicht gleich Preimage
An dieser Stelle ist eine Unterscheidung besonders wichtig.
Es gibt verschiedene kryptografische Aufgaben, die auf den ersten Blick ähnlich aussehen.
Collision
Gesucht werden irgendwelche zwei unterschiedlichen Eingaben mit demselben Hash:
Finde A und B:
A ≠ B
Hash(A) = Hash(B)
Preimage
Hier ist bereits ein bestimmter Hashwert H gegeben.
Gesucht wird eine Eingabe A mit:
Hash(A) = H
Das ist eine andere Aufgabe.
Bei einer idealen 256-Bit-Hashfunktion liegt der generische Aufwand für eine Preimage-Suche ungefähr bei:
2²⁵⁶
während der relevante Größenbereich für eine Kollisionssuche aufgrund des Birthday Bounds ungefähr bei:
2¹²⁸
liegt.
Deshalb sollte man Collision Resistance und Preimage Resistance nicht miteinander verwechseln.
Was Preimage Resistance genau bedeutet und warum SHA-256 dabei eine Sicherheitsstärke von 256 Bit zugeordnet wird, erkläre ich im Artikel Was ist Preimage Resistance?.
Was ist Second-Preimage Resistance?
Es gibt noch eine dritte verwandte Eigenschaft.
Dabei ist eine bestimmte Eingabe A bereits bekannt.
Gesucht wird eine andere Eingabe B, für die gilt:
A ≠ B
und
Hash(A) = Hash(B)
Das nennt man Second-Preimage Resistance.
Auch das unterscheidet sich von einem normalen Kollisionsangriff.
Bei einer Collision dürfen beide Eingaben frei gewählt werden.
Bei einem Second-Preimage-Angriff ist eine der beiden Eingaben bereits vorgegeben.
Diese Unterscheidung ist wichtig, weil es sich um unterschiedliche kryptografische Problemstellungen handelt.
Sind bereits echte Hash Collisions gefunden worden?
Ja.
Bei älteren kryptografischen Hashfunktionen konnten praktische Kollisionsangriffe entwickelt werden.
Ein bekanntes Beispiel ist MD5.
Für MD5 wurden praktische Verfahren entwickelt, mit denen gezielt unterschiedliche Daten mit demselben MD5-Hash erzeugt werden können. Deshalb ist MD5 für Anwendungen, die Collision Resistance benötigen, laut RFC 6151 nicht mehr geeignet.
Auch SHA-1 gilt heute nicht mehr als geeignete kryptografische Hashfunktion für neue Anwendungen. NIST empfiehlt, SHA-1 durch SHA-2 oder SHA-3 zu ersetzen.
2017 demonstrierten Marc Stevens und weitere Forscher mit der als SHAttered bekannt gewordenen Arbeit eine praktische Kollision für die vollständige SHA-1-Hashfunktion.
Dabei wurden zwei unterschiedliche PDF-Dateien erzeugt, die denselben SHA-1-Hashwert besitzen.
Das zeigt einen wichtigen Unterschied:
Kollisionen existieren mathematisch.
ist etwas völlig anderes als:
Kollisionen können praktisch gezielt erzeugt werden.
Der zweite Fall ist für eine kryptografische Hashfunktion ein ernstes Sicherheitsproblem.
Warum können Collisions gefährlich sein?
Besonders problematisch können Kollisionen werden, wenn ein Angreifer zwei unterschiedliche Dokumente gezielt so konstruieren kann, dass beide denselben Hashwert besitzen.
Wird anschließend eines dieser Dokumente signiert oder anderweitig anhand seines Hashwerts verarbeitet, könnte unter bestimmten Voraussetzungen das kollidierende zweite Dokument missbräuchlich verwendet werden.
Entscheidend ist dabei:
Bei einem normalen Kollisionsangriff kann der Angreifer beide kollidierenden Eingaben beeinflussen.
Die Aufgabe, zu einem bereits fest vorgegebenen Dokument nachträglich ein anderes Dokument mit demselben Hashwert zu finden, ist dagegen eine andere kryptografische Problemstellung – ein Second-Preimage-Angriff.
Diese Unterscheidung ist wichtig, wenn man die praktischen Auswirkungen von Hash-Kollisionen bewertet.
Wie sicher ist SHA-256 gegen Collisions?
SHA-256 wird von NIST mit einer Collision-Resistance-Stärke von 128 Bit geführt.
Für einen idealen 256-Bit-Hash liegt der generische Aufwand für die Kollisionssuche entsprechend im Größenbereich von:
2¹²⁸
Operationen.
Das liegt weit außerhalb dessen, was mit heutiger klassischer Rechentechnik praktisch durchführbar ist.
Das bedeutet allerdings nicht:
Eine SHA-256-Kollision existiert nicht.
Wir wissen mathematisch, dass Kollisionen existieren müssen.
Die Sicherheit beruht vielmehr darauf, dass es praktisch nicht möglich sein soll, eine solche Kollision gezielt zu finden.
Genau dieser Unterschied ist zentral für das Verständnis kryptografischer Hashfunktionen.
Was bedeutet Collision Resistance?
Eine kryptografische Hashfunktion gilt als kollisionsresistent, wenn es praktisch nicht möglich ist, zwei unterschiedliche Eingaben zu finden, die denselben Hashwert erzeugen.
Gesucht wären:
A ≠ B
mit:
Hash(A) = Hash(B)
Collision Resistance bedeutet also nicht, dass solche Paare nicht existieren.
Sie bedeutet, dass sie mit realistisch verfügbaren Ressourcen nicht praktikabel gefunden werden können.
Das Wichtigste in Kürze
Eine Hash Collision entsteht, wenn zwei unterschiedliche Eingaben denselben Hashwert erzeugen.
Die wichtigsten Punkte:
- Kollisionen sind bei Hashfunktionen mit fester Ausgabelänge mathematisch unvermeidbar.
- Das Vorhandensein von Kollisionen macht eine Hashfunktion nicht automatisch unsicher.
- Entscheidend ist, wie schwierig es ist, eine Kollision gezielt zu finden.
- Diese Sicherheitseigenschaft nennt man Collision Resistance.
- Bei einem idealen
n-Bit-Hash liegt der relevante Größenbereich für eine generische Kollisionssuche ungefähr bei2^(n/2). - SHA-256 wird mit 128 Bit Collision Resistance eingeordnet.
- Collision Resistance ist nicht dasselbe wie Preimage Resistance oder Second-Preimage Resistance.
- MD5 ist für Anwendungen, die Collision Resistance benötigen, nicht mehr geeignet.
- SHA-1 soll durch SHA-2 oder SHA-3 ersetzt werden.
Die Tatsache, dass Kollisionen unvermeidbar sind, ist also kein Widerspruch zur Sicherheit kryptografischer Hashfunktionen.
Die eigentliche Sicherheitsfrage lautet nicht:
Gibt es eine Kollision?
Sondern:
Können wir eine finden?
Wie geht es weiter?
Wenn du verstanden hast, warum Hash Collisions existieren, sind die nächsten interessanten Themen:
- Das Birthday Paradox
- Wie funktioniert ein Birthday Attack?
- Was ist Collision Resistance?
- Was ist Preimage Resistance?
- Was ist Second-Preimage Resistance?
- Warum ist MD5 unsicher?
- Wie wurde SHA-1 praktisch gebrochen?
- Warum gilt SHA-256 weiterhin als sicher?
Quellen und weiterführende Standards
Die folgenden Primär- und Normquellen bilden die Grundlage für die technischen Aussagen dieses Artikels:
-
National Institute of Standards and Technology (NIST), Hash Functions Hauptquelle für Sicherheitseigenschaften von Hashfunktionen und die Collision-Resistance-Stärke von SHA-256.
-
National Institute of Standards and Technology (NIST), NIST Policy on Hash Functions Aktueller NIST-Status zu SHA-1, SHA-2 und SHA-3.
-
National Institute of Standards and Technology (NIST), FIPS 180-4 – Secure Hash Standard (SHS) Spezifikation der SHA-1- und SHA-2-Hashalgorithmen, darunter SHA-256.
-
IETF, RFC 6151 – Updated Security Considerations for the MD5 Message-Digest and the HMAC-MD5 Algorithms Sicherheitsbewertung von MD5 und insbesondere der bekannten Kollisionsprobleme.
-
IETF, RFC 6194 – Security Considerations for the SHA-0 and SHA-1 Message-Digest Algorithms Sicherheitsbetrachtungen und bekannte Schwächen von SHA-1.
-
Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov, The First Collision for Full SHA-1, CRYPTO 2017. Praktische Kollision für die vollständige SHA-1-Hashfunktion, bekannt als „SHAttered".