Konsequenzen der erfolgreichen Angriffe auf SHA-1
Nahezu alle sicherheitsrelevanten Anwendungen nutzen derzeit die Hash-Funktion SHA-1. Sie kommt bei digitalen Signaturen und Integritätschecks von Software zum Einsatz. Ist das alles gefährdet und was kommt als Ersatz in Frage?
- Dr. Reinhard Wobst
- Jürgen Schmidt
Um realistisch einzuschätzen, was die Angriffe der chinesischen Forschergruppe bedeuten, ist etwas Hintergrundwissen erforderlich. Eine Hash-Funktion erzeugt aus einem Datensatz eine vergleichsweise kurze Zahl, den Hash-Wert, der als eine Art Fingerabdruck benutzt wird. Stimmt der abgespeicherte Hash-Wert des Originals mit dem der vorliegenden Kopie überein, geht man davon aus, dass die Daten gleich beziehungsweise unverändert sind.
Die Qualität einer kryptographischen Hash-Funktion beurteilt man vor allem nach ihrer Widerstandsfähigkeit gegen zwei Typen von Angriffen:
- Preimage-Angriff: Wie schwer ist es, zu einem vorgegebenen Hash-Wert eine Nachricht zu erzeugen, die denselben Hash-Wert ergibt?
- Kollisionsangriff: Wie schwer ist es, zwei verschiedenen Nachrichten mit gleicher Prüfsumme zu finden?
Beide Angriffe lassen sich theoretisch mit Brute Force - also roher (Rechen-)Gewalt - realisieren. SHA-1 beispielsweise bildet Hash-Werte mit 160 Bit. Es gibt somit insgesamt nur 2160 verschiedene, und viele Datensätze ergeben folglich denselben Hash-Wert. Hat man einen vorgegebenen Hash-Wert und probiert 2160 zufällige Nachrichten durch, ist die Wahrscheinlichkeit, eine mit dem gleichen zu erhalten, sehr hoch. Dieser Vorgang würde mit reeller Hardware allerdings weit über 100 Millionen Jahre dauern.
Will man nur eine Kollision finden, also zwei Nachrichten mit dem gleichen aber beliebigen Hash-Wert, muss man für ähnliche Erfolgschancen nur 280 zufällig ausgewählte Nachrichten durchprobieren. Preimage-Angriffe auf SHA-1 erfordern damit nicht doppelt soviele Versuche, sondern 280 mal so viele Hash-Operationen wie ein Kollisionsangriff. Trotzdem liegt auch die einfache Suche nach SHA-1-Kollisionen noch weit außerhalb des technisch Machbaren.
Geburtstag
Den enormen Unterschied zwischen dem Aufwand für Preimage- und Kollisionsattacken veranschaulicht das Geburtstagsparadoxon. Wenn Sie jemanden suchen, der am selben Tag Geburtstag hat wie Sie, müssen sie für eine Trefferwahrscheinlichkeit von 50 Prozent 253 Leute fragen. Ist Ihnen der konkrete Geburtstag egal und Sie suchen nur zwei Personen mit dem gleichen, genügen viel weniger. Bereits bei 23 Menschen ist die Chance fünfzig Prozent, dass zwei davon am selben Tag Geburtstag haben.
Gelingt ein Angriff mit deutlich weniger Versuchen als beim Brute-Force-Ansatz, gilt das Verfahren als geknackt. Genau das ist nach Schneiers Ansicht der chinesischen Forschergruppe gelungen: Sie haben ein Verfahren entwickelt, eine Kollision statt mit 280 bereits mit 269 Operationen zu ermitteln. Das reduziert die Zahl der notwendigen Operationen um den Faktor 2048 (211).
