Frage zum Verständnis der Funktionsweise von md5 und crypt

[Tom Collins]

Hallo miteinander,

dass die Ergebnisse von md5 und crypt nicht dekodiert werden können, habe ich nun begriffen. Aber warum ist das so?

md5('blafoo') ergibt zum Beispiel immer 'a47cccd7dacec4c59dc2a4c4a943d9df'
und crypt('blafoo', 'aa') immer 'aajlg71GiI1.k'.
Es scheint also das Ergebnis der Verschlüsselung eines bestimmten Strings immer gleich zu sein. Dann müsste doch die Entschlüsselung kein Problem sein.

Oder ist es so wie ich vermute, dass zum Beispiel 'a47cccd7dacec4c59dc2a4c4a943d9df' nicht nur bei 'blafoo' sondern auch bei verschiedenen anderen Strings generiert wird?

Grüße von Tom C.
(der sich mal wieder Mühe gibt, das zu verstehen, was er da macht ;-)

[Cheatah]

Hi,

Es scheint also das Ergebnis der Verschlüsselung eines bestimmten Strings immer gleich zu sein. Dann müsste doch die Entschlüsselung kein Problem sein.

die Algorithmen sind irreversibel. Das bedeutet insbesondere, dass Eingabe und Ausgabe nicht eineindeutig zueinander stehen: Nur weil eine Eingabe immer zur selben Ausgabe führt, heißt das noch lange nicht, dass eine Ausgabe immer von der selben Eingabe stammen muss. Die ursprünglichen Daten werden zwar verwendet, gehen aber dabei unwiderruflich verloren. Kurz gesagt ist die Eingabe nicht mehr in der Ausgabe enthalten.

Cheatah

[Tom Collins]

Hi Cheatah,

bitte um Mitleid für meine Begriffstutzigkeit bei einem mir vollkommen neuen Thema ;-)

Nur weil eine Eingabe immer zur selben Ausgabe führt,
heißt das noch lange nicht, dass eine Ausgabe immer von der
selben Eingabe stammen muss

Das bedeutet also, dass 'a47cccd7dacec4c59dc2a4c4a943d9df' gleich 'blafoo' sein _kann_ aber nicht sein _muss_?

Praktische Bedeutung: Wenn ich in meiner Datenbank lese, dass Benutzer XY das kodierte Passwort 'a47cccd7dacec4c59dc2a4c4a943d9df' hat, kann ich nicht sicher sagen, dass sein Passwort in "Reinschrift" 'blafoo' bedeutet.

Richtig?

Dankende Grüße
Tom C.

[Eternius]

Hallo,

ein ungefähr äquivalentes Beispiel ist die Quersumme:
Quersumme von 12345 ist 1+2+3+4+5 = (moment . . .), äh (start->ausführen->calc) 15,
die Quersumme von 54321 ist aber auch 15, die Quersumme von 13245 ist auch 15, wenn du jetzt die 15 hast, welche Ausgangszahl hattest du dann?

gruss

[Tom Collins]

Hallo Eternius,

endlich jemand, der sich auf mein Niveau begibt ;-)

Vielen Dank, das habe ich jetzt verstanden.

Grüße an alle Hilfeleistenden
Tom C.

[Eternius]

Hallo,

und nicht gleich wieder als abgehakt abheften, sondern
http://de.wikipedia.org/wiki/Surjektivität
 :)

gruss

[Sven Rautenberg]

Moin!

Das bedeutet also, dass 'a47cccd7dacec4c59dc2a4c4a943d9df' gleich 'blafoo' sein _kann_ aber nicht sein _muss_?

Es gibt kein "Gleich" in _dieser_ Richtung.

'blafoo' ergibt als MD5 'a47cccd7dacec4c59dc2a4c4a943d9df'.

Irgendein anderer String ergibt das aber ebenfalls.

Das ist mehr oder weniger identisch zu der Frage "Welche Zahl x habe ich benutzt, wenn bei Anwendung der Formel y=x^2 als Ergebnis 4 rauskommt?"

Antwort: Eindeutig kann man das nicht beantworten, es könnte 2 oder -2 gewesen sein.

Oder um es noch eindringlicher zu machen: "Von welchem Winkel habe ich den Sinus berechnet, wenn das Ergebnis 0,5 ist?" Antwort: Es ist keine eindeutige Angabe machbar, weil die Sinusfunktion für unendlich viele Winkel 0,5 ergibt - wobei diese Winkel allerdings regelmäßig verteilt sind.

MD5 hat ebenfalls solche Kollisionen, aber die sind vollkommen unregelmäßig verteilt und deshalb nicht vorhersagbar. Ebenso ist es nicht in vertretbarer Zeit möglich, ein MD5-Ergebnis wieder auf wenigstens eine mögliche Lösung zurückzurechnen, weil die Umkehrfunktionen dieser mathematischen Operation extrem langsam zu rechnen sind, während die eigentlichen Funktionen sehr schnell zu rechnen sind.

Praktische Bedeutung: Wenn ich in meiner Datenbank lese, dass Benutzer XY das kodierte Passwort 'a47cccd7dacec4c59dc2a4c4a943d9df' hat, kann ich nicht sicher sagen, dass sein Passwort in "Reinschrift" 'blafoo' bedeutet.

Richtig. Er könnte genausogut auch ein beliebiges anderes Passwort benutzt haben, welches zufällig das gleiche Ergebnis hat.

Andersherum betrachtet: Du weißt ja anfangs sowieso nicht, welches Passwort hinter dem MD5-Ergebnis steckt. Und weil du nicht bis zum Ende des Universums warten willst, bis das zurückgerechnet wurde, betrachtest du diese Wandlung eben als "unumkehrbar".

Der Versuch, alle möglichen Strings in ihr MD5-Ergebnis zu wandeln, um damit eine passende Tabelle aufzubauen, in der man dann einfach nur noch nachgucken muß, würde vermutlich am mangelnden Platz scheitern.

Und sollte MD5 doch irgendwann mal zu einfach lösbar sein, bliebe immer noch SHA1 als Ausweichalternative - da kommen nicht 2^128, sondern 2^168 (wenn ich es richtig erinnere) Möglichkeiten heraus.

- Sven Rautenberg

[Severin Kacianka]

Hallo,

dass die Ergebnisse von md5 und crypt nicht dekodiert werden können, habe ich nun begriffen. Aber warum ist das so?

Ich kenne mich mit diesen Algorithmen nicht aus, mir hat aber folgende Überlegung geholfen: Man kann aus einer iso-Datei einen md5-String erzeugen. Aus einer ~600MB großen Datei wird ein nur ein paar Byte langer String. Wenn man aus diesem String die iso-Datei "rückrechnen" könnte, hätte man einen perfekten Kompressionsalgorithmus gefunden. Man müsste einfach nur die md5-Summen übertragen und den Rest dem Rechner überlassen. Sowie man mit einem Fingerabdruck noch keinen Menschen hat. Es ist auch möglich, dass zwei unterschiedliche Dateien dieselbe md5-Summe haben. Das nennt sich "md5-Kollision" und ist der GAU für jeden Cryptograhpen ;-)

Gruß,
Severin