MD5-128 bit Brute force moeglich? in einer woche?

[negaH]

Zitat:

2^1024 - 2^128 ist nicht 2^896
das wäre 2^1024 / 2^128 (soweit ich mich erinnern kann nann man das nicht weiter auflösen, ohne das auszurechnen, oder?)

Korrekt: 2^1024 / 2^128 ist 2^(1024 - 128) == 2^896. So war es gemeint und das - ist ein Tippfehler, sollte natürlich / sein.

Zitat:

zudem ist meiner meinung nach ein weiterer kleiner Denkfehler drin.
Nicht alle der 2^896 (bzw eben nicht 2^896) werte werden als kollisionen erkannt werden.

Doch, es gibt für jeden der 2^128 möglichen Hash exakt 2^896 Kollisionen um auf eine Gesamtmenge von 2^1024 zu kommen. Das sollte mathematisch vom Entwickler der Hashfunktion garantiert werden. Denn eine Hashfunktion ist per Definition nur dann eine gute Hashfunktion wenn sie diese Kollisionen exakt statistisch gleichmäßig aber nicht reproduzierbar verteilt. Exakt diese Eigenschaft ist es die es erlaubt eine Hashfunktion auch als Zufallsgenerator zu gebrauchen. Denn eine nicht reproduzierbare und gleichmäßige Bitfolge von 0 und 1 ist nichts anderes als zwei unendlich große Bitfolgen aus 0 und 1 die dann gleichmäßig aber unreproduzierbar verteilt wurden. Das "unreproduzierbar" bezieht sich immer aus Sicht vom erzeugten Output zum benutzten Input.

Ergo: nach 2^128 Trials hat man alle 2^128 Bit großen Hashinputs durchgetestet und dabei mit 100% zu einem gegebenen Hashdigest einen Input gefunden. Nur das Problem dabei ist das dieser EINE Input zu unserem Digest nur einer von 2^896 möglichen Inputs darstellt um auf 2^1024 zu kommen. Die Eingangsfrage war aber konkret so das ausgehend von einem Digest der exakte Input zu finden ist. Nicht irgendein passender Input, also irgendeine Kollision, sondern DER benutzte Input eines angreifbaren Users. Und DAS geht eben nicht weil die Menge der möglichen Inputs unendlich groß ist und beim Prozess des Hashziehens Unendlich/2^128 dieser Unendlich vielen Möglichkeiten einfach Informationstheoretisch verloren gehen. Man kann also aus dem 128 Bit Digest niemals mehr exakt auf einen ganz spezifischen Input zurück-brute-forcen, einfach weil wichtige Informationen=Bits fehlen.

Das ginge nur wenn eindeutig bekannt wäre das der Input <= Digestgröße ist.

Gruß Hagen