MD5 Attack (beendet)

MD5 Attack war ein 2003 betriebenes Project von The NEO Project. Es ging um einen Angriff auf den MD5-Algorithmus.

Man unterscheidet prinzipiell 3 Typen von kryptographischen Algorithmen:

• Typ-2: Asymetrische Algorithmen (Public-Key-Algorithmen): Hier werden für Verschlüsselung und Entschlüsselung zwei verschiedene Schlüssel benutzt, die auch nur für jeweils eine der beiden Operationen gültig sind.
• Typ-1: Symetrische Algorithmen: Diese Algorithmen nutzen nur einen Schlüssel, mit dem man sowohl verschlüsseln als auch entschlüsseln kann.
• Typ-0: Hash-Algorithmen: Diese Algorithmen benutzen überhaupt keine Schlüssel. Stattdessen wird ein kurzer Hash (vergleichbar mit einer guten Seriennummer) berechnet und dieser Hash benutzt, um die Authentizität von verschlüsselten Nachrichten zu bestätigen.

Dieses Projekt greift den MD5-Algorithmus an. Dabei handelt es sich um einen Typ-0-Algorithmus mit 128 Bit Schlüssellänge.

Die Idee des Angriffs ist folgende:

• Insgesamt gibt es bei dieser Schlüssellänge genau 2¹²⁸ mögliche MD5-Hashes.
• Wenn man wiederholt zufällige Zahlen aus einem begrenzten Zahlenbereich 1 bis n auswählt, dann braucht man lediglich Quadratwurzel(n) Versuche, bis man mit hoher Wahrscheinlichkeit zwei gleiche Zahlen gefunden hat. Dieses Phänomen ist auch als Geburtstags-Paradoxon bekannt.
• Die Anzahl benötigter MD5-Hashes für eine wahrscheinliche Kollision beträgt somit etwa 2,16 * 10¹⁹.
• Da eine so große Anzahl Hashes nicht gespeichert werden kann, werden nur ganz spezielle Hashes ausgewählt (diese heißen Distinguished Points, kurz DP), bei denen die niedrigsten 32 Bit alle den Wert Null haben. Somit wird nur etwa jeder 4-billionste Hash gespeichert und zum zentralen Projektserver gemeldet. Diese Auswahltechnik wird Pollard's-Rho-Algorithmus genannt.
• Sofern zwei verschiedene Clients einmal einen gleichen Hash berechnet haben (obwohl sie mit verschiedenen Werten gestartet wurden), dann werden sie von diesem Punkt aus immer gleiche Hashes berechnen, da das Ergebnis jeder Berechnung als Eingabe für die nächste Berechnung im Client dient. Somit wird auch der nächste DP bei diesen beiden Clients gleich sein.
• Der zentrale Server prüft einmal täglich, ob unter allen gemeldeten DPs ein Paar gleicher Punkte ist. Wenn dies der Fall ist, war der Angriff erfolgreich und das Projektziel wurde erreicht.

Unter www.certainkey.com/dnet/ findet man eine Herleitung der Sicherheit des Verfahrens und die Kosten eines Angriffs. Die genaue Vorgehensweise innerhalb des NEO-Clients beschreibt die Webseite jlcooke.ca/neo/aboutmd5/.

Projektübersicht

MD5 Attack
Name	MD5 Attack
Kategorie	Kryptographie
Ziel	Knacken einer MD5-Verschlüsselung
Kommerziell	nein
Homepage	offline, hier Archive.org Link

Es ist uns leider nicht bekannt, wo auf der Welt dieses Projekt zu Hause ist.

Projektstatus

Projektstatus
Status	beendet
Beginn	30.01.2003
Ende	19.05.2003

Projektlinks

• Hintergrundinfos

	(nicht mehr aktiv)
Anmelden	sourceforge.net/project/showfiles.php?group_id=70840
FAQ	www.theneoproject.com/faqs.html
Statistiken	www.theneoproject.com/STATS/MD5MAIN.HTM
Mailingliste/Forum	www.theneoproject.com/wbboard/board.php?boardid=32
Support	www.theneoproject.com/wbboard/main.php

Clientprogramm

Betriebssysteme

	Windows
	Linux
	DOS
	BSD
	Solaris
	Java (betriebssystemunabhängig)

Client-Eigenschaften

Funktioniert auch über Proxy
Normal ausführbares Programm
Als Bildschirmschoner benutzbar
Kommandozeilenversion verfügbar
Personal Proxy für Work units erhältlich
Work units auch per Mail austauschbar
Quellcode verfügbar
Auch offline nutzbar
Checkpoints

Besonderheiten des Clients

• Der Client ist inklusive Quellcode auf Sourceforge.net als Open-Source-Projekt verfügbar.
• Der Client legt detaillierte XML-Dateien im Programmverzeichnis an, die den Fortschritt sowie alle berechneten Ergebnisse dokumentieren.

Veröffentlichte Versionen

• 22.02.2003: 1.0.750d

• 30.11.1999: alpha

Screenshots

• 

  Benutzereinstellung - Beim ersten Start fragt der Client nach den nötigen Angaben, um die Ergebnisse zu personalisieren.

• 

  Auswahl einer karitativen Einrichtung, NEO will sämtliche Preise, die durch Projekte errungen werden, karitativen Einrichtungen zur Verfügung stellen. Hier kann man abstimmen, welche Einrichtung das sein soll.

• 

  Auswahl der CPU, Abhängig von der Auswahl des eigenen CPU-Types lädt der NEO-Client einen Kernel aus dem Netz, der optimal für diese CPU geeignet ist.

• 

  Berechnungen, Nach Eingabe aller Daten startet die Berechnung. Der Client gibt keine Fortschrittsanzeige aus.