Konsequenzen der erfolgreichen Angriffe auf SHA-1

18.02.2005 13:22 Uhr Dr. Reinhard Wobst, Jürgen Schmidt

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?

Um realistisch einzuschätzen, was die Angriffe der chinesischen Forschergruppe [1] 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 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 [2]. 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¹¹).

Keine Panik

Trotzdem gehen Krypto-Experten wie Schneier und Kaliski davon aus, dass man SHA-1 durchaus noch recht unbesorgt einsetzen kann. Das rührt daher, dass auch 2⁶⁹ noch eine recht große Zahl ist. Auf Spezialhardware kann man eine Hash-Operation in etwa 40 Takten ausführen [1] [3]. Selbst wenn man diese von 33 MHz auf 4 GHz beschleunigen könnte, würde sie immer noch 170.000 Jahre benötigen. Selbst ein Riesen-Cluster aus solchen Maschinen könnte innerhalb eines realistischen Zeitraums weniger Jahre keine Kollision finden. Der überraschende Durchbruch von Wang et al. führt jedoch vor Augen, dass man sich auf einem solchen Polster nicht länger ausruhen kann.

Der zweite Grund ist deshalb fast noch wichtiger: Um beispielsweise einen digital signierten Vertrag nachträglich zu fälschen, müsste der Angreifer einen Preimage-Angriff durchführen. Er müsste also zum vorgegebenen Hash-Wert des echten Vertrags einen zweiten, gefälschten Vertrag finden, der denselben Hash-Wert ergibt. Das erfordert schon prinzipiell sehr viel mehr Operationen (2¹⁶⁰). Und alle bekannten Angriffe -- nach bisherigem Kenntnisstand auch der von Wang et al. -- beziehen sich nur auf Kollisionen. Verfahren, die die Anzahl der benötigten Operationen für Preimage-Angriffe deutlich reduzieren, sind bisher nicht bekannt.

Damit sind bereits existierende digitale Unterschriften und solche, bei denen man das Dokument selbst erstellt, erst einmal nicht gefährdet. Mit Kollisionen, die sich in realistischer Zeit errechnen lassen, sind aber durchaus Angriffe auf digitale Signaturen möglich, wenn der Angreifer den Hash-Wert des Originals frei bestimmen kann. Das illustriert das folgende, etwas vereinfachte Beispiel.

Falschspiel beim Vertragspoker

Ein intelligenter Angreifer erstellt zwei Verträge. Einen mit dem richtigen Preis für das Haus und einen mit einer sehr viel höheren Summe. Da er weiß, dass er mit 2^x Hash-Operationen eine Kollision finden kann, überlegt er sich x kosmetische Änderungen wie zusätzliche Leerzeichen am Zeilenende. Indem er alle möglichen Kombinationen der Änderungen durchführt, erzeugt er jeweils 2^x Versionen der beiden Verträge, unter denen sich mit hoher Wahrscheinlichkeit ein Paar mit gleichem Hash-Wert findet. Lässt er sein Opfer dann das Exemplar mit dem richtigen Kaufpreis unterschreiben, kann er im Nachhinein den Text ersetzen, ohne dass sich der Hash-Wert ändert und damit vor Gericht ziehen.

Der neue Angriff auf SHA-1 reduziert den Aufwand eines Betrügers für einen ähnlichen Kollisionsangriff unter Umständen um das Zweitausendfache, bleibt aber zum Glück immer noch außerhalb das real Machbaren. Angriffe auf SHA-1-Signaturen würden beispielsweise gelöschte Absätze in Word-Dateien nutzen, um Blocks mit zufälligen Variationen in ein Dokument einzufügen. Grundsätzlich ist es eine gute Idee, vor dem digitalen Signieren eines Dokuments immer noch selbst eine kosmetische Änderung vorzunehmen.

Auch durch Preimage-Angriffe ließen sich im Übrigen Verfahren nicht knacken, die erst digital signieren und dann chiffrieren. Wer nicht an den Klartext herankommt, kann nicht einmal eine MD4-Summe fälschen. Daher bleiben SSH und IPSec sicher. Unberührt bleiben auch so genannte HMAC-Summen. Dies sind Hashes, die sich nur bei Kenntnis eines geheimen Schlüssels berechnen lassen. Sie sind so konstruiert, dass ein Angreifer ohne das Geheimnis keine Kollisionen berechnen kann.

Die SHA-1-Attacken haben auch keine Bedeutung für die Sicherheit von Passwörtern, die in vielen Systemen nur als Hash-Werte abgespeichert werden. Die Berechnung eines Passworts zu einem vorgegebenem Hash-Wert bleibt vorerst aussichtslos, dort bleiben Wörterbuchattacken die größte Bedrohung.

