Was ist Preimage Resistance?
Eine wichtige Sicherheitseigenschaft kryptografischer Hashfunktionen ist die sogenannte Preimage Resistance.
Dabei geht es um eine zunächst einfach klingende Aufgabe:
Ein Hashwert ist bekannt. Kann ich eine Eingabe finden, die genau diesen Hashwert erzeugt?
Bei einer kryptografisch sicheren Hashfunktion soll das praktisch nicht möglich sein.
Vereinfacht:
gegeben:
Hashwert H
gesucht:
Eingabe x
mit:
Hash(x) = H
Diese Eigenschaft wird als Preimage Resistance bezeichnet.
Was ist ein Preimage?
Der Begriff Preimage lässt sich mit „Urbild“ übersetzen.
Nehmen wir eine Hashfunktion:
x
↓
Hashfunktion
↓
H
Die Eingabe x erzeugt den Hashwert H.
Damit ist x ein Preimage von H.
Bei einem Preimage-Angriff betrachten wir die Situation genau andersherum:
?
↓
Hashfunktion
↓
H
Der Hashwert ist bereits bekannt.
Gesucht wird irgendeine Eingabe, die genau diesen Hashwert erzeugt.
Ein Preimage-Angriff versucht also nicht zwangsläufig, eine ursprüngliche Eingabe „zurückzurechnen“. Gesucht wird irgendeine Eingabe, deren Hash dem vorgegebenen Hashwert entspricht.
Ein Beispiel mit SHA-256
Angenommen, wir kennen folgenden SHA-256-Hash:
a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e
Wir wissen zunächst nicht, welche Eingabe diesen Hash erzeugt hat.
Die Aufgabe lautet:
Finde x mit:
SHA-256(x)
=
a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e
Eine mögliche Lösung wäre:
Hello World
Denn:
SHA-256("Hello World")
=
a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e
Die entscheidende Frage ist jedoch:
Wie finde ich eine solche Eingabe, wenn ich vorher nur den Hashwert kenne?
Bei einer preimage-resistenten Hashfunktion soll es dafür keinen praktikablen allgemeinen Weg geben.
Warum kann man einen Hash nicht einfach zurückrechnen?
Hashing wird manchmal so beschrieben, als wäre es eine Art Einbahnstraße.
Das ist als Vorstellung hilfreich, aber technisch etwas vereinfacht.
Eine Hashfunktion nimmt eine Eingabe und berechnet daraus einen Hashwert:
Eingabe
↓
Hashfunktion
↓
Hashwert
Es gibt jedoch keinen dazugehörigen Entschlüsselungsalgorithmus:
Hashwert
↓
???
↓
ursprüngliche Eingabe
Das unterscheidet Hashing beispielsweise von Verschlüsselung.
Bei einer Verschlüsselung ist die Rückrichtung ausdrücklich vorgesehen:
Klartext
↓
Verschlüsselung + Schlüssel
↓
Ciphertext
↓
Entschlüsselung + Schlüssel
↓
Klartext
Bei einer Hashfunktion existiert kein entsprechender Schlüssel, mit dem man den Hashwert einfach wieder entschlüsseln könnte.
Was Hashing grundsätzlich von Verschlüsselung und Encoding unterscheidet, erkläre ich ausführlicher im Artikel Was ist eine Hashfunktion?.
Warum können unterschiedliche Eingaben denselben Hashwert besitzen?
Hashfunktionen bilden einen sehr großen Eingaberaum auf einen begrenzten Ausgaberaum ab.
SHA-256 besitzt:
2²⁵⁶
mögliche Hashwerte.
Für ausreichend große Eingaberäume gibt es jedoch mehr mögliche Eingaben als mögliche Hashwerte.
Deshalb müssen unterschiedliche Eingaben existieren, die denselben Hashwert erzeugen.
Dieses Phänomen nennt man eine Hash Collision.
Für einen Preimage-Angriff ist dabei ein anderer Punkt entscheidend:
Es muss nicht eine bestimmte ursprüngliche Eingabe wiedergefunden werden.
Es genügt, eine beliebige Eingabe zu finden, die auf den vorgegebenen Hashwert abgebildet wird.
Warum Kollisionen mathematisch unvermeidbar sind und warum sie eine andere kryptografische Problemstellung darstellen, erkläre ich im Artikel Was ist eine Hash Collision?.
Preimage Resistance bedeutet nicht „unmöglich“
Die Aussage:
Man kann einen Hash nicht zurückrechnen.
ist als vereinfachte Erklärung verbreitet, aber technisch zu absolut.
Preimage Resistance bedeutet nicht, dass es mathematisch unmöglich ist, eine passende Eingabe zu finden.
Sie bedeutet vielmehr, dass es praktisch nicht möglich sein soll, zu einem vorgegebenen Hashwert eine passende Eingabe zu finden.
Ein Angreifer kann beispielsweise Kandidaten ausprobieren:
Eingabe 1 → Hash → passt nicht
Eingabe 2 → Hash → passt nicht
Eingabe 3 → Hash → passt nicht
...
Eingabe n → Hash → gesuchter Hash
Bei einem ausreichend großen Suchraum wird dieser Ansatz jedoch schnell unpraktikabel.
Warum Hashes nicht entschlüsselt werden, Angreifer aber trotzdem passende Eingaben finden können, erkläre ich im Artikel Kann man einen Hash zurückrechnen?.
Wie schwierig ist ein Preimage-Angriff auf SHA-256?
SHA-256 erzeugt einen Hashwert mit 256 Bit.
Damit existieren:
2²⁵⁶
mögliche Hashwerte.
Für eine ideale 256-Bit-Hashfunktion liegt der generische Aufwand, ein Preimage mit hoher Wahrscheinlichkeit zu finden, in der Größenordnung von:
2²⁵⁶
Hashoperationen.
NIST ordnet SHA-256 entsprechend eine Preimage-Resistance-Stärke von 256 Bit zu.
Die Zahl 2²⁵⁶ ist enorm.
Sie entspricht ungefähr:
1,16 × 10⁷⁷
Das liegt weit außerhalb dessen, was mit klassischer Rechentechnik praktisch vollständig durchsucht werden könnte.
Muss man wirklich exakt 2²⁵⁶ Versuche durchführen?
Nein.
2²⁵⁶ beschreibt die Größenordnung des generischen Suchaufwands.
Eine passende Eingabe könnte bei einer konkreten Suche früher gefunden werden.
Entscheidend ist deshalb nicht, dass exakt 2²⁵⁶ Berechnungen durchgeführt werden müssen.
Die Angabe von 256 Bit Preimage Security beschreibt vielmehr die Größenordnung der Sicherheitsstärke gegenüber einem generischen Preimage-Angriff.
Was solche Bitangaben bedeuten, erkläre ich im Artikel Wie sicher sind 128, 256 und 512 Bit?.
Preimage Resistance ist nicht Collision Resistance
Preimage Resistance wird leicht mit Collision Resistance verwechselt.
Die Aufgaben unterscheiden sich jedoch deutlich.
Preimage
Ein bestimmter Hashwert H ist vorgegeben:
gegeben:
H
gesucht:
x
mit:
Hash(x) = H
Collision
Bei einer Collision ist kein bestimmter Hashwert vorgegeben.
Gesucht werden zwei unterschiedliche Eingaben:
gesucht:
x ≠ y
mit:
Hash(x) = Hash(y)
Das macht einen großen Unterschied beim generischen Suchaufwand.
Für einen idealen 256-Bit-Hash gilt grob:
| Eigenschaft | generischer Aufwand |
|---|---|
| Preimage | 2²⁵⁶ |
| Collision | 2¹²⁸ |
Warum Collisions bereits in der Größenordnung von 2¹²⁸ relevant werden, erkläre ich im Artikel Was ist eine Hash Collision?.
Preimage ist auch nicht Second Preimage
Eine weitere verwandte Eigenschaft ist Second-Preimage Resistance.
Beim Preimage-Angriff ist ein Hashwert vorgegeben:
H
Gesucht wird ein x mit:
Hash(x) = H
Beim Second-Preimage-Angriff ist dagegen bereits eine konkrete Eingabe x bekannt.
Gesucht wird eine andere Eingabe y mit:
x ≠ y
und
Hash(x) = Hash(y)
Das sind unterschiedliche kryptografische Problemstellungen.
Second-Preimage Resistance erkläre ich deshalb ausführlicher im nächsten Artikel Was ist Second-Preimage Resistance?.
Was hat das mit Passwörtern zu tun?
An dieser Stelle entsteht leicht ein Missverständnis.
Wenn ein Passwort lediglich mit einer schnellen allgemeinen Hashfunktion wie SHA-256 gehasht würde, könnte ein Angreifer nach einem Datenbank-Leak bekannte oder wahrscheinliche Passwörter ausprobieren:
"password" → SHA-256 → Vergleich
"123456" → SHA-256 → Vergleich
"sommer2026" → SHA-256 → Vergleich
Das widerspricht nicht der Preimage Resistance von SHA-256.
Der Angreifer versucht nicht, den gesamten theoretischen Suchraum eines 256-Bit-Hashes zu durchsuchen.
Er nutzt aus, dass menschliche Passwörter häufig aus einem wesentlich kleineren und vorhersehbareren Suchraum stammen.
Deshalb sollte eine schnelle allgemeine Hashfunktion wie SHA-256 nicht allein zur Speicherung von Passwörtern verwendet werden.
Für Passwörter werden spezielle Password-Hashing-Verfahren verwendet, die einen Salt und einen Kostenfaktor einbeziehen und einzelne Rateversuche gezielt verteuern. Die entsprechenden Anforderungen beschreibt NIST in SP 800-63B.
Dieses Thema behandle ich ausführlich in einem eigenen Artikel über Passwort-Hashing.
Preimage Resistance bedeutet nicht, dass kurze Eingaben sicher sind
Nehmen wir an, ein Hashwert stammt garantiert von einer vierstelligen PIN.
Dann gibt es lediglich:
0000
bis
9999
also:
10.000
mögliche Eingaben.
Ein Angreifer könnte alle Möglichkeiten ausprobieren:
0000 → Hash
0001 → Hash
0002 → Hash
...
9999 → Hash
und jeden erzeugten Hashwert mit dem gesuchten Hash vergleichen.
Die kryptografische Stärke der Hashfunktion ändert daran nichts.
Die Sicherheitsstärke der Hashfunktion und die Größe beziehungsweise Entropie des Eingaberaums sind zwei unterschiedliche Dinge.
Die Preimage Resistance einer Hashfunktion schützt deshalb nicht automatisch einen kleinen oder vorhersehbaren Eingaberaum.
Die Sicherheit eines konkreten Systems hängt nicht nur vom verwendeten Hashalgorithmus ab.
Warum ist Preimage Resistance wichtig?
Preimage Resistance verhindert, dass aus einem bekannten Hashwert auf einfache Weise eine passende Eingabe konstruiert werden kann.
Das ist für viele kryptografische Anwendungen wichtig.
Hashfunktionen werden als Bausteine in zahlreichen kryptografischen Verfahren verwendet.
Wenn ein Angreifer zu einem bestimmten Hashwert mit praktikablem Aufwand eine passende Eingabe erzeugen könnte, könnten darauf aufbauende Sicherheitsannahmen verletzt werden.
Preimage Resistance gehört deshalb zu den grundlegenden Sicherheitseigenschaften kryptografischer Hashfunktionen.
Preimage Resistance und der Avalanche Effect sind nicht dasselbe
Auch der Avalanche Effect ist eine wichtige Eigenschaft kryptografischer Hashfunktionen, beschreibt aber etwas anderes.
Beim Avalanche Effect geht es darum, wie stark sich der Hashwert verändert, wenn die Eingabe geringfügig verändert wird.
Preimage Resistance fragt dagegen:
Kann ich zu einem bereits vorgegebenen Hashwert eine passende Eingabe finden?
Ein gutes Avalanche-Verhalten beweist deshalb keine Preimage Resistance.
Wie sich bereits ein einzelnes verändertes Bit auf einen SHA-256-Hash auswirken kann, zeige ich im Artikel Was ist der Avalanche Effect?.
Das Wichtigste in Kürze
Preimage Resistance beschreibt die Schwierigkeit, zu einem vorgegebenen Hashwert eine passende Eingabe zu finden.
Gegeben ist:
H
Gesucht wird:
x
mit:
Hash(x) = H
Die wichtigsten Punkte:
- Der Hashwert ist beim Preimage-Angriff bereits vorgegeben.
- Gesucht wird irgendeine Eingabe, die diesen Hashwert erzeugt.
- Es muss nicht die ursprünglich verwendete Eingabe gefunden werden.
- Preimage Resistance bedeutet nicht, dass die Suche mathematisch unmöglich ist.
- Bei einem idealen 256-Bit-Hash liegt der generische Suchaufwand in der Größenordnung von
2²⁵⁶. - SHA-256 wird eine Preimage-Resistance-Stärke von 256 Bit zugeordnet.
- Preimage Resistance ist nicht dasselbe wie Collision Resistance.
- Preimage Resistance ist nicht dasselbe wie Second-Preimage Resistance.
- Ein gutes Avalanche-Verhalten beweist ebenfalls keine Preimage Resistance.
- Kleine oder vorhersehbare Eingaberäume können trotzdem durch Ausprobieren durchsucht werden.
- Deshalb ist SHA-256 allein beispielsweise kein geeignetes Verfahren zur Passwortspeicherung.
Die entscheidende Frage lautet also nicht:
Kann irgendeine Eingabe diesen Hashwert erzeugen?
Sondern:
Kann ich mit realistisch verfügbaren Ressourcen eine solche Eingabe finden?
Wie geht es weiter?
Preimage Resistance ist eine von mehreren wichtigen Sicherheitseigenschaften kryptografischer Hashfunktionen.
Als Nächstes bietet sich die verwandte Frage an:
Was ist Second-Preimage Resistance?
Danach lassen sich die drei Eigenschaften direkt miteinander vergleichen:
Preimage Resistance
↓
Second-Preimage Resistance
↓
Collision Resistance
Weitere passende Themen sind:
- Was ist Collision Resistance?
- Was ist eine Hash Collision?
- Wie sicher sind 128, 256 und 512 Bit?
- Warum ist SHA-256 nicht für Passwörter geeignet?
- Wie funktioniert SHA-256?
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), CSRC Glossary – Preimage Resistance Definition von Preimage Resistance.
-
National Institute of Standards and Technology (NIST), Hash Functions Übersicht über kryptografische Hashfunktionen und die Sicherheitsstärken von SHA-2 und SHA-3.
-
National Institute of Standards and Technology (NIST), SP 800-107 Rev. 1 – Recommendation for Applications Using Approved Hash Algorithms NIST-Empfehlungen zu Sicherheitseigenschaften und Anwendungen kryptografischer Hashalgorithmen. NIST hat Ende 2022 angekündigt, die Publikation zurückzuziehen; relevante Inhalte wurden in die aktuelle NIST-Hash-Functions-Seite überführt.
-
National Institute of Standards and Technology (NIST), SP 800-63B – Authentication and Lifecycle Management Aktuelle NIST-Anforderungen und Empfehlungen zur sicheren Speicherung von Passwörtern.