Was ist der Grund, warum man aus einem MD5-Hash die ursprüngliche Nachricht nicht zurückrechnen kann?


Moderiert von Christian S.: Topic aus Sonstiges (Delphi) verschoben am Do 24.05.2007 um 10:44

Weil es nunmal ein Hash ist. Der Hash berechnet einen Wert, der einen String eindeutig bestimmen soll. Hierzu schmeißt er aber Infos, die in dem String drin stehen weg, um zu einer festen Hash-Länge zu kommen. Und diese können nicht wieder hergezaubert werden. Ich weiß jetzt nicht genau, wie im speziellen MD5 funktioniert, Wikipedia sollte aber helfen.
Überleg mal was das für eine Komprimierung wäre, wenn ich beliebig größe Strings/Dateien immer in einen sehr kleinen Hash packen könnte und danach wieder zurückrechnen könnte... Das wär ja phänomenal Dann bräuchte kein Mensch mehr eine 16 MBit Internetleitung, weil ja sowieso alles mit den (kleinen) Hashs versendet wird, die dein Rechner dann wieder zurückrechnet....



MrSaint

Hashing ist mathematisch eine eindeutige aner nicht eineindeutige Abbildungsfunktion. D.H beim hashen des selben Code entsteht immer der selbe Hash. Aber es gibt unendlich viele Strings welche den delben Hash erzeugen.

Wenn Dir das nicht reicht, dann schau mal hier:
de.wikipedia.org/wiki/Hash

Zur Verdeutlichung:
Wenn ich mir eine Zahl denke, und dir dann sage sie ist durch 3 teilbar, jedoch nicht durch 2 (hier der Hash), dann kannst du auch nicht "zurückrechnen", welche Zahl ich mir gedacht habe, da es unendlich viele Zahlen gibt, mit der Eigenschaft "durch 3 teilbar, durch 2 nicht teilbar".
Wenn ich jedoch den möglichen Bereich eingrenze, sagen wir ich habe mir eine Zahl von 1 bis 10 gedacht, dann wäre hier der Hash eindeutig, da es nur eine einzige Möglichkeit gibt, nämlich die Zahl 9.

Chryzler hat folgendes geschrieben:

Zur Verdeutlichung: Wenn ich mir eine Zahl denke, und dir dann sage sie ist durch 3 teilbar, jedoch nicht durch 2 (hier der Hash), dann kannst du auch nicht "zurückrechnen", welche Zahl ich mir gedacht habe, da es unendlich viele Zahlen gibt, mit der Eigenschaft "durch 3 teilbar, durch 2 nicht teilbar". Wenn ich jedoch den möglichen Bereich eingrenze, sagen wir ich habe mir eine Zahl von 1 bis 10 gedacht, dann wäre hier der Hash eindeutig, da es nur eine einzige Möglichkeit gibt, nämlich die Zahl 9.

Womit übrigens eindrucksvoll bewiesen ist, dass man so keine Kompression machen kann.
Um die Information '3' zü übertragen, brauchen der Hash schon 2 Byte. Die Information, die dann das Zurückrechnen ermöglicht, nämlich '1 bis 10', benötigt nochmal 2 Byte, womit der Speicherbedarf größer ist.

Martok hat folgendes geschrieben:

Womit übrigens eindrucksvoll bewiesen ist, dass man so keine Kompression machen kann.

Kann man eindrucksvoller beweisen:
Trinke ein Bier, warte ein bisschen und pinkel vor versammelter Meute in das leere Bierglas.
Wer jetzt aus dem Inhalt des Glases wieder das Bier 'zurückrechnen' kann, kann wahrscheinlich sogar einen MD5 Hash zurückzaubern.

Robert_G hat folgendes geschrieben:

Wer jetzt aus dem Inhalt des Glases wieder das Bier 'zurückrechnen' kann, kann wahrscheinlich sogar einen MD5 Hash zurückzaubern.

Kölsch-Brauer können einen MD5 Hash zurückzaubern?

Ach, nein, denen gelingt das Zurückrechnen des Bieres ja auch nicht ...

mkinzler hat folgendes geschrieben:

Aber es gibt unendlich viele Strings welche den delben Hash erzeugen.

Wieso speichert man dann Passwörter als Hash?
Ist das nicht unsicherer als würde man das Passwort selbst speichern?

Coder hat folgendes geschrieben:

