Dipl.-Inform. Carsten Eilers

Man unterscheidet zwei Arten von Angriffen auf Hash-Funktionen:

• Bei einem Kollisionsangriff sollen zwei Nachrichten mit identischem Hash-Wert gefunden werden:
  Gesucht werden zwei Nachrichten M und M' (M ≠ M') mit H(M) = H(M').
• Bei einem Preimage-Angriff wird zu einer gegebenen Nachricht (dem preimage) und dem dazu berechneten Hashwert eine zweite Nachricht mit identischem Hashwert gesucht:
  Gegeben sind M und H(M), gesucht wird M' (M ≠ M') mit H(M) = H(M').
  Im Rahmen eines gezielten Angriff kommt als weitere Einschränkung hinzu, dass M' ein sinnvoller und für den Angreifer nützlicher Text ist.

Das Geburtstagsparadoxon

Der Aufwand für die beiden Angriffe unterscheidet sich stark, wie man am sog. Geburtstagsparadoxon erkennen kann:

• Um mit einer Trefferwahrscheinlichkeit von 50 Prozent jemanden zu finden, der an einem bestimmten Tag Geburtstag hat, werden 253 Personen benötigt (Preimage-Angriff).
• Werden dagegen nur zwei Personen gesucht, die an demselben Tag Geburtstag haben, reichen für eine Trefferwahrscheinlichkeit von 50 Prozent 23 Personen aus. Bei mehr als 57 Personen steigt die Wahrscheinlichkeit auf über 99 Prozent an (Kollisionsangriff).

Abgeleitet vom Geburtstagsparadoxon wurde der sog. Geburtstagsangriff entwickelt:

Es werden mehrere Varianten der originalen Nachricht erstellt, deren Unterschiede dem Opfer nicht auffallen. Ebenso werden Varianten der gefälschten Nachricht erstellt.
Der Angreifer sucht dann ein Paar aus Original und Fälschung, die den gleichen Hashwert ergeben.
Signiert das Opfer danach das ausgewählte Original, gilt diese Signatur auch für die dazu gehörende Fälschung.

Um einem Geburtstagsangriff entgegenzuwirken, gibt es zwei Möglichkeiten:

1. Ein möglichst langer Hashwert erhöht dem Aufwand zum Finden passender Texte.
2. Ändert der Signierer den Text direkt vor dem Signieren, läuft der Angriff ins Leere: Die Signatur des geänderten Textes passt nicht mehr zur vorbereiteten Fälschung.

Die Auswirkungen der Angriffe

Bei der Frage nach den Auswirkungen der Angriffe stellt sich zuerst die Frage, was denn der Angreifer überhaupt erreichen will.

Es gibt zwei Haupteinsatzgebiete für Hashfunktionen: Digitale Signaturen und Integritätsprüfungen.

Im Rahmen einer digitalen Signatur wird die Hashfunktion verwendet, um den zu signierenden Text zu komprimieren: Statt des kompletten Textes wird nur dessen Hashwert signiert ('Hash-then-Sign'-Paradigma).

Bei der Integritätsprüfung wird der Hashwert beliebiger Daten berechnet, gespeichert und später mit dem erneut berechneten Hashwert verglichen. Stimmen gespeicherter und berechneter Hashwert überein, wurden die Daten nicht verändert. So kann z.B. die Unversehrtheit von Dateien oder Netzwerkpaketen sichergestellt werden.

Kryptographisch gilt eine Hashfunktion als gebrochen (und damit unbrauchbar), wenn man allgemein Kollisionen berechnen kann.
Für einen praktischen Angriff reicht das nicht aus: Ein Angreifer muss eine für ihn brauchbare Kollision berechnen können. Schließlich nutzt es ihm wenig, einen signierten Vertragstext durch eine signierte Buchstabenwüste oder ein ausführbares Programm durch eine nicht ausführbare Datei zu ersetzen.

Brute Force geht immer - zumindest wenn man genug Zeit hat

Grundsätzlich ist immer ein Brute-Force-Angriff möglich: Ein 128-Bit-Hashwert kann 'nur' 2¹²⁸ verschiedene Werte annehmen, ein 160-Bit-Hashwert 2¹⁶⁰ Werte, und allgemein ein n-Bit-Hashwert 2ⁿ Werte. Es muss also zwangsläufig viele Kollisionen geben.

Um zu gegebenen Eingabedaten und zugehörigem Hashwert mit ausreichender Wahrscheinlichkeit eine Kollision zu finden, müsste man also 'nur' die Hashwerte für 2¹²⁸ bzw. 2¹⁶⁰ Eingaben berechnen. Was einfach zu lange dauert, um einen brauchbaren Angriff zu ergeben.

'Schneller' werden Brute-Force-Angriffe, wenn nur irgendeine Kollision gesucht wird, der Hashwert also beliebig sein kann. Für Hashfunktionen mit einem 128-Bit-Hashwert werden dann 2⁶⁴ Berechnungen benötigt, bei einem 160-Bit-Hashwert 2⁸⁰ , und das ohne dass die Hashfunktion irgendeine Schwachstelle enthalten muss. Mit steigender Rechenleistung wird eine Hashfunktion also generell unsicher(er). Obwohl auch diese Werte zur Zeit noch nicht wirklich beherrschbar sind.

Schlechter sieht die Sache aus, wenn die Hashfunktion eine Schwachstelle enthält. So können inzwischen Kollisionen in MD4 per Hand berechnet werden, in SHA-1 wurde der Aufwand auf 2⁶³ Berechnungen reduziert. Zwar ist auch das noch eine sehr große Zahl, es besteht aber immer die Möglichkeit, das sich die Angriffe weiter verbessern lassen, wie es z.B. "The SHAppening für SHA-1 gezeigt hat

Und was bedeutet das in der Praxis?

Beim Angriff auf eine digitale Signatur sind zwei Fälle zu unterscheiden:

• Kann der Angreifer den Inhalt des zu signierenden Textes bestimmen, kann er im Rahmen eines Geburtstagsangriffs vorab zwei passende Texte suchen.
• Sind Text und Signatur vorgegeben, bleibt dem Angreifer ein Preimage-Angriff: Er muss zum gegebenen Text einen zweiten Text mit identischem Hashwert finden, der einen für ihn nützlichen Inhalt hat.

Der Aufwand für einen Geburtstagsangriffs ist durch die bereits erwähnten Angriffe auf MD4, MD5, SHA und SHA-1 deutlich gesunken. Man sollte diese Verfahren deshalb wirklich nicht mehr nutzen. Die aktuellen Verfahren, insbesondere SHA-2 und SHA-3, sind dagegen noch für einige Jahre sicher.

Da ein Geburtstagsangriff voraussetzt, dass das Opfer den vom Angreifer gelieferten Text signiert, besteht ein einfacher Schutz darin, keine von Dritten vorgelegten Texte zu signieren oder diese vor dem Signieren abändern.

Für bereits signierte Texte ist das natürlich keine Lösung, hier hilft nur die (rechtzeitige) Verwendung einer sicheren Hashfunktion wie SHA-2 oder SHA-3. Zumal Flames Angriff auf die Windows-Updates bewiesen hat, dass zumindest Angriffe auf MD5 erfolgreich durchgeführt werden können. Auch hier gilt: SHA-2 und SHA-3 sind noch einige Zeit sicher, so lange der Hashwert lang genug ist (mind. 256 Bit). Denn ohne Schwachstellen in Algorithmus oder Implementierung sind für einen Preimage-Angriff 2^{(Länge des Hashwerts)} Berechnungen notwendig. Was bei 256 Bit langen oder noch längeren Hashwerten einfach zu lange dauert.

Dies gilt entsprechend auch für integritätsgeschützte Daten: Ein Angreifer könnte beim Einsatz der unsicheren Hashfunktionen evtl. zwei Programme mit gleichem Hashwert konstruieren, von denen eines harmlos ist und das andere Schadfunktionen enthält. Für Sourcecode hat Nat McHugh das 2014 bereits für PHP-Skripte bewiesen, indem er zwei auf den ersten Blick identische PHP-Skripte erstellt hat, die den gleichen MD5-Hashwert haben, aber unterschiedliche Ausgaben erzeugen. Zu einem vorhandenen Programm ein Schadprogramm mit identischen Hashwert zu finden, um z.B. einen eingeschleusten Virus zu tarnen, ist dagegen praktisch unmöglich.

Zusätzliche Schutzmaßnahmen

Der beste Schutz vor Angriffen ist die Verwendung einer sicheren Hashfunktion wie SHA-2 oder SHA-3 mit möglichst langen Hashwerten. Zusätzlichen Schutz bietet die Verschlüsselung der signierten bzw. integritätsgeschützten Daten: Wenn der Angreifer die Originaldaten nicht kennt, kann er auch keinen Preimage-Angriff durchführen.

Hiermit ist das Thema "Kryptographie" fast abgeschlossen. In der nächsten Folge gibt es zum Abschluss noch einen Überblick über die vorgestellten Algorithmen und ihre Sicherheit.

Carsten Eilers