Hash mich

Konsequenzen der erfolgreichen Angriffe auf SHA-1

Reinhard Wobst, Jürgen Schmidt - 18.02.2005

Nahezu alle sicherheitsrelevanten Anwendungen nutzen derzeit die Hash-Funktion SHA-1. Sie kommt bei digitalen Signaturen und Intergritätschecks von Software zum Einsatz. Passwörter speichern moderne Betriebssysteme nicht direkt, sondern nur deren Hash-Wert. SHA-1 kommt in OpenPGP und S/MIME zum Einsatz, IPSec nutzt es genauso wie SSH und selbst das am Horizont dräuende TCPA setzt auf den Secure Hash Algorithm. Neben RSA und AES bildet SHA-1 das Fundament unserer kryptographischen Sicherheitsinfrastruktur. Wackelt durch die erfolgreichen Angriffe das gesamte Gebäude?

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:

1. Preimage-Angriff: Wie schwer ist es, zu einem vorgegebenen Hash-Wert eine Nachricht zu erzeugen, die denselben Hash-Wert ergibt?
   
2. 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 2¹⁶⁰ verschiedene, und viele Datensätze ergeben folglich denselben Hash-Wert. Hat man einen vorgegebenen Hash-Wert und probiert 2¹⁶⁰ 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 2⁸⁰ zufällig ausgewählte Nachrichten durchprobieren. Preimage-Angriffe auf SHA-1 erfordern damit nicht doppelt soviele Versuche, sondern 2⁸⁰ 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 2⁸⁰ bereits mit 2⁶⁹ Operationen zu ermitteln. Das reduziert die Zahl der notwendigen Operationen um den Faktor 2048 (2¹¹).