Wieso speichert man dann Passwörter als Hash?

Damit, falls jemand unbefugt Zugang zur Datenbank erhält, derjenige die Passwörter nicht kennt. Oder auch befugt (wie z.B. ich beim DF): Es gibt sicherlich viele Nutzer, die dasselbe Passwort fürs DF und andere Seiten benutzen. Die würde ich dann alle kennen. Da nur der Hash gespeichert wird, nicht.

Und was die Sicherheit angeht: Es gibt zwar Millionen Strings, die den gleichen Hash erzeugen. Aber noch viel mehr, die das nicht tun Eine solche "Kollision" zu finden, ist ein sehr großer Aufwand.

Hier mal etwas genauere Zahlen zum Erkennen der Größenordnung:

Bei MD5 (128-Bit-Hash) gibt es 2^128 verschiedene Hash-Ergebnisse. Das sind etwa
340282366921000000000000000000000000000 verschiedene Hash-Werte.
Damit sollte es relativ schwierig werden, zu einem Hash-Wert den ursprünglichen String (oder einen mit dem gleichen Hash) zu finden.

Allerdings muss man der Wahrheit zuliebe sagen, dass genau dies einigen chinesischen Wissenschaftlern gelungen ist (siehe z. B. Wikipedia-Artikel).

ub60

Coder hat folgendes geschrieben:

mkinzler hat folgendes geschrieben: Aber es gibt unendlich viele Strings welche den delben Hash erzeugen. Wieso speichert man dann Passwörter als Hash? Ist das nicht unsicherer als würde man das Passwort selbst speichern?

Nein.

Wenn Du das Passwort speicherst, dann kann man es wieder auslesen. Bei einem guten Hash ist es so, das Du sehr viele Passwörter durchprobieren musst, um einen identischen Hashwert zu erhalten. Ganz sicher ist so etwas natürlich nicht, aber was ist schon sicher?

stell dirs vor wie ne quersumme:

348 hat die quersumme 15
aber die zahl 726 hat auch die quersumme 15

man kommt von der zahl aber die quersumme aber nicht zurück.

Hi

... und genau da ist ja auch die Schwachstelle der Hash-Speicherung: Es reicht aus, irgend eine Orignalnachricht zu ermitteln, die auf den gleichen Hash abgebildet wird.

Wenn Du nun die Quersumme als Hashfunktion nimmst, dann kann man zwar genausowenig das Original rückberechnen, aber da man einen beliebigen anderen Wert mit der gleichen Quersumme berechnen kann, kann man diese Sicherheitshürde trotzdem überwinden.

Ziel ist es also, eine Hashfunktion zu entwickeln, für die es keine Umkehrfunktion gibt (Trapdoor-Funktion). Dann muss man nämlich probieren, und das dauert.

Kleine Anmerkung vorweg: Für MD5 gibt es inzwischen eine Möglichkeit für einen bekannten Klartext einen weiteren anzugeben, der genau den gleichen Hashwert erzeugt. Problem an MD5 ist seine Symmetrie ... Siehe hier

Witzig ist es aber, wenn man mehrere Hash-Werte concateniert und diese mit einem weiteren (sicheren) Verfahren hasht ... So steigert man zwar nicht unbedingt die Sicherheit, aber ein SHA256-Hasch mit CRC32-Suffix, der wie MD5 aussieht, bringt fast jeden zur Verzweiflung ...

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

alzaimar hat folgendes geschrieben:

Ziel ist es also, eine Hashfunktion zu entwickeln, für die es keine Umkehrfunktion gibt (Trapdoor-Funktion). Dann muss man nämlich probieren, und das dauert.

Eine Trapdoor-Funktion ist eine Umkerfunktion, die das Umkehren einer eigentlichen Einweg-Funktion nur durch eine Zusatzinformation möglich macht. Es stimmt aber, dass eine Hash-Funktion gefunden werden muss, zu der es keine Umkehrfunktion gibt, alles andere macht Kryptografisch keinen Sinn!

Das Zurückrechnen von MD5 ist nicht möglich, weil eine Modulo-Funktion verwendet wird. Von allen 512Bit-Blöcken des Strings werden vier 32Bit-Blöcke erzeugt die zu den vier 32Bit-Ausgabeblöcken addiert werden. Da 32Bit-Blöcke in der länge begrenzt sind, wird die Modulofunktion zum "kürzen" verwendet.