zurück zum Artikel

Warum SHAttered wichtig ist

Hintergrund
Warum SHAttered wichtig ist

Die SHAttered benannten Kollisionen zum SHA-1-Verfahren sind ein wichtiger Meilenstein. Sie zeigen klar und deutlich, dass SHA-1 für den Einsatz als kryptographische Hash-Funktion nicht mehr geeignet ist.

Zunächst zur praktischen Bedeutung des im Februar vorgestellten Angriffs auf SHA-1 [1]: Die Forscher erstellten zwei PDF-Dokumente [2] mit nahezu identischem Inhalt. Nur, dass das eine einen blauen Hintergrund hatte und das andere einen roten. Doch beide ergeben den gleichen SHA-1-Hash-Wert. Das sollte praktisch unmöglich sein (mehr dazu später).

Die zwei SHAttered-PDFs nebeneinander -- der Unterschied ist offensichtlich.
Die zwei SHAttered-PDFs nebeneinander -- der Unterschied ist offensichtlich. (Bild: shattered.it)

Um daraus einen realen Angriff zu konstruieren, hätten sie genauso gut zwei Versionen eines Vertrags über den Kauf eines Hauses aufsetzen können. Die "blaue" Version wiese dann einen Kaufpreis von 1 Million Euro aus, die "rote" hingegen nur noch 1 Euro. Trotzdem ergäben beide den gleichen SHA-1-Hash. Anschließend würden sie das Haus für 1 Million kaufen und den Verkäufer den blauen Vertrag unterschreiben lassen.

Doch der sollte sich nicht zu früh über die Million freuen, wenn diese Unterschrift digital mit einem SHA-1-Hash erfolgt ist. Der Angreifer trennt nämlich dann die digitale Signatur ab und "klebt" sie unter den "roten" Vertrag mit dem Kaufpreis von 1 Euro. Der ist damit vom echten Vertrag nicht zu unterscheiden, und der Betrüger kann beweisen, dass ihm das Haus quasi geschenkt wurde. Der Verkäufer sieht die erhoffte Million niemals (sofern er nicht mit einer Kopie des blauen Vertrags den Betrug rechtzeitig beweisen kann – aber das führt jetzt zu weit).

Eine etwas komplexere Variante dieses Angriffs führten Marc Stevens et al übrigens mit MD5 [3] vor: Sie ließen sich ein Zertifikat von einer Zertifizierungsstelle unterschreiben. Diese digitale MD5-Unterschrift montierten sie unter eine Zertifikat einer eigenen Zertifizierungsstelle. Mit dem hätten sie sich anschließend beliebige Zertifikate ausstellen können.

Theoretisch machbar - praktisch unmöglich

Solche Betrügereien sollten eigentlich praktisch unmöglich sein; deshalb verwendet man schließlich keine einfache Prüfsumme, sondern ein kryptographisches Hash-Verfahren. Praktisch unmöglich bedeutet: Es ist zwar theoretisch durchaus denkbar, aber ein realer Angreifer mit realistischen Ressourcen kann es in der ihm zur Verfügung stehenden Zeit nicht praktisch umsetzen.

Eine Hash-Funktion bildet einen beliebig langen Datensatz auf einen kurzen Wert ab. Bei SHA-1 ist das ein 160-Bit-Wert. Es gibt also insgesamt nur 2160 verschiedene Hash-Werte. Da es aber unendlich viele Datensätze gibt, erzeugen einige davon notwendigerweise den gleichen Hash-Wert – es gibt sogar unendlich viele solcher Kollisionen.

Was die Hash-Funktion von einer einfachen Prüfsumme unterscheidet, ist nicht nur, dass es sehr unwahrscheinlich ist, dass zwei Datensätze zufällig den gleichen Hash-Wert ergeben. Eine kryptographisch sichere Hash-Funktion muss darüber hinaus gewährleisten, dass es keine Abkürzung zum Finden zweier Datensätze mit identischem Hash-Wert gibt. Erst das garantiert die Fälschungssicherheit. Bei SHA-1 müsste man für eine Trefferwahrscheinlichkeit von 50 Prozent 280 Möglichkeiten durchprobieren (dafür ist das Geburtstagsparadoxon [4] verantwortlich).

