Was ist Collision Resistance?
Eine der wichtigsten Sicherheitseigenschaften kryptografischer Hashfunktionen ist die sogenannte Collision Resistance.
Dabei geht es um folgende Aufgabe:
Kann ich zwei unterschiedliche Eingaben finden, die denselben Hashwert erzeugen?
Vereinfacht:
gesucht:
x und y
mit:
x ≠ y
und
Hash(x) = Hash(y)
Bei einer kollisionsresistenten Hashfunktion soll es praktisch nicht möglich sein, ein solches Paar gezielt zu finden.
Diese Eigenschaft wird als Collision Resistance bezeichnet.
Collision Resistance bedeutet nicht, dass keine Kollisionen existieren
Das ist der wichtigste Punkt zuerst.
Collision Resistance bedeutet nicht, dass eine Hashfunktion keine Kollisionen besitzt.
Bei einer Hashfunktion mit fester Ausgabelänge sind Kollisionen mathematisch unvermeidbar.
SHA-256 erzeugt beispielsweise einen Hashwert mit 256 Bit.
Damit existieren:
2²⁵⁶
mögliche SHA-256-Hashwerte.
Der mögliche Eingaberaum ist dagegen größer.
Deshalb müssen unterschiedliche Eingaben existieren, die auf denselben Hashwert abgebildet werden.
Collision Resistance stellt deshalb nicht die Frage:
Existieren Kollisionen?
Sondern:
Können wir mit praktikablem Aufwand eine Kollision finden?
Warum Kollisionen mathematisch unvermeidbar sind, erkläre ich ausführlich im Artikel Was ist eine Hash Collision?.
Wie sieht ein Kollisionsangriff aus?
Bei einem Kollisionsangriff ist kein bestimmter Hashwert vorgegeben.
Der Angreifer sucht zwei unterschiedliche Eingaben:
x ≠ y
für die gilt:
Hash(x) = Hash(y)
Vereinfacht:
x ──→ Hashfunktion ──┐
├──→ gleicher Hashwert
y ──→ Hashfunktion ──┘
Welcher konkrete Hashwert am Ende entsteht, ist für die eigentliche Kollisionssuche zunächst nicht entscheidend.
Entscheidend ist nur, dass zwei unterschiedliche Eingaben denselben Hashwert besitzen.
Warum besitzt SHA-256 nur 128 Bit Collision Resistance?
SHA-256 erzeugt einen Hashwert mit 256 Bit.
Man könnte deshalb zunächst erwarten:
256-Bit-Hash
=
256 Bit Collision Security
Das ist jedoch nicht der Fall.
Für eine ideale Hashfunktion mit einer Ausgabelänge von n Bit liegt die generische Collision Resistance aufgrund des Birthday Bounds bei ungefähr:
n / 2 Bit
beziehungsweise einem Arbeitsaufwand in der Größenordnung von:
2^(n/2)
Für SHA-256 ergibt sich:
2^(256/2)
=
2^128
NIST führt SHA-256 deshalb mit einer Collision-Resistance-Stärke von 128 Bit.
Das ist kein spezieller Fehler oder eine Schwäche von SHA-256.
Es ist die erwartete generische Kollisionssicherheit eines idealen 256-Bit-Hashes.
Warum hilft das Birthday Paradox einem Angreifer?
Der Grund für die halbierte Sicherheitsstärke liegt darin, dass der Angreifer keinen bestimmten Hashwert treffen muss.
Er sucht lediglich irgendein Paar unterschiedlicher Eingaben mit gleichem Hash.
Das ähnelt dem bekannten Geburtstagsproblem.
Bei 23 Personen liegt die Wahrscheinlichkeit bereits bei ungefähr 50,7 Prozent, dass mindestens zwei Personen am selben Kalendertag Geburtstag haben – unter den üblichen vereinfachenden Annahmen.
Dabei suchen wir nicht nach jemandem mit einem bestimmten Geburtstag.
Wir fragen lediglich:
Gibt es irgendein Paar mit demselben Geburtstag?
Bei Hashwerten ist die Situation ähnlich.
Mit zunehmender Anzahl berechneter Hashwerte steigt die Anzahl möglicher Paare sehr schnell.
Deshalb wird eine Kollision statistisch wesentlich früher relevant als ein Treffer auf einen bestimmten vorgegebenen Hashwert.
Diesen Zusammenhang erkläre ich ausführlicher im Artikel Das Birthday Paradox. Wie ein Angreifer ihn gezielt ausnutzt, zeige ich im Artikel Wie funktioniert ein Birthday Attack?.
Collision Resistance und Preimage Resistance sind nicht dasselbe
Der Unterschied wird besonders deutlich, wenn man die Aufgaben direkt vergleicht.
Preimage Resistance
Ein bestimmter Hashwert H ist vorgegeben:
gegeben:
H
gesucht:
x
mit:
Hash(x) = H
Bei einer idealen 256-Bit-Hashfunktion liegt der generische Aufwand in der Größenordnung von:
2²⁵⁶
Collision Resistance
Kein bestimmter Hashwert ist vorgegeben:
gesucht:
x und y
mit:
x ≠ y
und
Hash(x) = Hash(y)
Aufgrund des Birthday Bounds liegt der generische Aufwand für einen idealen 256-Bit-Hash dagegen in der Größenordnung von:
2¹²⁸
Deshalb führt NIST SHA-256 mit:
| Eigenschaft | Security Strength |
|---|---|
| Preimage Resistance | 256 Bit |
| Collision Resistance | 128 Bit |
Was Preimage Resistance genau bedeutet, erkläre ich im Artikel Was ist Preimage Resistance?.
Collision Resistance und Second-Preimage Resistance sind ebenfalls verschieden
Auch Second-Preimage Resistance darf nicht mit Collision Resistance verwechselt werden.
Bei einem Second-Preimage-Angriff ist bereits eine konkrete Eingabe x vorgegeben:
gegeben:
x
gesucht:
y
mit:
x ≠ y
und
Hash(x) = Hash(y)
Bei einem Kollisionsangriff darf der Angreifer dagegen beide Eingaben suchen:
gesucht:
x und y
mit:
x ≠ y
und
Hash(x) = Hash(y)
Diese zusätzliche Freiheit ist entscheidend.
Eine praktische Methode zum Finden von Kollisionen bedeutet deshalb nicht automatisch, dass zu jeder beliebigen bestehenden Nachricht ein Second Preimage gefunden werden kann.
Die Unterschiede erkläre ich ausführlicher im Artikel Was ist Second-Preimage Resistance?.
Warum können Kollisionen gefährlich sein?
Kollisionen können problematisch werden, wenn eine Anwendung davon ausgeht, dass unterschiedliche relevante Daten nicht praktikabel denselben Hashwert erhalten können.
Ein besonders wichtiger Anwendungsbereich sind digitale Signaturen.
Vereinfacht wird dabei häufig nicht die gesamte Nachricht direkt signiert, sondern ein kryptografischer Hashwert der Nachricht in den Signaturprozess einbezogen.
Wenn ein Angreifer zwei unterschiedliche Nachrichten gezielt so konstruieren kann, dass sie denselben Hashwert besitzen, kann das abhängig vom verwendeten Verfahren und den konkreten Umständen die Sicherheit einer solchen Anwendung gefährden.
Deshalb ist Collision Resistance eine wichtige Sicherheitseigenschaft für kryptografische Hashfunktionen, die in digitalen Signaturverfahren verwendet werden.
Wichtig ist dabei erneut:
Bei einem Kollisionsangriff kann der Angreifer beide kollidierenden Nachrichten beeinflussen.
Das unterscheidet ihn von einem Second-Preimage-Angriff.
Was passiert, wenn Collision Resistance gebrochen wird?
Ein praktischer Kollisionsangriff bedeutet, dass der erwartete generische Aufwand nicht mehr notwendig ist, weil ein besseres Verfahren bekannt ist.
Genau das ist bei älteren Hashfunktionen passiert.
MD5
Für MD5 sind praktische Kollisionsangriffe bekannt.
MD5 sollte deshalb laut RFC 6151 nicht für Anwendungen verwendet werden, die Collision Resistance benötigen.
SHA-1
Auch die Collision Resistance von SHA-1 gilt als gebrochen.
2017 wurde mit SHAttered erstmals eine praktische Kollision für die vollständige SHA-1-Hashfunktion demonstriert.
Zwei unterschiedliche PDF-Dateien wurden so konstruiert, dass sie denselben SHA-1-Hash besitzen.
Das zeigt sehr anschaulich den Unterschied zwischen:
Kollisionen existieren mathematisch
und:
Kollisionen können praktisch gezielt gefunden werden
Erst die zweite Aussage ist der entscheidende kryptografische Sicherheitsbruch.
Bedeutet ein Collision-Angriff, dass man Hashes zurückrechnen kann?
Nein.
Das ist ein wichtiger Unterschied.
Wenn Collision Resistance gebrochen wird, bedeutet das nicht automatisch, dass auch Preimage Resistance gebrochen ist.
Ein Angreifer kann möglicherweise zwei Eingaben konstruieren:
x ≠ y
mit:
Hash(x) = Hash(y)
Das bedeutet aber nicht, dass er zu einem beliebig vorgegebenen Hashwert H eine passende Eingabe finden kann.
Das wäre ein Preimage-Angriff.
Die verschiedenen Sicherheitseigenschaften einer Hashfunktion können deshalb unterschiedlich stark sein.
Bedeutet gutes Avalanche-Verhalten Collision Resistance?
Ebenfalls nein.
Beim Avalanche Effect geht es darum, dass eine kleine Änderung der Eingabe viele Bits der Ausgabe beeinflusst.
Collision Resistance beantwortet dagegen die Frage, wie schwierig es ist, zwei unterschiedliche Eingaben mit demselben Hashwert zu finden.
Eine Hashfunktion kann ein überzeugendes Avalanche-Verhalten zeigen und trotzdem kryptografische Schwächen besitzen.
Der Avalanche Effect allein beweist deshalb keine Collision Resistance.
Wie der Effekt funktioniert und wie sich die veränderten Bits messen lassen, zeige ich im Artikel Was ist der Avalanche Effect?.
Die drei Resistance-Eigenschaften im Vergleich
Damit lassen sich die drei grundlegenden Problemstellungen direkt nebeneinanderstellen.
| Eigenschaft | Vorgegeben | Gesucht |
|---|---|---|
| Preimage Resistance | Hashwert H | x mit Hash(x) = H |
| Second-Preimage Resistance | Eingabe x | anderes y mit gleichem Hash |
| Collision Resistance | nichts Konkretes | beliebige unterschiedliche x und y mit gleichem Hash |
Für SHA-256 führt NIST unter anderem folgende Sicherheitsstärken:
| Eigenschaft | SHA-256 |
|---|---|
| Preimage Resistance | 256 Bit |
| Collision Resistance | 128 Bit |
| Second-Preimage Resistance | abhängig von der Nachrichtenlänge |
Damit wird deutlich, warum die drei Eigenschaften getrennt betrachtet werden müssen.
Was solche Bitangaben konkret bedeuten, erkläre ich im Artikel Wie sicher sind 128, 256 und 512 Bit?.
Das Wichtigste in Kürze
Collision Resistance beschreibt die Schwierigkeit, zwei unterschiedliche Eingaben mit demselben Hashwert zu finden.
Gesucht werden:
x und y
mit:
x ≠ y
und
Hash(x) = Hash(y)
Die wichtigsten Punkte:
- Collision Resistance bedeutet nicht, dass keine Kollisionen existieren.
- Kollisionen sind bei Hashfunktionen mit begrenzter Ausgabelänge mathematisch unvermeidbar.
- Entscheidend ist, wie schwierig es ist, eine Kollision gezielt zu finden.
- Bei einer Collision ist kein bestimmter Hashwert vorgegeben.
- Bei einem idealen
n-Bit-Hash liegt der generische Kollisionsaufwand in der Größenordnung von2^(n/2). - SHA-256 besitzt deshalb 128 Bit Collision Resistance.
- SHA-256 besitzt gleichzeitig 256 Bit Preimage Resistance.
- Collision Resistance ist nicht dasselbe wie Preimage Resistance.
- Collision Resistance ist nicht dasselbe wie Second-Preimage Resistance.
- Ein Kollisionsangriff bedeutet nicht automatisch, dass Hashwerte zurückgerechnet werden können.
- Gutes Avalanche-Verhalten beweist ebenfalls keine Collision Resistance.
Damit sind die drei zentralen Resistance-Eigenschaften kryptografischer Hashfunktionen voneinander abgegrenzt.
Wie geht es weiter?
Mit:
- Hashfunktionen
- Hash Collisions
- Avalanche Effect
- Preimage Resistance
- Second-Preimage Resistance
- Collision Resistance
sind die wichtigsten Grundlagen gelegt.
Damit ist der Grundlagenbereich abgeschlossen.
Im Bereich Sicherheit verstehen zeige ich als Nächstes, was diese Eigenschaften praktisch bedeuten – beginnend mit:
Danach kann es tiefer in einzelne Themen gehen – beispielsweise in die Funktionsweise von SHA-256, gebrochene Hashfunktionen oder Passwort-Hashing.
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 Definitionen und Sicherheitsstärken von Collision, Preimage und Second-Preimage Resistance.
-
National Institute of Standards and Technology (NIST), FIPS 180-4 – Secure Hash Standard (SHS) Offizielle Spezifikation von SHA-1 und SHA-2 einschließlich SHA-256.
-
National Institute of Standards and Technology (NIST), SP 800-107 Rev. 1 – Recommendation for Applications Using Approved Hash Algorithms Hintergrund zu Sicherheitseigenschaften kryptografischer Hashfunktionen und deren Verwendung. NIST hat Ende 2022 angekündigt, die Publikation zurückzuziehen; die ergänzenden Inhalte wurden auf die NIST-Hash-Functions-Seite überführt.
-
IETF, RFC 6151 – Updated Security Considerations for the MD5 Message-Digest and the HMAC-MD5 Algorithms IETF-Sicherheitsbetrachtungen zu MD5 und Collision Resistance.
-
Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik Markov, The First Collision for Full SHA-1, CRYPTO 2017. Primärquelle zur praktischen SHA-1-Kollision.