Was ist Second-Preimage Resistance?
Eine wichtige Sicherheitseigenschaft kryptografischer Hashfunktionen ist die sogenannte Second-Preimage Resistance.
Dabei ist eine bestimmte Eingabe bereits bekannt.
Die Aufgabe besteht darin, eine andere Eingabe mit demselben Hashwert zu finden.
Vereinfacht:
gegeben:
Eingabe x
gesucht:
Eingabe y
mit:
x ≠ y
und
Hash(x) = Hash(y)
Bei einer kryptografisch sicheren Hashfunktion soll es praktisch nicht möglich sein, eine solche zweite Eingabe zu finden.
Diese Eigenschaft wird als Second-Preimage Resistance bezeichnet.
Was ist ein Second Preimage?
Nehmen wir eine Eingabe x:
x
↓
Hashfunktion
↓
H
Die Eingabe erzeugt den Hashwert H.
Bei einem Second-Preimage-Angriff kennen wir sowohl x als auch den daraus resultierenden Hashwert.
Gesucht wird nun eine andere Eingabe y:
x ──→ Hashfunktion ──→ H
↑
y ──→ Hashfunktion ───┘
wobei gilt:
x ≠ y
Die zweite Eingabe y wird als Second Preimage bezeichnet.
Ein Beispiel mit SHA-256
Nehmen wir wieder:
Hello World
Der SHA-256-Hash lautet:
a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e
Bei einem Second-Preimage-Angriff wäre die Aufgabe nun:
Finde eine andere Eingabe als
Hello World, die exakt denselben SHA-256-Hash erzeugt.
Gesucht wäre also ein y mit:
y ≠ "Hello World"
aber:
SHA-256(y)
=
a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e
Für eine second-preimage-resistente Hashfunktion soll diese Aufgabe mit realistisch verfügbaren Ressourcen nicht praktikabel lösbar sein.
Der entscheidende Unterschied zu Preimage Resistance
Second-Preimage Resistance klingt zunächst sehr ähnlich wie Preimage Resistance.
Der Unterschied liegt darin, was bereits vorgegeben ist.
Bei einem Preimage-Angriff ist ein Hashwert vorgegeben:
gegeben:
H
gesucht:
x
mit:
Hash(x) = H
Bei einem Second-Preimage-Angriff ist dagegen bereits eine konkrete Eingabe vorgegeben:
gegeben:
x
gesucht:
y
mit:
x ≠ y
und
Hash(x) = Hash(y)
Das sind unterschiedliche kryptografische Problemstellungen.
Was Preimage Resistance genau bedeutet, erkläre ich im Artikel Was ist Preimage Resistance?.
Second Preimage ist nicht dasselbe wie eine Collision
Noch wichtiger ist die Abgrenzung zu einer Hash Collision.
Bei einer Collision darf ein Angreifer beide Eingaben suchen:
gesucht:
x und y
mit:
x ≠ y
und
Hash(x) = Hash(y)
Es ist also zunächst keine der beiden Eingaben vorgegeben.
Bei einem Second-Preimage-Angriff sieht die Situation anders aus:
x ist bereits vorgegeben
gesucht:
y
mit:
x ≠ y
und
Hash(x) = Hash(y)
Diese zusätzliche Vorgabe macht einen entscheidenden Unterschied.
Ein erfolgreicher Kollisionsangriff bedeutet deshalb nicht automatisch, dass man zu einer beliebigen bereits vorhandenen Nachricht ein Second Preimage finden kann.
Warum Kollisionen trotzdem eine wichtige Sicherheitseigenschaft kryptografischer Hashfunktionen betreffen, erkläre ich in den Artikeln Was ist eine Hash Collision? und Was ist Collision Resistance?.
Warum ist dieser Unterschied praktisch wichtig?
Stell dir vor, eine bestimmte Datei besitzt einen bekannten Hashwert.
Zum Beispiel:
original.pdf
↓
SHA-256
↓
H
Ein Second-Preimage-Angriff würde versuchen, eine andere Datei zu erzeugen:
manipuliert.pdf
↓
SHA-256
↓
H
mit:
original.pdf ≠ manipuliert.pdf
Die ursprüngliche Datei ist dabei bereits fest vorgegeben.
Genau das unterscheidet dieses Szenario von einem normalen Kollisionsangriff, bei dem der Angreifer beide kollidierenden Dateien konstruieren darf.
Diese Unterscheidung ist wichtig, wenn man praktische Angriffe auf Hashfunktionen beurteilt.
Wie sicher ist SHA-256 gegen Second-Preimage-Angriffe?
Hier ist etwas mehr Vorsicht notwendig als bei der Preimage- oder Collision-Sicherheit.
Für SHA-256 gibt NIST die Second-Preimage-Resistance-Stärke mit:
256 − L(M)
Bit an.
L(M) hängt dabei von der Länge der betrachteten Nachricht ab.
NIST definiert für SHA-256:
L(M) = log₂(len(M) / 512)
wobei len(M) die Nachrichtenlänge in Bit und 512 die Blockgröße von SHA-256 ist.
Das bedeutet:
Die Second-Preimage-Sicherheit von SHA-256 wird nicht für jede denkbare Nachrichtenlänge pauschal mit 256 Bit angegeben.
Für gewöhnliche Nachrichten bleibt die Sicherheitsstärke sehr hoch. Bei sehr langen Nachrichten kann sie jedoch geringer sein.
Diese Besonderheit ist einer der Gründe, warum Preimage Resistance und Second-Preimage Resistance trotz ihrer Ähnlichkeit getrennt betrachtet werden.
Warum spielt die Nachrichtenlänge eine Rolle?
SHA-256 verarbeitet Nachrichten blockweise.
Die Blockgröße beträgt laut FIPS 180-4:
512 Bit
Sehr lange Nachrichten bestehen daher aus vielen einzelnen Blöcken.
Für iterative Hashkonstruktionen sind generische Second-Preimage-Angriffe bekannt, die bei sehr langen Nachrichten weniger Arbeit benötigen können als die naiv erwarteten 2²⁵⁶ Operationen.
Deshalb berücksichtigt NIST bei SHA-256 die Nachrichtenlänge in der angegebenen Second-Preimage-Resistance-Stärke.
Für einen Grundlagenartikel ist dabei vor allem wichtig:
Second-Preimage Resistance ist eine eigene Sicherheitseigenschaft und ihre konkrete Sicherheitsstärke muss nicht immer identisch mit der Preimage Resistance sein.
Bedeutet eine gefundene Collision auch ein Second Preimage?
Nein.
Angenommen, ein Angreifer findet:
A ≠ B
mit:
Hash(A) = Hash(B)
Dann hat er eine Collision gefunden.
Das bedeutet aber nicht automatisch, dass er zu einer beliebigen bereits existierenden Nachricht X eine andere Nachricht mit demselben Hash finden kann.
Bei der Collision durfte er A und B selbst auswählen.
Beim Second-Preimage-Angriff ist dagegen:
X
bereits fest vorgegeben.
Das ist eine deutlich andere Ausgangssituation.
Genau deshalb unterscheidet die Kryptografie zwischen Collision Resistance und Second-Preimage Resistance.
Warum ist Second-Preimage Resistance wichtig?
Hashwerte werden häufig verwendet, um Daten eindeutig zu repräsentieren oder als Bestandteil anderer kryptografischer Verfahren.
Wenn ein Angreifer zu einer bereits feststehenden Nachricht einfach eine zweite Nachricht mit demselben Hashwert erzeugen könnte, könnte das je nach Anwendung problematisch sein.
Second-Preimage Resistance soll genau solche Angriffe erschweren.
Sie gehört deshalb zusammen mit:
- Preimage Resistance
- Collision Resistance
zu den grundlegenden Sicherheitseigenschaften kryptografischer Hashfunktionen.
Die drei Problemstellungen im Vergleich
Jetzt lassen sich die drei Begriffe bereits gut voneinander unterscheiden.
Preimage Resistance
gegeben:
H
gesucht:
x
mit:
Hash(x) = H
Second-Preimage Resistance
gegeben:
x
gesucht:
y
mit:
x ≠ y
und
Hash(x) = Hash(y)
Collision Resistance
gesucht:
x und y
mit:
x ≠ y
und
Hash(x) = Hash(y)
Der entscheidende Unterschied ist also:
| Eigenschaft | Was ist vorgegeben? | Was wird gesucht? |
|---|---|---|
| Preimage | Hashwert | passende Eingabe |
| Second Preimage | eine Eingabe | zweite Eingabe mit gleichem Hash |
| Collision | nichts Konkretes | zwei unterschiedliche Eingaben mit gleichem Hash |
Diese drei Aufgaben sehen ähnlich aus, besitzen aber unterschiedliche kryptografische Sicherheitsanforderungen.
Das Wichtigste in Kürze
Second-Preimage Resistance beschreibt die Schwierigkeit, zu einer bereits vorgegebenen Eingabe eine andere Eingabe mit demselben Hashwert zu finden.
Gegeben ist:
x
Gesucht wird:
y
mit:
x ≠ y
und
Hash(x) = Hash(y)
Die wichtigsten Punkte:
- Eine konkrete erste Eingabe ist bereits vorgegeben.
- Gesucht wird eine andere Eingabe mit demselben Hashwert.
- Second-Preimage Resistance ist nicht dasselbe wie Preimage Resistance.
- Second-Preimage Resistance ist nicht dasselbe wie Collision Resistance.
- Bei einem normalen Kollisionsangriff darf ein Angreifer beide Eingaben suchen.
- Eine gefundene Collision liefert deshalb nicht automatisch ein Second Preimage für eine beliebige bestehende Nachricht.
- Bei SHA-256 hängt die von NIST angegebene Second-Preimage-Resistance-Stärke von der Nachrichtenlänge ab.
- Für SHA-256 gibt NIST diese Stärke mit
256 − L(M)Bit an. - Second-Preimage Resistance gehört zu den grundlegenden Sicherheitseigenschaften kryptografischer Hashfunktionen.
Damit fehlt noch eine der drei zentralen Eigenschaften:
Collision Resistance.
Wie geht es weiter?
Im nächsten Artikel geht es deshalb um die Frage:
Dort lässt sich auch erklären, warum SHA-256 zwar einen 256 Bit langen Hash erzeugt, aber eine Collision-Resistance-Stärke von 128 Bit besitzt.
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 Definition und Sicherheitsstärken von Preimage, Second Preimage und Collision Resistance.
-
National Institute of Standards and Technology (NIST), CSRC Glossary – Second Preimage Resistance Definition von Second-Preimage Resistance.
-
National Institute of Standards and Technology (NIST), FIPS 180-4 – Secure Hash Standard (SHS) Offizielle Spezifikation von SHA-256, einschließlich Hash- und Blockgröße.
-
John Kelsey, Bruce Schneier, Second Preimages on n-bit Hash Functions for Much Less than 2^n Work, EUROCRYPT 2005. Wissenschaftliche Grundlage für generische Second-Preimage-Angriffe auf lange Nachrichten und die von NIST berücksichtigte Abhängigkeit von der Nachrichtenlänge.