Wie funktioniert eigentlich MD5?

[S.Goertz]

Hallo,

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.
Für mich klingt da so einiges mathematisch unlogisch (bzw. ich weiß nicht, ob die Möglichkeiten, die ich mir gedacht habe, tatsächlich richtig sind).

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. Das würde auch erklären, wie ein langer Text sowie ein kurzer problemlos in einen einheitlich langen Code passen, so kommt es zu garantierten dopplungen.
Außerdem erklärte ich mir selber, dass lange Eingaben gekürzt und kurze Eingaben verlängert werden, sodass es wieder zu einer korrekten Codierung in die einheitliche Länge kommt. Das ganze sind allerdings nur Überlegungen von mir. Stimmt das wenigstens in etwa so? Wenn nicht würde ich mich sehr über die korrekte Version freuen. Google brachte mir nur ein technisches Wirrwarr, welches ich absolut nicht verstand...

Gruß,
  S.Goertz

[Harry]

Holladiewaldfee,

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.
Für mich klingt da so einiges mathematisch unlogisch (bzw. ich weiß nicht, ob die Möglichkeiten, die ich mir gedacht habe, tatsächlich richtig sind).

http://aktuell.de.selfhtml.org/artikel/javascript/md5/index.htm

Hier ist der komplette MD5-Algorithmus in JavaScript. Vielleicht hilft Dir das ja etwas.

Ciao,

Harry

[Christian Seiler]

Hallo,

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.

Jain.Wenn Du eine normale mathematische Verknüpfung hast, dann kann diese im Normalfall rückgängig gemacht werden. Wenn diese Verknüfpung dann z.B. lautet "die Zahl hoch zwei", dann weißt Du, dass Du die Quadratwurzel zeihen musst. Dies ist bei sehr vielen mathematischen Verknüpfungen der Fall.

Nun stelle Dir jedoch vor, dass Du die Verknüpfung nicht über den normalen unendlichen Zahlenraum durchführst, sondern über einen endlichen Zahlenraum einer Uhr. Stelle Dir also vor, Du hättest eine normale analoge Uhr vor Dir, bei der die 12 durch 0 ausgetauscht wäre. Wenn Du nun 4+5 rechnest, dann ist es ganz klar, dass Du bei 9 rauskommst. Du gehst von der 0 aus 4 Schritte im Uhrzeigersinn und dann 5 Schritte weiter. Dann kommst Du bei der 9 raus. Wenn Du dagegen 9 + 6 rechnest, kommt 3 heraus. Dies sollte klar sein, Du gehst von der 9 aus 6 Schritte im Uhrzeigersinn. Dann kommst Du bei der 3 an. Du bekommst die 3 rechnerisch heraus, indem Du (9 + 6) mod 12 rechnest.

Wenn Du nun eine Verknüpfung wie 23^x hast, dann dürfte in einem Uhrensystem mit Ziffern von 0 bis 16 es ziemlich schwierig sein, das ganze wieder umzukehren. Bei bei der Zahl 7 wäre das Ergebins (23^7) mod 17 = 14. Wenn Du nun den Wert 14 hast, dann kannst Du keine 7. Wurzel daraus ziehen, um auf den ursprünglichen zurückzukommen. Die einzige Möglichkeit wäre durchprobieren:

(23^1) mod 17 = 6
(23^2) mod 17 = 2
(23^3) mod 17 = 12
(23^4) mod 17 = 4
(23^5) mod 17 = 7
(23^6) mod 17 = 8
(23^7) mod 17 = 14

Aha, wir haben ihn also gefunden. Aber: Der Wertebereich, den wir hier gewählt haben, war sehr klein. Nur 17 verschiedene Möglichkeiten für ein Ergebnis. Ein MD5-Hash ist 16 Bytes = 128 Bit lang. Damit stehen 340.282.366.920.938.463.463.374.607.431.768.211.456 verschiedene Möglichkeiten für eine MD5-Zeichenkette zur Verfügung. Daher dürfte das durchprobieren sichtlich schwer fallen.

Ich sollte vielleicht noch erwähnen, dass ich keine Ahnung habe, wie der MD5-Algorithmus genau funktioniert. Ich weiß nur, dass es eine nichtumkehrbare Funktion ist. Die Uhrenarithmetik hier war nur ein Beispiel für das mögliche Funktionieren einer solchen Funktion. Es gibt vermutlich noch andere Wege, nichtumkehrbare Funktionen zu erstellen.

Das würde auch erklären, wie ein langer Text sowie ein kurzer problemlos in einen einheitlich langen Code passen, so kommt es zu garantierten dopplungen.

Es gibt bei MD5 auch Doppelungen, das kann man mathematisch Nachweisen. Allerdings ist bisher noch kein einziger Mensch auf eine gestoßen.

Außerdem erklärte ich mir selber, dass lange Eingaben gekürzt und kurze Eingaben verlängert werden, sodass es wieder zu einer korrekten Codierung in die einheitliche Länge kommt.

Nein. Ich weiß zwar nicht, wie der Algorithmus genau funktioniert, aber eines weiß ich: Wenn Du in einer 2GB großen Datei ein einziges Bit an welcher Stelle auch immer veränderst, ändert sich auch der entsprechende MD5-Wert.

Google brachte mir nur ein technisches Wirrwarr, welches ich absolut nicht verstand...

