Was ist HashClash@home ?

Das BOINC-Projekt HashClash hat die kryptographische Hash-Funktion MD5 zum Thema und wird als Master Degree Projekt von Marc Stevens an der Technischen Universität Eindhoven betrieben.
Eine Hash-Funktion wird verwendet, um eine lange Eingabe (Quellmenge) wie z.B. einen Text in eine kurze Ausgabe (Zielmenge), den Hash-Wert des Textes, umzusetzen.
Dieses Verfahren findet sich an verschiedenen Stellen des "Alltags" wieder. Meistens wird es dazu verwendet, eine abgesendete Datei mit der, welche beim Empfänger ankommt, zu vergleichen. Hat sich ein Übertragungsfehler eingeschlichen, so stimmen die Hash-Werte der abgesendeten und der empfangenen Datei nicht überein. In der Praxis wird bei Downloads aus dem Internet des Öfteren der entsprechende Hash-Wert angegeben. Um die korrekte Übertragung der Datei zu überprüfen, muss man einfach den Hash-Wert der downgeloadeten Datei bilden und ihn mit dem im Internet angegebenen vergleichen. Stimmen die beiden Werte überein, so ist die Datei unbeschädigt beim Empfänger angekommen.

Hash-Funktionen werden des Weiteren auch verwendet, um sich gegen absichtliche Manipulationen abzusichern, womit wir bei der Kollsionsresistenz angekommen wären. Der MD5-Algorithmus, mit welchem sich das HashClash-Projekt momentan befasst, erstellt einen 128-Bit-Hashwert. Daraus folgt, dass es 2^128 mögliche Hash-Werte gibt. Dies ist zwar auf den ersten Blick eine sehr große Anzahl. Der Vergleich mit den unendlich vielen verschiedenen Nachrichten bzw. Daten, von denen man einen Hash-Wert bilden kann, zeigt jedoch, dass diese Anzahl schnell ausgeschöpft sein wird. Folglich gibt es mehrere Nachrichten mit dem gleichen Hash-Wert. Dies wird als eine Kollision zwischen den entsprechenden Nachrichten bezeichnet. Ziel einer Hash-Funktion ist es u.a., diese Kollisionen möglichst zu vermeiden (auch wenn dies logischerweise nicht gänzlich möglich ist), sprich möglichst kollisionsresistent zu sein. Die Kollisionsresistenz ist von essentieller Bedeutung, da ohne sie manipulierte Daten trotz der jeweiligen Veränderung den gleichen Hash-Wert wie die Originaldaten haben können.

Im August 2004 wurde der MD5-Algorithmus von einem chinesischen Forschungsteam unter der Leitung von Xiaoyun Wang geknackt; es wurde also eine Technik gefunden, zwei unterschiedliche Nachrichten mit dem gleichen Hash-Wert zu erstellen. Die von ihnen erfundene Technik kann aber im "Reallife" kaum verwendet werden, da die Nachrichten hierfür eine spezielle, realitätsferne Form haben müssen.
Hier setzt das Projekt HashClash an: Es sucht ebenfalls nach Kollisionen zwischen zwei Nachrichten. Diese sollen jedoch im Endeffekt flexibler zu verwenden, also nicht an spezielle Eigenschaften der Nachricht gebunden sein. Hierzu wird zunächst ein Nachrichtenblock nach dem Geburtstagsparadoxon gesucht.

Der Geburtstagsangriff stellt eine Methode dar, für eine gegebene Hash-Funktion verschiedene Dokumente mit gleichem Hash-Wert zu finden. Normalerweise würde hierzu ein naiver Brute-Force-Angriff verwendet, d.h. alle (oder jedenfalls eine große Menge der) zur Verfügung stehenden Varianten würden ausprobiert. Hierzu würden bei einem Hash-Wert von nur 40 Bit schon ca. eine Billion Versuche benötigt (zur Erinnerung: die MD5-Funktion erzeugt einen erheblich größeren Hash-Wert von 128 Bit).
Bei einem nach dem Geburtstagsparadoxon aufgebauten Missbrauchsszenario ist allerdings keiner der beiden Texte statisch, sie werden beide variiert. Dies schränkt die Anzahl der benötigten Variationen auf eine etwas größere Zahl als die Quadratwurzel der beim oben beschriebenen naiven Brute-Force-Angriff benötigten Anzahl, also etwas mehr als eine Million Versuche bei einem 40-Bit-Hash, ein.
Für einen einzelnen Intel Pentium 4 Rechner mit 3 Ghz würde der Geburtstagsangriff auf den MD5-Algorithmus jedoch im Durchschnitt immer noch 800 Stunden ununterbrochenen Betrieb bedeuten. Durch das Distributed Computing soll diese Zeit drastisch reduziert werden. Es ist geplant, später auch den SHA-1-Algorithums zu untersuchen.

Jedoch sind nicht alle bei HashClash gefundenen Kollisionen für das Projektziel relevant. Weisen die beiden Nachrichten einer gefundenen Kollision denselben Startwert auf, so sind sie für das Projekt nutzlos, da hier explizit nach Kollisionen zwischen Nachrichten mit verschiedenen Startwerten gesucht wird. Nur diese können unter der Voraussetzung, dass das Ergebnis nicht an spezielle Nachrichteneigenschaften gebunden sein soll, weiterverwendet werden. Da drei verschiedene Startwerte zum Einsatz kommen, liegt die Wahrscheinlichkeit, dass bei einer Kollision die Startwerte beider Nachrichten gleich sind, bei 1/3.

Weiterführende Informationen finden sich u.a. in den zur Erstellung dieses Textes genutzten Webseiten:
* HashClash explanation
* HashClash-Messageboard, Collision found !!
* technische universiteit eindhoven TU/e, HashClash, 20. März 2006
* Wikipedia, Hash-Funktion, 21. März 2006
* Wikipedia, Message Digest Algorithm 5, 23. März 2006
* Wikipedia, Geburtstagsangriff, 5. März 2006

(c) Hoffez2003, Team BOINC@Heidelberg, März 2006
Kontakt: Hoffez2003 (at) boinc-team (dot) de