Md5/Sicherheit

topic - Kurzbeschreibung

Beschreibung

MD5 wurde mit dem Ziel entwickelt, eine höhere Sicherheit als sein Vorgänger MD4 zu bieten, da Kryptoanalysen dieser Zeit ergaben, dass MD4 wahrscheinlich nicht kollisionsresistent ist. MD5 erlangte weite Verbreitung und wurde ursprünglich als kryptographisch sicher angesehen. Heute ist bekannt, dass MD5 keine Kollisionsresistenz bietet. Mit geringem Aufwand lassen sich zwei unterschiedliche Nachrichten $M$ und $M'$ erzeugen, die denselben Hashwert $\operatorname {MD5} (M)=\operatorname {MD5} (M')$ erzeugen. Nicht alle kryptographischen Anwendungen erfordern Kollisionsresistenz. Beispielsweise setzt die Schnorr-Signatur, anders als die Signatur auf Basis von RSA oder Digital Signature Algorithm, keine kollisionsresistente Hashfunktion voraus.

In Internetstandards und technischen Richtlinien, beispielsweise von der IETF oder dem BSI, wird heute von der Verwendung von MD5 abgeraten.

Preimage-Angriffe

Seit 2009 ist ein theoretischer Preimage-Angriff auf MD5 bekannt, der jedoch mit $2^{123,4}$ MD5-Hashoperationen einen Rechenaufwand jenseits der Praktikabilität erfordert. Bei einem Preimage-Angriff sucht man zu einem vorgegebenen Hashwert $\operatorname {MD5} (M)$ die Nachricht $M$ oder eine andere Nachricht $M'$, so dass man $\operatorname {MD5} (M)=\operatorname {MD5} (M')$ erhält. Da man beim Preimage-Angriff $M$ nicht frei wählen kann, ist dieser Angriff viel schwieriger.

Ein Preimage-Angriff wäre beispielsweise erforderlich, um nachträglich ein gefälschtes Dokument zu erstellen, das zu einer bestehenden, mit RSA und MD5 erzeugten Signatur passt. Es ist jedoch durch einen Kollisionsangriff möglich, zwei Dokumente zu erstellen, die denselben MD5-Hashwert ergeben, dann das erste, legitime Dokument signieren zu lassen, und anschließend dieses durch das zweite, gefälschte Dokument auszutauschen.

Kollisionsangriffe

Bereits 1994 veröffentlichten Bert de Boer und Antoon Bosselaers einen Algorithmus zum Erzeugen von Pseudokollisionen auf die Kompressionsfunktion von MD5: zwei unterschiedliche Initialisierungskonstanten ergeben für dieselbe Nachricht denselben Hashwert.

1996 fand Hans Dobbertin eine Kollision für zwei unterschiedliche Nachrichten. Es handelt sich dabei um eine echte Kollision, also zwei speziell präparierte Nachrichten, die sich unterscheiden, aber dennoch denselben Hashwert ergeben. Allerdings verwendete Dobbertin eine modifizierte MD5-Variante, in der andere Initialisierungskonstanten (für A, B, C, D) verwendet werden. Auch war es nicht möglich, den Inhalt der kollidierenden Nachrichten beliebig vorzugeben. Somit waren praktische Angriffe auf MD5 zwar nicht möglich, aber die ersten Schwächen des Algorithmus wurden deutlich.

Im August 2004 gelang es einer chinesischen Forschergruppe um Xiaoyun Wang Kollisionen in MD5 systematisch zu erzeugen. Der Anfang der Nachrichten kann beliebig gewählt werden, ist aber bei beiden Nachrichten identisch (Common-Prefix-Kollision): $M_{0},M_{1},...,M_{i-1}$. Dahinter folgen zwei präparierte Paare von Nachrichtenblöcken $M_{i},M_{i+1}$ und $M'_{i},M'_{i+1}$, die sich unterscheiden, aber dennoch denselben Hashwert ergeben. Aufgrund der Merkle-Damgård-Konstruktion kann optional an beide Nachrichten ein identischer Suffix angehangen werden, wobei beide Nachrichten weiterhin einen identischen Hashwert ergeben: $M_{i+2},...,M_{i+n}$. Der Rechenaufwand zur Erzeugung des ersten Angriffsblocks dauerte auf einem IBM p690 Hochleistungsrechner etwa eine Stunde, die des zweiten Angriffsblocks bis zu fünf Minuten. Der Angriff setzt voraus, dass zwei 512-Bit-Nachrichtenblöcke (insgesamt 128 Bytes) in die Nachricht eingefügt werden, die abhängig vom Nachrichtenpräfix präpariert werden. Da die Angriffsblöcke nicht frei gewählt werden können, schränkt dies je nach Anwendungsszenario die Praktikabilität des Angriffs ein.

