Wie funktioniert eigentlich MD5?

[Henryk Plötz]

Moin,

ich weiß bereits, dass MD5 eine Kodierung ist, welche nicht rückgängig gemacht werden kann. Außerdem hat eine MD5-Kodierung immer dieselbe Länge - egal wie lang der Ursprungstext ist.

MD5 ist eine Hash-Funktion.

Also ich dachte mir, dass es nur dann nicht rückgängig gemacht werden kann, wenn es mehrere Ursprünge hinter einem Code gibt, denn dann könnte kein eindeutiges Ergebnis geliefert werden.

Unter anderem, ja. Das sorgt aber nur dafür dass es nicht eindeutig umkehrbar ist und es Kollisionen gibt (zwei Eingaben die den gleichen Hash ergeben). Das ist aber gar nicht das eigentliche Problem, bzw. es ist eher ein Problem das gegen MD5 (und jede andere Hash-Funktion) spricht. Wenn es mehrere Texte gibt die die gleiche MD5-Summe haben und man nur die MD5-Summe zur Prüfung heranzieht (zum Beispiel ob ein Programm richtig übertragen wurde, oder ob das eingegebene Passwort richtig ist) ist es nicht völlig unmöglich (wenn auch unwahrscheinlich) dass die Prüfung ein positives Ergebnis ausgibt, obwohl die beiden überprüften Texte ungleich sind. Für Passwörter bedeutet dies zum Beispiel dass man gar nicht mehr das ursprüngliche Passwort finden muß, sondern dass es reicht eine Kollision mit diesem Passwort zu finden. Und die kann mit etwas Pech sogar kürzer als das ursprüngliche Passwort sein. Ok, das ist alles reichlich theoretisch da es 2^128 verschiedene MD5-Summen gibt.

Zum Problem des Rückgängigmachens: Da es reicht eine Kollision mit einem vorgegebenen Hash zu finden kann man sich eine ja eine Funktion definieren die für unsere Zwecke als Umkehrfunktion reicht[1]. Zum Beispiel indem man definiert dass sie immer die kürzeste Kollision zurückgibt. Da treten jetzt die wirklichen Probleme auf: Die MD5-Funktion ist aus der Sicht eines Mathematikers furchtbar hässlich, da ekelhaft nichtlinear. Eine Umkehrfunktion gar man gar nicht so leicht angeben.

[1] Die Sinusfunktion lässt sich ja auch nicht eindeutig umkehren, trotzdem der Arcussinus sehr nützlich.