MD5 - Hash eundeutig?

Computer: Software & Programmierung Programmierung allgemein
#1

Der Message Digest 5 (MD5) Algorithmus erzeugt zu einem beliebigen Eingabestrom einen Hash-Wert. Der Hash-Wert des MD6 hat die Eigenschaft nicht vorher sagbar zu sein, d.h. es ist praktisch kaum möglich, einen Eingabestrom so zu definieren, dass ein gewünschter Hash-Wert entsteht.

Dieses Verhalten und die genaue Implementierung ist im RFC1321 beschrieben. Meine Frage ist nun folgende:

1.) Können unterschiedliche Eingabedaten den gleichen Hash zur Folge haben?
=> da der hash nur 128Bit breit ist, sollte das theoretisch möglich sein.

2.) Wie sieht es mit der Eindeutigkeit aus, wenn der Eingabestrom

#2

Moin

1.) Können unterschiedliche Eingabedaten den gleichen Hash zur
Folge haben?

ja. (wie bei allen hashs)

2.) Wie sieht es mit der Eindeutigkeit aus, wenn der
Eingabestrom

#3

Hash-Eindeutigkeit unmöglich!
Hallo,

1.) Können unterschiedliche Eingabedaten den gleichen Hash zur
Folge haben?
=> da der hash nur 128Bit breit ist, sollte das theoretisch
möglich sein.

Du wirst es nicht glauben, aber spätestens mit der (2128+1)-ten Anwendung des Algorithmus’ muß mindestens ein Hashwert mindestens doppelt vorgekommen sein :wink:. Tip zum besseren Verständnis: Stell Dir vor, Du hast einen Algorithmus, der einen nur 4-bittigen Hashwert erzeugt, und anschließend läßt Du Dir dann von diesem die Hashes von 17 Eingabedateien berechnen.

Gruß
Martin

#4

1.) Können unterschiedliche Eingabedaten den gleichen Hash zur
Folge haben?
=> da der hash nur 128Bit breit ist, sollte das theoretisch
möglich sein.

Du wirst es nicht glauben, aber spätestens mit der
(2128+1)-ten Anwendung des Algorithmus’ muß
mindestens ein Hashwert mindestens doppelt vorgekommen sein
:wink:.

nach langem ueberlegen, glaube ich jetzt den smily interpretiern zu können.
aber ich denke dein beispiel mit 2^4 ist irreführend, da das schoene an potenzen die unglaubliche potenz ist:

2^128+1 sind:
340282366920938463463374607431768211457
sagt zumindest mein bc.

ich kann mir keine applikation vorstellen, innerhalb der ich diese menge ausschöpfen kann.
schliesslich muesste ich 2^128+1 zeichenfolgen bilden, auf die ich die md5 anwenden koennte.
ich bin mir ziemlich sicher, dass, rein unter der betrachtung der anzahl der duplikate, selbst google md5 in irgendeiner form fuer ihren index nutzen koennte.

es stellen sich also eigentlich die fragen:

  • wie hoch ist die wahrscheinlichkeit, dass 2 strings innerhalb einer praktischen menge (vielleicht: 10.000.000?)die gleiche md5-summe bilden? und:
  • gibt es einen implementierungsfehler, der dafuer sorgt, dass der fehler: 2 strings bilden die gleiche md5-summe, expotential ansteigt?
  • steigt oder faellt meine fehlerwahrscheinichkeit signifikant, wenn ich den md5-of-md5 speichere?
  • bin ich genauso lame, weil ich md5 anstatt sha-1 nutze [1], wie ich wäre, wenn ich telnet statt ssh nutzte?

[1] MD5 wird seit der Veröffentlichung eines theoretischen Angriffsszenarios als nicht mehr sicher erachtet. Stattdessen wird empfohlen, den SHA-1-Algorithmus zu benutzen. (http://de.wikipedia.org/wiki/MD5)

#5

schoene an potenzen die unglaubliche potenz ist:

2^128+1 sind:
340282366920938463463374607431768211457
sagt zumindest mein bc.

Wenn du z.B. Texte verschlüsselst mit z.B. 1000 Buchstaben, dann
ergibt das 26^1000 versiedene Möglichkeiten, und sind natürlich
mehr als 2^128, aber die Wahscheinlichkeit, daß 2 SINNVOLLE Texte
gleiche Hashes haben, ist sehr gering. Bei binären Datenströmen
mit z.B. 500 Bytes gibt es z.B. 256^500 = 2^4000 Möglichkeiten -
also ungefähr genauso viele. Aber bei binären Datenströmen kommen
halt alle Möglichkeiten in Betracht, und damit ist die
Wahrscheinlichkeit höher.
Bei Exe-Binaries kommen nur die ausführbaren Möglichkleiten in Betracht,
und deshalb ist die Wahrscheinlichkeit wieder geringer, daß 2 den
gleichen Hash haben.

Falls die Eingabe weniger als 128 Bit hat, kann es glaube ich trotzdem
2 verschiedene Eingaben mit gleichem Hash geben. Da müßte der MD5 schon
ein optimaler Hasher sein.

In der Praxis sollte es aber wohl nicht vorkommen, daß zwei verschiedene
„Pakete“ den gleichen Hash haben.
Außerdem werden Hashes meistens verwendet, um ähnliche(!) „Pakete“
voneinenander zu unterscheiden, und in diesem Fall können eigentlich
keine 2 gleichen Hashes entstehen, da der MD5 schon bei der kleinsten
Änderung stark streut.
2 „Pakete“ mit gleichem Hash sind grundverschieden.

Gruß
Thorsten