m.schmidt am 4. December, 2006
Am Wochenende habe ich endlich mal Zeit gefunden, mich näher mit md5 zu beschäftigen, genauer gesagt mit den Angriffen auf diesen Algorithmus. Einer dieser Angriffe von Xiaoyun Wang beschäftigt sich mit der Berechenbarkeit von Kollisionen. Demnach benötigt man zwei Initiale Vektoren mit gleichem md5 Hash, an welche dann beliebige Daten angehängt werden können, die Hashwerte jedoch gleich bleiben. (dies ist ein inhärentes Problem Blockbasierender (Hash)verfahren: hat man einmal zwei Blöcke mit gleichem Hash, ensteht durch Konkatenation beliebiger Daten an diese Blöcke wieder ein gleicher Hash) Mathematisch ausgedrückt:
if md5(x)==md5(y) then md5(x+z)=md5(y+z)
Die initialen Vektoren unterscheiden sich in Wangs Beispiel nur um 6 Bit, hängt man jedoch mehrere solcher Blöcke aneinander, lassen sich mehrere Bytes an frei belegbaren Nutzdaten gewinnen. Eine genauere, mathematische Beschreibung würde den Rahmen dieses Artikels sprengen, deshalb sei neben dem eingangs genannten Paper noch auf die Quelle von Peter Selinger verwiesen, in welcher die Funktionsweise der Kollisionsermittlung näher erläutert wird. Hier soll ein kleines Beispiel verdeutlichen, was sich mit zwei initialen Vektoren anstellen lässt. Die beiden Dateien vec1 und vec2 besitzen den gleichen md5 Hash, sind jedoch verschieden, wie der sha1 Hash zeigt.
ftp:/md5coll# md5sum vec*; sha1sum vec*
da5c61e1edc0f18337e46418e48c1290 vec1
da5c61e1edc0f18337e46418e48c1290 vec2
8f42c29f6ac45423d2a7dd614d666a26e39f29ee vec1
dfce366c23c88044ad57a5eaa7d5420024a7fd14 vec2
Selbst das Anhängen eines zufälligen 32K Blocks ändert nichts an diesem Zustand.
ftp:/md5coll# dd if=/dev/urandom of=foo bs=32460 count=1
1+0 Datensätze ein
1+0 Datensätze aus
32460 Bytes (32 kB) kopiert, 0,044771 Sekunden, 725 kB/s
ftp:/md5coll# cat foo >> vec1
ftp:/md5coll# cat foo >> vec2
ftp:/md5coll# md5sum vec*; sha1sum vec*
64dbc8e1f2cc1855f09f37528181484b vec1
64dbc8e1f2cc1855f09f37528181484b vec2
b73dde6a98b46c53fd32fb709330dad835a9d116 vec1
e60795346ab6041ff1a315e8ca745c854ffe6ae2 vec2
Obwohl der Angriff noch nicht vollständig veröffentlicht ist (es gibt nur initiale Vektoren, theoretisch wäre es aber denkbar, Doppelgängerblöcke auch in der Mitte von zu hashenden Daten zu haben) lassen sich damit schon eine nette Anzahl Spielereien betreiben.
Zum Beispiel ein Binary, welches auf seinem Weg durch Filesharingbörsen Informationen sammelt. Kazaa hasht Dateien nicht komplett, sondern tut dies jeweils mit 32K großen Blöcken. Es ist also möglich, alle 32K ein Bit für die eigenen Zwecke zu nutzen. Bei einem 60MB großen Binary sind das demnach 1920 Bit Payload, ohne das sich der Hash ändert (würde er dies tun, so würde das Binary x-mal in den Filesharingbörsen auftauchen, was ziemlich auffällig ist). Nun braucht das Binary nicht mehr „nach Hause telefonieren“, man kann es sich von Zeit zu Zeit aus den Filesharingbörsen ziehen und den Payload auswerten. (zu sammelnde Daten wären etwa MAC Adressen, Rechnernamen, email Daten u.s.w.)
Auch Security Audit Tools, welche die md5 Summen von Dateien auf der Platte überwachen, bekommen davon nichts mit. Peter Selinger hält auf seiner Seite ein nettes Tool bereit, mit dem sich Paare von ausführbaren Dateien erzeugen lassen, welche den gleichen md5 Hash besitzen, sich aber unterschiedlich verhalten.
Da mein PC noch an einem eigenen Beispiel rechnet verwende ich die vorbereiteten Dateien.
mschmidt@ftp:~$ md5sum erase; md5sum hello; sha1sum erase; sha1sum hello
da5c61e1edc0f18337e46418e48c1290 erase
da5c61e1edc0f18337e46418e48c1290 hello
dfce366c23c88044ad57a5eaa7d5420024a7fd14 erase
8f42c29f6ac45423d2a7dd614d666a26e39f29ee hello
mschmidt@ftp:~$ ./erase This program is evil!!!
Erasing hard drive…1Gb…2Gb… just kidding! Nothing was erased.
(press enter to quit)
mschmidt@ftp:~$ ./hello
Hello, world! (press enter to quit)
Irgendwie beängstigend, das
if md5(binA)==md5(binB)thenbehaviour(binA)==behaviour(binB)
nicht mehr wirklich gillt.
Nun, ist md5 damit am Ende? Sicher nicht, denn die Einsatzszenarien der (bisher veröffentlichten) Angriffe sind doch noch sehr begrenzt. (Der genaue Algorithus zur Kollisionsfindung, und dessen Möglichkeiten, sind noch nicht vollständig bekannt) Es sollte jedoch klar sein, das zumindest der Anfang des Endes von md5 begonnen hat, und ein Umstieg auf Alternativen (sha1) nicht früh genug erfolgen kann.
Wer tiefer gehendes Interesse an der Materie hat, dem sei darüber hinaus dieses Buch ans Herz gelegt, besonders die Kapitel 3 und 11 zeigen die Möglichkeiten und Gefahren der md5 Kollision
Update
Security, Adventskalender | Kein Kommentar »
Tags: md5, hack, security, hash, algorithm
Das 14te Türchen – default Passwörter
