Warum SHA-1 unsicher ist

Hauke Stieler 29. Februar 2016 1 Kommentar

Schon seit längerem gilt der Hashing-Algorithmus SHA-1 als unsicher und sollte durch SHA-2 oder SHA-3 ersetzt werden. Was macht aber SHA-1 zu einem unsicheren Hash-Verfahren und wie hat man das herausgefunden?

Das Lustige an der Sache: SHA bedeutet secure hash algorithm, was in diesem Zuge doch recht ironisch ist.

Was Hash-Verfahren sind

Hash-Verfahren erzeugen aus einer Menge an Daten eine scheinbar willkürliche Folge an Bits. So wird durch SHA-1 beispielsweise aus dem Wort curi0sity die Zeichenfolge e544b48a746e297c9a10957ff0cf433cb41073d9. Ändert man nun ein Zeichen, also Curi0sity (großes statt kleines C am Anfang), so ändert sich der Hash-Wert komplett zu 5eed9a4940371dadad8119be0f9f32d94e52296c. Kleine Änderung, große Wirkung.

Genutzt werden Hash-Werte z.B. um zu überprüfen ob eine Datei richtig übertragen wurde. Der Sender stellt die Datei und den Hash bereit und der Empfänger bildet den Hash der empfangenen Datei. Sind die Werte identisch, so war die Übertragung mit sehr hoher Wahrscheinlichkeit erfolgreich. Sind die Werte nicht identisch, so war die Übertragung definitiv nicht erfolgreich.
Auch werden von Passwörtern erst die Hash-Werte bestimmt und diese dann übertragen oder gespeichert, sodass Hacker, die den Netzwerkverkehr mitschneiden, das Passwort nicht als Klartext haben. Sie haben somit nur den Hash-Wert, aus dem sich die originale Zeichenkette nicht wieder herstellen lässt (jeden Falls nicht mit einfachen mitteln und in kurzer Zeit).

Wann ist ein Hash-Algorithmus „gebrochen“?

Das Problem bei Hash-Algorithmen ist, dass die Größe der Ausgabe fest ist (bei SHA-1 z.B. 160 Bits), somit gibt es Kollisionen, sprich zwei Eingabewerte ergeben den selben Ausgabewert (s. Grafik oben).

Hash-Verfahren sind nichts anderes als surjektive Funktionen, sie haben zu jedem Element des Definitionsbereiches genau ein Element in der Wertemenge. Dabei gilt keine Injektivität, sprich ein Element aus der Wertemenge kann ein Bild von verschiedenen Elementen aus dem Definitionsbereich sein.
In anderen Worten: Jede Eingabe hat definitiv einen Hash-Wert und mehrere Eingaben können den selben Hash-Wert generieren.

Gebrochen ist ein Hash-Algorithmus nun dann, wenn man eine Kollision gefunden hat.
Schlecht ist das, weil dann zum Beispiel – um den Dateitransfer wieder aufzugreifen – eine Datei mit Fehlern übertragen wird, die aber trotzdem den selben Hash-Wert generiert wie eine korrekt übertragene Datei. Kollisionen bieten zudem große Möglichkeiten Angriffe z.B. gegen digitale Signaturen oder verschlüsselte Übertragungen zu starten. Eine Gleichverteilung der Hash-Werte ist deswegen überaus wichtig, da so die Wahrscheinlichkeit eine Kollision zu finden minimiert wird.

Hash-Algorithmen angreifen

Die einfachste – und langsamste Methode – einen Hash-Algorithmus anzugreifen (sprich eine Kollision zu finden) ist ein brute-force-Angriff (hierzulande auch Holzhammermethode genannt), bei dem man einfach alle Kombinationen an Eingaben durchprobiert und auf eine Kollision hofft. Bei SHA-1 bräuchte man im worst-case 2⁸⁰ Eingaben bis man auf eine Kollision trifft (also eine Laufzeit in O(2⁸⁰)), was mit heutigen Rechnern (sprich Cluster-Servern mit diversen Grafikeinheiten) nicht in annehmbarer Zeit machbar ist. Schafft man es diese Zeit zu reduzieren ist der Algorithmus nicht nur so gut wie gebrochen, sondern auch vergleichsweise unsicher.

Methoden dazu gibt es viele, die bei Algorithmen, welche nach dem Merkle-Darmgard-Prinzip erstellt sind, hauptsächlich auf die Kompressionsfunktion gerichtet sind (das Herzstück des Hash-Algorithmus). So ändert man bei einigen Verfahren die Eingabe auf eine bestimmte Art und Weise (Blocks, Bits oder ganze Hälften) und versucht Analogien in der Ausgabe zu bestimmen. So kann man z.B. über Differenzen der Ein- und Ausgabe (Differenzielle Kryptoanalyse, Boomerang Attacke) gehen, wobei es nicht unbedingt Bitweise Differenzen sein müssen, aber dazu später mehr. Andere Verfahren versuchen die Kompressionsfunktion zu reverse engineeren, sodass man beliebig Nachrichtenblöcke einfügen kann ohne den Hash zu ändern (Fixed-Point-Attack).

Alle Verfahren verbessern die Bedingungen zur Suche nach Kollisionen, was nicht bedeutet, dass es auf einmal in polynomieller Laufzeit machbar ist oder ähnliches, denn es wird höchstens der Exponent der Laufzeit etwas verringert.

Durchbruch durch The SHAppening bei SHA-1

