MD5 für Textnachrichten: wie fälschbar?

[lf_dy_laglc]

Hallo.

Wie gut kann man heute MD5-gesicherte Textnachrichten fälschen?

D.h. "unbequeme" Passagen ersetzten, z.B. in einem (erfundenen) Schuldschein (siehe unten).

- Zwei mögliche Fälscher gibts

a) "Huber Georg" will die Schulden nicht zahlen, d.h. sein Name wird ersetzt oder die Art/Anzahl der Tiere

"Maier Sepp" weiss dass der Huber Georg nicht zahlen kann und hätte gern einen anderen Schuldner oder andere Tiere.

Die komplette Nachricht ersetzen z.B. durch "In München regnets" sei nicht erlaubt.

Gibts da schon Werkzeuge dafür?

Wikipedia sagt "Bereits 1994 entdeckten Bert den Boer und Antoon Bosselaers Pseudo-Kollisionen in MD5"

Ciao

C:\temp>echo "der Huber Georg schuldet dem Maier Sepp 5555 Wolpertinger" >orig.txt

C:\temp>md5sum orig.txt

30eee946f610d3b40ebbf52134968362 *orig.txt

[Cadpax]

Bei den Kollisionen ist es letztendlich ja so, dass ein Hash für verschiedene Texte gleich ust. Ich persönlich, nachdem ich mich eben kurz rein gelesen habe, was die Forscher da fabriziert haben, [1], [2], [3], halte ich es persönlich für unbedenklich, dass oben genannter Fall so eintreten dürfte, da ich die Methoden, im Moment, eher für reine Willkür betrachte, als eine wirkliche Gefahr.

Ein Eingabeblock (512 Bit) wird modifiziert, wobei versucht wird, eine bestimmte Differenz zum Original im Ausgang zu erzeugen. Durch eine aufwändige Analyse des Algorithmus kann die Anzahl der unbekannten Bits so weit verringert werden, dass dies rechnerisch gelingt. Im nächsten 512-Bit-Block wird mit den gleichen Methoden versucht, die Differenz wieder aufzuheben. Die Fälschung beschränkt sich also auf einen zusammenhängenden Datenblock von 1.024 Bit = 128 Byte, was den "Einsatz" stark einschränkt.

Ich denke, dass eine solch erhebliche Änderung sich nicht einfach so wegmachen lässt.

Lass mich allerdings gerne vom Gegenteil überzeugen.

[lordy]

Man muß hier zwei wesentliche Faktoren unterscheiden:

Zum einen der "einfache" Kollisions-Angriff (Kollisionsangriff - Wikipedia), sprich, das Erzeugen einer beliebigen Nachricht, die die selbe Prüfsumme aufweißt, wie das Original. Das ist im Laufe der letzten Jahre durch diverse Untersuchungen der Algorithmen sicherlich einfacher geworden, aber immernoch eine Herausforderung.

Das zweite ist ein sogenannter Preimage-Angriff (Preimage-Angriff - Wikipedia), bei dem versucht wird, nicht irgendeine Kollision zu erzeugen, sondern eine, die dem Originaltext möglichst ähnlich ist. Der Aufwand für diese ist exponentiell zu der einer Kollision, daher würde ich Preimage-Angriffe gegen aktuelle Hash-Algorithmen (MD5, SHA, etc.) als unmöglich einstufen.

[lf_dy_laglc]

Das zweite ist ein sogenannter Preimage-Angriff (Preimage-Angriff - Wikipedia), bei dem versucht wird, nicht irgendeine Kollision zu erzeugen, sondern eine, die dem Originaltext möglichst ähnlich ist. Der Aufwand für diese ist exponentiell zu der einer Kollision, daher würde ich Preimage-Angriffe gegen aktuelle Hash-Algorithmen (MD5, SHA, etc.) als unmöglich einstufen.

Lordy ist doch der Beste :e@sy:uli

Nun:

Wie siehts aus mit MD4 oder MD2? Gibt da schon fertige Programme, am besten mit Quelltext, die ein Preimage zu meinem obigen String erzeugen können.

Noch besser, wenn das auf einem handelsüblichen Pentium 4 in, sagen wir, unter einer Woche, durchläuft.

[lordy]

Ich bin kein Mathematiker, aber da auch MD2 und MD4 128-bit lange Prüfsummen bilden und ich noch nichts über Angriffe gegen diese Algorithmen gelesen habe, glaube ich nicht, das du ein derartiges Programm finden wirst. Von deiner gewünschten Laufzeit mal ganz abgesehen

[lf_dy_laglc]

glaube ich nicht, das du ein derartiges Programm finden wirst.

Oooooch, nichtmal für MD4? schaaaaade

Trotzdem danke Lordy :e@sy

[.vash]

ich würde die Frage etwas anders angehen: Bei reinem Text dürfte eine Manipulation schwer durchzuführen sein.

In einer Word oder HTML-Datei wo sich beliebige Zeichenfolgen eingeben lassen die nicht angezeigt werden (HTML Kommentar, unsichtbarer Text) ließe sich sowas theoretisch sicher eher bewerkstelligen.

Allerdings denke ich auch nicht dass es da ein fertiges Programm zum Download geben wird dass mir das erledigt. Soviel wie ich bisher darüber gelesen habe sind diese Kollisionen wohl sehr willkürlich herbei geführt worden - im übrigen hat man bei einem Vertrag immer zwei Ausfertigungen (sogar wenn er digital sein sollte), so dass eine plötzliche optische Differenz nun gelinde gesagt mehr als Verdächtig erweisen sollte.

[lf_dy_laglc]

Bei reinem Text dürfte eine Manipulation schwer durchzuführen sein.

Okay, dann erweitere ich die Aufgabe auf HTML, DOC, PDF, JPEG oder GIF.

[lordy]

Und wie hoch ist das Preisgeld ?

[lf_dy_laglc]

5 Ostmark

[deano]

bei den formaten wird es ja noch eine stufe schwieriger (quasi schwerer als unmöglch), weil:

du musst die komprimierung bedenken. dort lässt sich die reine information nicht einfach so verändern. bei manchen komprimierungsverfahren, z.b. bei filmen, wird der aktuelle block in verbindung mit dem letzten komprimiert.

wunder gibts sofort, bei unmöglichem bitte einen termin mit meiner sekretärin ausmachen:D