Preimage-Angriff

Urbild-Angriffe (engl. preimage attack) sind Angriffe auf eine kryptologische Hashfunktion mit dem Ziel, zu einem gegebenen Hash einer unbekannten Nachricht (Erstes-Urbild-Angriff, engl. first-preimage attack) eine Nachricht zu finden oder zu einer gegebenen Nachricht selbst (Zweites-Urbild-Angriff, engl. second-preimage attack) eine weitere Nachricht, die den gleichen Hash ergibt.

• Beim Erstes-Urbild-Angriff ist das Ziel, zu einem Hashwert ein Urbild zu finden.

Gegeben: Hash $S(N)$, die Nachricht N braucht nicht bekannt zu sein
Gesucht: $N'$, so dass gilt: $S(N')$ = $S(N)$.

• Beim Zweites-Urbild-Angriff ist das Ziel, zu einer Nachricht ein zweites Urbild zu finden, das auf denselben Wert gehasht wird.

Gegeben: Nachricht $N$, damit berechenbar ist der Hash der Nachricht $S(N)$
Gesucht: $N'$, so dass gilt: $N'\neq N$ und $S(N')$ = $S(N)$.

Beispiel

Der Text eines Vertrags („Ich bestelle eine Kaffeemaschine für 100 €“) sei mit Hilfe eines Hashes signiert. Ein Angreifer kann nun entweder den Hash der Signatur alleine oder auch noch zusätzlich den Text des Vertrags kennen. Für den verwendeten Hash-Algorithmus existiert ein praktikabler Urbild-Angriff, im ersten Fall ist nur ein erster Urbild-Angriff möglich, im zweiten Fall sind es beide Angriffsvarianten. Damit kann der Angreifer nun Texte erzeugen, die den gleichen Hash wie der Vertrag besitzen. Diese Texte werden im Normalfall keine sinnvolle Nachricht sein. Deshalb muss der Angreifer so lange Texte erzeugen, bis diese eine sinnvolle Nachricht bilden und für seinen Angriff tauglich sind („Ich bestelle 200 Kaffeemaschinen für je 2000 €“).

Erklärung

Wenn Passwörter direkt über einen Hash kodiert werden und dem Angreifer nur der Hash bekannt ist, so kann er sich durch einen Erstes-Urbild-Angriff ein weiteres Passwort verschaffen. Da dieses zweite Passwort den gleichen Hash hat, kann sich der Angreifer damit den Zugang verschaffen.

Besitzt der Angreifer nun bereits ein Passwort, beispielsweise durch einen Erstes-Urbild-Angriff oder durch Vorkenntnis, so kann er sich nun durch diese zusätzliche Information (und durch diejenige des bereits vorher bekannten Hashes der korrekten Passwörter) durch einen Zweites-Urbild-Angriff noch weitere gültige Passwörter verschaffen.

Grundsätzlich kann nicht entschieden werden, ob Passwörter, die durch Angriffe auf Hashes ermittelt wurden, originär sind. Denn bei allen üblichen Hash-Funktionen kann jeder Hash praktisch unbegrenzt vielen möglichen Passwörtern gegenüberstehen (Nicht-Injektivität). Es werden keine Merkmale außer dem eigentlichen Hash selbst gespeichert, die eine weitere Überprüfung ermöglichen würden.

Aufwand

Dadurch, dass bei einem Zweites-Urbild-Angriff mehr Informationen zur Verfügung stehen als bei einem Erstes-Urbild-Angriff, lassen sich beim Betrachten von Gleichungen, differentiellen Pfaden usw. der Kompressionsfunktion der Hash-Funktion mehr Variablen festhalten oder an andere Variablen binden, wodurch deren Anzahl an Freiheitsgraden sinkt und sich so der nötige Aufwand verringern lässt.

Nach der Kenntnis einer passenden Nachricht durch einen Zweites-Urbild-Angriff lässt sich diese durch die Anwendung der Hash-Funktion leicht in den für den Erstes-Urbild-Angriff notwendigen Hash überführen. Mit dem passenden Hash eines Erstes-Urbild-Angriffes lässt sich hingegen keine passende Nachricht mit geringerem Aufwand als einem zweiten Urbild-Angriff finden. Man bekommt also bei einem Zweites-Urbild-Angriff einen Erstes-Urbild-Angriff gewissermaßen geschenkt.

Urbild-Angriffe sind sehr viel schwerer durchzuführen als ein Kollisionsangriff, da Urbild-Angriffe stets nach einer speziellen Nachricht zu einer weiteren speziellen Nachricht bzw. zu einem Hashwert suchen, wohingegen ein Kollisionsangriff eine beliebige Nachricht zu einer beliebigen weiteren Nachricht sucht. Mit einem Geburtstagsangriff, der das Geburtstagsparadoxon ausnutzt, benötigt ein Angriff auf eine beliebige Hash-Funktion mit einem $m$ Bit langen Hashwert einen Aufwand von $2^{m/2}$, wohingegen ein naiver Urbild-Angriff per Brute-Force-Methode einen Aufwand von $2^{m}$ benötigt. Bei einer 128-bit Hash-Funktion benötigt ein Geburtstagsangriff somit 2⁶⁴ Versuche, ein Urbild-Angriff mit 2¹²⁸ jedoch nicht doppelt (also 2⁶⁵), sondern 2⁶⁴ mal so viele Versuche.