2015 haben die Kryptoanalysten Marc Stevens und Pierre Karpman die Laufzeit zum finden einer Kollision auf O(2⁵⁷) gekürzt. Der Angriff gilt nicht direkt dem vollen SHA-1 Algorithmus, sondern mehr der Kompressionsfunktion (siehe oben). Die Kosten für eine Kollision liegen damit bei um die 100.000USD (wenn man Cloud-Server mietet), was durchaus im Rahmen von Kriminellen Organisationen oder auch manchen Einzelpersonen liegt. Auch wird das Finden von erneuten Kollisionen vereinfacht, da man bereits eine große Menge an Hashes berechnet hat und nur noch abgleichen muss. Marc Stevens und Pierre Karpman haben ihren Erfolg kurzerhand The SHAppening getauft.

Vorgehen bei The SHAppening

Als Grundlage wurde ein Meet-In-The-Middle Angriff auf eine 76-Iterationen Variante des SHA-Algorithmus‘ benutzt (normal sind 80 Iterationen der Kompressionsfunktion), der bei der CRYPTO 2015 vorgestellt wurde.

Als erstes musste der Disturbance vector (Störungsvektor) bestimmt werden, welcher eine Reihe von lokalen Kollisionen ist. Eine lokale Kollision ist dabei eine Differenz in einem Zwischenschritt, welche sich aus der Differenz von Wörtern aus dem Schritt davor ergibt. Man kann also eine Differenz zum Wort Ai durch Differenz zum Wort Wi-1 in gewisser Weise vorhersagen, wenn man so möchte.

Danach wurden die Bedingungen weiter verfeinert, was bedeutet, dass nach der ersten Runde die Bit-Belegungen günstig liegen mussten um weitere Runden mit wieder günstigen Ergebnissen (=Bit-Belegungen) zu finden. Die Belegung muss dabei so liegen, dass es beim letzten Schritt des differencial paths (Differenzpfad) keine Differenz mehr zum Hash-Wert der originalen Nachricht gibt (wobei Differenz nicht bitweise, sondern bezüglich den Operationen der SHA-1-Funktion gemeint ist). Ein Differenzpfad ist dabei eine Folge von Differenzen durch die ganzen Schritte des Hashings, wobei eben der letzte Schritt keine Differenz aufweisen darf. Ist das bei zwei Nachrichten der Fall, so handelt es sich um eine Kollision.
Bei diesem Schritt werden auch Bedingungen für die Nachrichtenbits gefunden, welche immer gelten, bzw. gelten müssen (s.u.).

Anschließend wurden auxiliary paths (Hilfspfade) optimiert, welche auch als Boomerang bezeichnet werden, da hierbei eine Boomerang Attack benutzt wird. Ein Boomerang ist eine Menge von Bits, die zu einer lokalen Kollision führen und das finden einer Kollision im Gesamtalgorithmus erleichtern.
Auch wurden in diesem Schritt neutral bits (neutrale Bits) gesucht und gefunden. Ein neutrales Bit ist ein Bit, welches man flippen kann (also 0 → 1 bzw. 1 → 0), sodass auch andere Bits im gleichen Schritt flippen um die Bedingungen für die Nachrichtenbits (s.o.) zu erhalten.

Im Prinzip waren das die Bedingungen und Vorbereitungen, die getroffen wurden bevor es an die Implementation auf den GPUs ging. Mehr dazu kann man in der Veröffentlichung von Stevens und Karpman nachlesen.

Kleine Anmerkung 😉
Ich bin absolut kein Experte auf dem Gebiet der Kryptoanalyse und habe versucht die Vorgänge aus der Veröffentlichung nachzuvollziehen und zu übersetzen. Ich würde mich daher über gefundene Fehler oder ausführlichere (und möglichst leicht verständliche) Informationen sehr freuen.

SHA-1 ersetzen

Da Stevens und Karpman es geschafft haben zu demonstrieren, dass SHA-1 nicht mehr sicher ist (in Bezug auf: „Eine Kollision kann man in brauchbarer Zeit mit für Kriminelle Organisationen schaffbaren Mitteln finden“), raten diese auf SHA-2 oder SHA-3 zu wechseln. Einige Browser verbieten bereits Zertifikate mit SHA-1 Hashes und auch viele andere Dienste sind dabei um zu steigen.
Ob der Algorithmus für Dateihashes (wie eingangs mit dem Dateitransfer beschrieben) ausreicht liegt wahrscheinlich im Auge des Betrachters, da dies meist keine sicherheitsrelevanten Bereiche sind (ebenso z.B. Commit-Hashes von git, uvm.).

Wrap-up

Wer vorher – so wie ich – dachte, dass das brechen oder für unsicher erklären eines Hash-Algorithmus‘ nur heißt Kollisionen zu finden, der ist jetzt hoffentlich nicht mehr davon überzeugt. Die Analyse von Hash-Algorithmen ist ein überaus komplexes Thema (wie die gesamte Kryptographie an sich) und sollte nicht unterschätzt werden. Wenn also ein Hash-Algorithmus unsicher ist, heißt es lediglich, dass es Möglichkeiten gibt Kollisionen leichter zu finden als mit brute-force-Angriffen.

Bei SHA-1 wurden die Vorbedingungen durch Eigenschaften der Kompressionsfunktion verfeinert, sodass man die Nachricht, welche eine Kollision erzeugen soll, einfacher Finden kann. Das heißt nun, dass man Kollisionen in geringer Zeit finden kann und das zu erträglichen Kosten. Kriminelle Organisationen (oder durchaus auch Einzelpersonen) haben also theoretisch die Möglichkeit Kollisionen zu finden und so Verschlüsselte Verbindungen oder Passwörter zu knacken.

Wie schon gesagt: Unsichere Hash-Algorithmen sollten dringend ersetzt werden.