280 Berechnungen sind nötig – eigentlich

Um das zu veranschaulichen: Die Anzahl der erforderlichen 280 Berechnungen entspricht der Anzahl aller Sandkörner auf der Erde – wenn man sie nochmal mit 1000 multipliziert. Angesichts dieser riesigen Zahl wäre es praktisch unmöglich, eine SHA-1-Kollision zu berechnen. Das Problem ist jedoch: Es gibt eine Abkürzung. Bereits 2005 zeigten chinesische Forscher, dass man eine SHA-1-Kollision mit 269 Rechenschritten errechnen kann. Damit galt SHA-1 für Kryptologen bereits als geknackt.

Allerdings waren 269 Operationen immer noch viel zu viel, um es praktisch umzusetzen; SHA-1 wurde also nach wie vor eingesetzt. Doch die Angriffe wurden verbessert und die Rechenleistung wuchs. Und 2017 gelang es Forschern in einer Kooperation des CWI Amsterdam mit Google mit etwa 263 Operationen eine reale Kollision zu erzeugen.

Praktische Bedeutung

Auch für die Shattered-Attacke muss man noch viel rechnen – allerdings nur ein Bruchteil von der Zeit, die für einen klassischen Bruteforce-Angriff nötig ist.
Um eine SHA-1-Kollision per Bruteforce herbeizuführen, müsste man im Durchschnitt 12 Millionen GPUs ein ganzes Jahr rechnen lassen. Durch Shattered sinkt diese Zahl auf 110 GPUs. (Bild: shattered.it)

Mancher mag denken, dass die für SHAttered benötigten 6500 CPU-Jahre die Latte immer noch ausreichend hoch legen. Doch angesichts von Cloud Computing und dem immer noch gültigen Moore'schem Gesetz zum Wachstum der Rechenleistung kombiniert mit weiteren Fortschritten bei den Angriffen ist das ein gefährlicher Irrtum. So mussten etwa 2008 die Forscher um Marc Stevens noch einen Cluster von über 200 Playstation-3-Konsolen mehrere Tage rechnen lassen. Heute spuckt jeder PC eine solche MD5-Kollision in weniger als einer Sekunde aus. Die Gnadenfrist ist mit SHAttered definitiv abgelaufen: SHA-1 ist offiziell tot.

Wer SHA-1 heute noch einsetzt, sollte schleunigst auf SHA256 umsteigen. Das verwendet einen längeren Hash-Wert mit 256-Bit, was die erforderliche Zahl von Operationen auf 2128 anhebt. Es hat sich auch trotz seiner Verwandtschaft gegen die für SHA-1 entwickelten Angriffstechniken als immun erwiesen. Andere Alternativen wie SHA-3 und Blake und deren Vor- und Nachteile diskutiert der heise-Security-Artikel Kryptographie in der IT - Empfehlungen zu Verschlüsselung und Verfahren [5] im Kapitel zu "Hashes und MACs". (ju [6])

Update 24.1.2017, 16:00: Erklärung zur Herleitung der Zahl 2^80 korrigiert und das Geburtstagsparadoxon eingefügt.


URL dieses Artikels:
http://www.heise.de/-3634341

Links in diesem Artikel:
[1] https://www.heise.de/meldung/Todesstoss-Forscher-zerschmettern-SHA-1-3633589.html
[2] https://shattered.it/
[3] https://www.heise.de/meldung/25C3-Erfolgreicher-Angriff-auf-das-SSL-Zertifikatsystem-192869.html
[4] https://www.heise.de/security/artikel/Konsequenzen-der-erfolgreichen-Angriffe-auf-SHA-1-270648.html
[5] https://www.heise.de/security/artikel/Kryptographie-in-der-IT-Empfehlungen-zu-Verschluesselung-und-Verfahren-3221002.html
[6] mailto:ju@ct.de