Md5/Sicherheit

Md5/Sicherheit - 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

Links

Weblinks