Thronfolger

Trotz aller Einschränkungen bezüglich der praktischen Realisierbarkeit der Angriffe lassen es die Erfolge der Krypto-Analyse ratsam erscheinen, sich auf die Suche nach potenziellen Nachfolgern für SHA-1 zu machen. Burt Kaliski, Leiter der Forschungsabteilung von RSA, rechnet innerhalb der nächsten fünf bis zehn Jahre mit mit ersten erfolgreichen Preimage-Angriffen auf SHA-1.

Die bisher kaum eingesetzten Weiterentwicklungen von SHA-1 mit längeren Hash-Werten SHA-224, SHA-256, SHA-384 und SHA-512 stehen in der Erbfolge weit oben. Für sie spricht, dass sie neben SHA-1 die einzigen Hash-Funktionen sind, die das amerikanische National Institute of Standards and Technology (NIST [4]) in seinen Federal Information Processing Standards [5] spezifiziert hat. Medienberichten [6] zu Folge hat das NIST auch kurz vor dem Bekanntwerden der neuen SHA-1-Angriffe eröffnet, man plane demnächst SHA-1 durch SHA-256 und SHA-512 abzulösen.

Welche Algorithmen in Deutschland als geeignet für qualifizierte elektronische Signaturen gelten, wird vom BSI festgelegt und von der Regulierungsbehörde für Telekommunikation veröffentlicht [7]. Die Version für 2004 erachtet neben der SHA-Familie auch den europäischen Algorithmus RIPEMD-160 als "bis Ende 2009 für die Anwendung bei qualifizierten elektronischen Signaturen geeignet".

Ob SHA-256/512 aber tatsächlich die richtige Wahl für eine langfristige Perspektive sind, bezweifeln manche Kryptanalytiker. Denn mehr Sicherheit bieten sie hauptsächlich durch längere Hash-Werte. Da sie jedoch zur selben Familie wie SHA-1 gehören, sind sie unter Umständen gegen dieselben Attacken anfällig. Denn bisher haben sich die Kryptanalytiker mit ihnen viel weniger beschäftigt als mit SHA-1. Wenn sich das jetzt ändert, könnten durchaus neue Schwächen ans Licht kommen.

Letzteres gilt auch für den europäischen Algorithmus RIPEMD-160, der sich nicht gegen SHA-1 durchsetzen konnte. Die diesem Verfahren zu Grunde liegende Variante RIPEMD wurde bereits 2004 geknackt. Das noch häufig eingesetzte MD5 haben die chinesischen Forscher bereits 2004 überwunden [8].

Dass ein längerer Hash-Wert nicht automatisch mehr Sicherheit bedeutet, gilt leider auch für das Aneinanderhängen zweier verschiedener Hash-Werte über die gleiche Nachricht, etwa von MD5 und SHA-1. Alternativen, die Blockchiffres verwenden, sind in der Regel zu langsam.

Ein ebenfalls in den letzten Tagen öfter angeführter Algorithmus ist Whirlpool [9]. Er erzeugt Hash-Werte mit 512 Bit mit einer eigenen Block-Chiffre namens W und ist dabei mindestens zweimal langsamer als SHA-1. Des Weiteren ist er kaum zwei Jahre alt und noch wenig untersucht.

Die Frage der Thronfolger ist also längst nicht beantwortet. Vielleicht klärt sie sich ja auch erst in einem ähnlichen Verfahren wie bei der Ablösung des in Ungnade gefallenen DES. Dort errang der Algorithmus Rijndael bei einer Ausschreibung des NIST die Krone des Advanced Encryption Standard (AES).

[10]Links

[1] Comparative Analysis of the Hardware Implementations of Hash Functions SHA-1 and SHA-512 [11] (PDF) (ju [12])

URL dieses Artikels:
https://www.heise.de/-270648

Links in diesem Artikel:
[1] https://www.heise.de/news/Kryptoverfahren-SHA-1-geknackt-135372.html
[2] http://de.wikipedia.org/wiki/Geburtstagsparadoxon
[3] #lit-u2
[4] http://csrc.nist.gov/
[5] http://csrc.nist.gov/CryptoToolkit/tkhash.html
[6] http://www.fcw.com/fcw/articles/2005/0207/web-hash-02-07-05.asp
[7] http://www.regtp.de/tech_reg_tele/in_06-02-02-00-00_m/03/index.html
[8] https://www.heise.de/news/Verunsicherung-um-Sicherheit-von-Kryptoalgorithmen-100595.html
[9] http://planeta.terra.com.br/informatica/paulobarreto/WhirlpoolPage.html
[10]
[11] http://www.east.isi.edu/~bschott/pubs/grembowski02comparative.pdf
[12] mailto:ju@ct.de