Ich hoffe, meine Erklärung ist verständlicher.

Viele Grüße,
Christian

[Henryk Plötz]

Moin,

Wenn Du nun eine Verknüpfung wie 23^x hast, dann dürfte in einem Uhrensystem mit Ziffern von 0 bis 16 es ziemlich schwierig sein, das ganze wieder umzukehren. Bei bei der Zahl 7 wäre das Ergebins (23^7) mod 17 = 14. Wenn Du nun den Wert 14 hast, dann kannst Du keine 7. Wurzel daraus ziehen, um auf den ursprünglichen zurückzukommen. Die einzige Möglichkeit wäre durchprobieren:

Die Umkehrfunktion heisst diskreter Logarithmus und durchprobieren (wiederholte Multiplikation reicht) ist tatsächlich die naheliegenste Möglichkeit. Es gibt aber unter gewissen Umständen Algorithmen die das schneller können (zum Beispiel Shanks Algorithmus, oder Pohlig-Hellman).

[Christoph Zurnieden]

Hi,

Wenn Du nun eine Verknüpfung wie 23^x hast, dann dürfte in einem Uhrensystem mit Ziffern von 0 bis 16 es ziemlich schwierig sein, das ganze wieder umzukehren. Bei bei der Zahl 7 wäre das Ergebins (23^7) mod 17 = 14. Wenn Du nun den Wert 14 hast, dann kannst Du keine 7. Wurzel daraus ziehen, um auf den ursprünglichen zurückzukommen. Die einzige Möglichkeit wäre durchprobieren:

Die Umkehrfunktion heisst diskreter Logarithmus und durchprobieren (wiederholte Multiplikation reicht) ist tatsächlich die naheliegenste Möglichkeit. Es gibt aber unter gewissen Umständen Algorithmen die das schneller können (zum Beispiel Shanks Algorithmus, oder Pohlig-Hellman).

Es gab letzthin wieder eine "Möglichkeit" ( um den Begriff "Lösbarkeit" zu vermeiden) für MD5 von berühmter Stelle. Habe aber aus Zeitgründen mal wieder nix mitbekommen, weißt Du evt Näheres?
Vieleicht sogar Links zur Hand?

so short

Christoph Zurnieden

[Henryk Plötz]

Moin,

Es gab letzthin wieder eine "Möglichkeit" ( um den Begriff "Lösbarkeit" zu vermeiden) für MD5 von berühmter Stelle. Habe aber aus Zeitgründen mal wieder nix mitbekommen, weißt Du evt Näheres?

Nein, aber bei der Recherche für mein Posting eben bin ich darauf gestoßen dass man für MD5 Kollisionen für die Kompressionsfunktion berechnen kann und dass die erste Runde von MD5 mit differentieller Kryptanalyse geknackt (um mal ein Publikumswirksames Wort zu verwenden ;-) ist.

Vieleicht sogar Links zur Hand?

http://www.stack.nl/~galactus/remailers/attack-3.html Allgemeineres zu den Brechungsmöglichkeiten
ftp://ftp.rsa.com/pub/pdfs/bulletn4.pdf Beschreibung von MD2, MD4 und MD5 und dem Status dieser Funktionen

Die Dokumente sind aber schon ein bisschen älter.

[Christoph Zurnieden]

Hi Henryk,

Es gab letzthin wieder eine "Möglichkeit" ( um den Begriff "Lösbarkeit" zu vermeiden) für MD5 von berühmter Stelle. Habe aber aus Zeitgründen mal wieder nix mitbekommen, weißt Du evt Näheres?

Nein, aber bei der Recherche für mein Posting eben bin ich darauf gestoßen dass man für MD5 Kollisionen für die Kompressionsfunktion berechnen kann und dass die erste Runde von MD5 mit differentieller Kryptanalyse geknackt (um mal ein Publikumswirksames Wort zu verwenden ;-) ist.

Naja, "geknackt" ... ;-)

Vieleicht sogar Links zur Hand?

http://www.stack.nl/~galactus/remailers/attack-3.html Allgemeineres zu den Brechungsmöglichkeiten
ftp://ftp.rsa.com/pub/pdfs/bulletn4.pdf Beschreibung von MD2, MD4 und MD5 und dem Status dieser Funktionen

Die Dokumente sind aber schon ein bisschen älter.

Und schon bekannt, leider.
Aber irgendjemand hat letzthin wirklich einmal ein weiteres [sic!] "Loch" in MD5 gefunden.
Da ich annehme, das sowas evt interessiert, werde ich mal suchen gehen.

Aber trotzdem und auf jeden Fall: besten Dank für die Mühe!

so short

Christoph Zurnieden

[S.Goertz]

Hallo,

Ich hoffe, meine Erklärung ist verständlicher.

Ja, die war echt gut. Ich habe glaub ich alles verstanden. Auf die Idee mit einem endlichen Zahlensystem war ich gar nicht gekommen.

Gruß,
  S.Goertz

[Christian Seiler]

Hallo,

Auf die Idee mit einem endlichen Zahlensystem war ich gar nicht gekommen.

Erstens muss ich dazu sagen, dass ich nicht weiß, ob der MD5-Algorithmus auch mit so etwas arbeitet. Zweitens wäre ich auch nicht von alleine darauf gekommen. ;-)

Viele Grüße,
Christian

[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.