Kurz nach der Veröffentlichung von Wang wurde das Volunteer-Computing-Projekt MD5CRK eingestellt, das versuchte, eine Kollision per Brute-Force-Methode zu finden. Die Angriffsmethode wurde von Wang und anderen Forschergruppen verbessert, sodass ein PC heute innerhalb von Sekunden eine MD5-Kollision berechnen kann.

Der Aufwand zum Finden einer Kollision ist größer, wenn der Anfang der beiden Nachrichten abweicht (Chosen-Prefix-Kollision). 2008 gelang es einer Gruppe um Marc Stevens und Alexander Sotirov einen solchen Kollisionsangriff durchzuführen, um ein gefälschtes CA-Zertifikat zu erzeugen, das von gängigen Webbrowsern als vertrauenswürdige Zertifizierungsstelle anerkannt wurde. Mit diesem waren sie prinzipiell in der Lage, für jede beliebige URL ein SSL-Zertifikat zu fälschen und damit die Sicherheitsmechanismen von HTTPS auszuhebeln. Die Arbeit wurde erstmals auf dem 25. Chaos Communication Congress vorgestellt und einige Monate später in einem wissenschaftlichen Artikel veröffentlicht. Zur Kollisionsberechnung benutzten sie einen Cluster von 200 Sony PlayStation 3.

Die 2012 entdeckte Windows-Malware Flame verwendete ein gefälschtes Code-Signing-Zertifikat, das auf einer neuen und bis dahin unbekannten Variante einer Chosen-Prefix-Kollision für MD5 basierte.

Password-Hashing

Ein Einsatzzweck von MD5 und anderen kryptographischen Hashfunktionen ist die Schlüsselableitung aus einem geheimen Passwort. Wenn die Hashwerte dem Angreifer bekannt sind, können sie per Brute-Force-Methode oder Wörterbuchangriff zum Klartext zurückgerechnet werden. Der Angriff besteht darin, zu möglichst vielen Passwortkandidaten den dazugehörigen Hashwert zu berechnen und ihn auf Gleichheit mit dem gesuchten Passwort-Hashwert zu vergleichen. Dabei handelt es sich um eine naiven Preimage-Angriff, dessen Erfolg davon abhängt, ob das Passwort erraten werden kann und wie viele Hashwerte der Angreifer in einer gegebenen Zeit berechnen kann.

Die Brute-Force-Methode ist bei MD5 durch den Einsatz von GPGPU besonders effizient, da sich der MD5-Algorithmus auf Grafikprozessoren gut parallelisieren und effizient berechnen lässt. Aus diesem Grund eignen sich spezialisierte Hashfunktionen wie zum Beispiel bcrypt oder PBKDF2 besser zum sicheren Speichern von Passwort-Hashwerten.

Eine Maßnahme zur Erhöhung der Effizienz eines Brute-Force-Angriffs ist es, mehrere Passwort-Hashwerte gleichzeitig anzugreifen. Hierbei muss die Hashwert-Berechnung nur einmal erfolgen, kann aber gegen eine Liste von Hashwerten erfolgen. Diese Effizienzsteigerung kann durch die Verwendung eines Salt abgewehrt werden. Ein Salt ist eine zufällige Zeichenkette, die bei der Hashwert-Berechnung an das Passwort angefügt wird und die mit dem Passwort-Hashwert unverschlüsselt gespeichert wird. Idealerweise verwendet jedes Passwort ein einmaliges Salt, da der Angreifer dann keinen Mehrfachvergleich gegen eine Liste von Passwort-Hashes durchführen kann, sondern für jede Vergleichsoperation die Hashfunktion mit dem jeweils einmaligen Salt neu berechnen muss.

Eine andere Angriffsmethode stellen Regenbogentabellen dar. In diesen Tabellen sind Zeichenketten mit den zugehörigen Hashwerten gespeichert. Es handelt sich dabei um einen Kompromiss des Angreifers zwischen dem Rechenaufwand und Speicherbedarf (Time-Memory Tradeoff). Gegenüber einem Brute-Force-Angriff spart die Verwendung von Regenbogentabellen teilweise Rechenaufwand, benötigt jedoch viel Speicherplatz zum Durchsuchen der vorberechneten und gespeicherten Tabellen. Für die Erstellung der Regenbogentabellen ist ein hoher Rechenaufwand erforderlich, jedoch nur einmalig, wenn die Tabellen für mehrere Angriffe wiederverwendet werden. Auch hier kann durch die Verwendung eines Salt die Angriffsmethode abgewehrt werden. Der Angreifer müsste für jeden zufälligen Salt eine eigene Regenbogentabelle vorberechnen, wodurch die Wiederverwendbarkeit und damit das Einsparpotential der Regenbogentabelle nicht mehr gegeben ist.

Anhang

Siehe auch

• Md5/Sicherheit