Kollisionen in MD5 gefunden

[Roman Racine]

Gemäss [1] ist es einer Gruppe von chinesischen Wissenschaftern gelungen,
ein Verfahren zu konstruieren, mit dem binnen Stunden Kollisionen in MD5,
sowie weiteren Hashverfahren (RIPEMD, MD4, HAVAL-128) erzeugt werden
können. Leider haben sie scheinbar nicht an die Endianness-Probleme
gedacht, so dass das angegebene Beispiel nicht mit dem Standard-IV
funktioniert (für Little Endian Maschinen
{0x67452301,0xefcdab89,0x98badcfe,0x10325476}), sondern mit einem
entsprechend modifizierten ({0x01234567,0x89abcdef,0xfedcba98,0x76543210}).

Ich habe meine eigene Implementation von MD5 angepasst und notdürftig
kommandozeilentauglich gemacht (s. [2]). Mit dem modifizierten IV ergibt
sich tatsächlich eine Kollision, das in [1] angedeutete Verfahren würde
wohl grundsätzlich auch für den korrekten IV funktionieren.

Eine Kollision in SHA-0 wurde vor einigen Tagen ja schon von anderen
veröffentlicht.

Gruss

Roman

[1] http://eprint.iacr.org/2004/199.pdf
[2] http://www.trash.net/~roman/weiteres/md5_coll.tar.gz

[Carsten Krueger]

Post by Roman Racine
Ich habe meine eigene Implementation von MD5 angepasst und notdürftig
kommandozeilentauglich gemacht (s. [2]). Mit dem modifizierten IV ergibt
sich tatsächlich eine Kollision, das in [1] angedeutete Verfahren würde
wohl grundsätzlich auch für den korrekten IV funktionieren.

Kannst du das mal näher erklären?
Ich kenn mich bei Hashfunktionen nicht aus.

Kann man jetzt trivial eine Datei erzeugen die den gleichen MD5-Hash
hat wie eine vorgegebene?

Post by Roman Racine
Eine Kollision in SHA-0 wurde vor einigen Tagen ja schon von anderen
veröffentlicht.

Was ist dann zur Zeit sicher? SHA-1?

Post by Roman Racine
[2] http://www.trash.net/~roman/weiteres/md5_coll.tar.gz

403 forbidden

[Sebastian Gottschalk]

Post by Carsten Krueger
Kann man jetzt trivial eine Datei erzeugen die den gleichen MD5-Hash
hat wie eine vorgegebene?

Nein, aber du kannst trivial zwei Dateien erzeugen die den gleichen Hash
produzieren. Mit der Unterschrift des Hashes der einen hast du dann auch
eine gültige Unterschrift für die zweite.

Post by Carsten Krueger
Was ist dann zur Zeit sicher? SHA-1?

Und SHA-192 und SHA-224 und SHA-256 und RIPEMD-160.

[Carsten Krueger]

Post by Sebastian Gottschalk
Nein, aber du kannst trivial zwei Dateien erzeugen die den gleichen Hash
produzieren. Mit der Unterschrift des Hashes der einen hast du dann auch
eine gültige Unterschrift für die zweite.

Habe ich Einfluss auf den Inhalt der Dateien?

Post by Sebastian Gottschalk
Und SHA-192 und SHA-224 und SHA-256 und RIPEMD-160.

Nicht wirklich viel Auswahl.

Gruß CArsten

[Sebastian Gottschalk]

Post by Carsten Krueger

Post by Sebastian Gottschalk
Nein, aber du kannst trivial zwei Dateien erzeugen die den gleichen Hash
produzieren. Mit der Unterschrift des Hashes der einen hast du dann auch
eine gültige Unterschrift für die zweite.

Habe ich Einfluss auf den Inhalt der Dateien?

Das kann man nur anhand der Methode herausfinden, aber normalerweise nicht.
Ist aber auch egal, denn man kann ja die Bedeutung selber festlegen. Wnen
du sagst "och, diese Bytefolge ist 100 € wert" und "och, die andere
Bytefolge ist 10000 € wert" und du bekommst die 100€-Bytefolge
authorisiert...

Post by Carsten Krueger

Post by Sebastian Gottschalk
Und SHA-192 und SHA-224 und SHA-256 und RIPEMD-160.

Nicht wirklich viel Auswahl.

SHA-256 und RIPEMD-160 wird shcon lange gepredigt, letzteres sogar mit
ziemlichem Erfolg.

[Bjoern Tantau]

Post by Sebastian Gottschalk

Post by Carsten Krueger
Kann man jetzt trivial eine Datei erzeugen die den gleichen MD5-Hash
hat wie eine vorgegebene?

Nein, aber du kannst trivial zwei Dateien erzeugen die den gleichen Hash
produzieren. Mit der Unterschrift des Hashes der einen hast du dann auch
eine gültige Unterschrift für die zweite.

Ich hoffe das klingt jetzt nicht zu dämlich, aber der mit MD5 erzeugte
Hash hat doch eine Vorgegeben Länge, oder? Das heißt doch auch, das es
nur eine endliche Anzahl an möglichen Hash-Werten gibt und das
ermöglicht ja schon von vorneherein, dass es zwei (oder mehr) Dateien
geben kann, die den gleichen Hash-Wert haben.
Oder bin ich hier total am eigentlichen Topic vorbei geschossen?

Björn, ratlos

[Carsten Aulbert]

Post by Bjoern Tantau
Ich hoffe das klingt jetzt nicht zu dämlich, aber der mit MD5 erzeugte
Hash hat doch eine Vorgegeben Länge, oder? Das heißt doch auch, das es
nur eine endliche Anzahl an möglichen Hash-Werten gibt und das
ermöglicht ja schon von vorneherein, dass es zwei (oder mehr) Dateien
geben kann, die den gleichen Hash-Wert haben.
Oder bin ich hier total am eigentlichen Topic vorbei geschossen?

Eigentlich hast Du recht, aber...

md5sum /etc/passwd
d3058ae3768055bed55e392d805278ac /etc/passwd

Mal sehen, 32 Ziffern mit Inhalt [0-9a-f] also 4 bit, demzufolge hat das
ganze "Ding" 128 bit, also gibt es 2^128 Möglichkeiten bzw. wenn die
Funktion "ideal" wäre, dann gäbe es nur eine Chance von ~ 3e-39, dass zwei
beliebige, unterschiedliche Dateien den gleichen MD5-Hash haben.

Das ist schon bekannt, aber das interessante ist wohl, dass man jetzt
gezielt zwei Dateien bauen kann, die den gleichen Hash haben (werden).

Carsten

PS: Wenn ich zuviel Dummfug geschrieben habe sollte, bitte korrigieren.

[Sebastian Gottschalk]

Post by Carsten Aulbert
md5sum /etc/passwd
d3058ae3768055bed55e392d805278ac /etc/passwd
Mal sehen, 32 Ziffern mit Inhalt [0-9a-f] also 4 bit, demzufolge hat das
ganze "Ding" 128 bit,

MD5 hat immer einen 128Bit-Output, aber normalerweise schaut man sich dazu
die Funktion selber und nicht ein möglicherweise gekürztes oder gestrechtes
Ergebnis an. Ideale kryptogrpahische Funktionen kann man ja problemlos
kürzen, AES-384 ist nicht umsonstn AES-512 minus die letzten 128 Byte,
SHA-256 ist auch nix weiter als die grundlegende SHA-Funktion mit mehreren
Runden und anderer Blockgröße und -verarbeitung.

Post by Carsten Aulbert
also gibt es 2^128 Möglichkeiten bzw. wenn die
Funktion "ideal" wäre, dann gäbe es nur eine Chance von ~ 3e-39, dass zwei
beliebige, unterschiedliche Dateien den gleichen MD5-Hash haben.

Falsch. Der optimale Angriff besteht nämlich nicht darin zu einen gegebenen
Eingabe eine Eingabe mit gleichem Inahlt zu finden (was im Schnitt 2**128 /
2 = 2**127 Versuche benötigt), sondern in dem Geburtstagsparadoxon, das
besagt daß ich nur sqr(2**128)=2**64 Nachrichten generieren muss um bereits
eine 50%ige Chance zu haben daß zwei davon den gleichen Hashwert erzeugen.

Post by Carsten Aulbert
PS: Wenn ich zuviel Dummfug geschrieben habe sollte, bitte korrigieren.

Done :-)

[Carsten Aulbert]

Post by Sebastian Gottschalk
Falsch. Der optimale Angriff besteht nämlich nicht darin zu einen gegebenen
Eingabe eine Eingabe mit gleichem Inahlt zu finden (was im Schnitt 2**128 /
2 = 2**127 Versuche benötigt), sondern in dem Geburtstagsparadoxon, das
besagt daß ich nur sqr(2**128)=2**64 Nachrichten generieren muss um bereits
eine 50%ige Chance zu haben daß zwei davon den gleichen Hashwert erzeugen.

Ich weiß, aber was scheren mich 50%, wenn ich Sicherheit haben will? ;)
Frage bleibt nur, was ist das Paradoxe am Geburtstagsparadoxon?

Post by Sebastian Gottschalk

Post by Carsten Aulbert
PS: Wenn ich zuviel Dummfug geschrieben habe sollte, bitte korrigieren.

Done :-)

Danke!

Carsten

f'up2p, weil wir abdriften.

[Sebastian Gottschalk]

Post by Carsten Aulbert
Ich weiß, aber was scheren mich 50%, wenn ich Sicherheit haben will? ;)

Die 50% Chance entsprechen dem durchschnittlichen Aufwand.
\sum AnzahlDerVersuche \null AnzahlDerVersuche * Chance =
DurchschnittlicheAnzahlderVersuche * 0.5

Post by Carsten Aulbert
Frage bleibt nur, was ist das Paradoxe am Geburtstagsparadoxon?

Wieviele Menschen braucht man in einem Raum damit die Chance, daß zwei von
ihnen an gleichem Tag im Jahr Geburtstag haben, 50% beträgt? Nur 23 =
roundup(sqr(366)). Bei 2^128 Inputs reichen dann nur die vergleichsweise
lächerliche Anzahl von 2^64 Inputs aus um eine Kollision verbeizuführen.

Post by Carsten Aulbert
f'up2p, weil wir abdriften.

fup ignoriert, weil wir nicht abdriften. Der Übergang zwischen der einen
Variante des Angriffs (bestehende Nachricht verändern) zu der anderen
(Kollisionen in großen Mengen an Inputs finden) ist alles andere als
trivial.

[Carsten Aulbert]

Post by Sebastian Gottschalk

Post by Carsten Aulbert
Frage bleibt nur, was ist das Paradoxe am Geburtstagsparadoxon?

Wieviele Menschen braucht man in einem Raum damit die Chance, daß zwei von
ihnen an gleichem Tag im Jahr Geburtstag haben, 50% beträgt? Nur 23 =
roundup(sqr(366)). Bei 2^128 Inputs reichen dann nur die vergleichsweise
lächerliche Anzahl von 2^64 Inputs aus um eine Kollision verbeizuführen.

Äh, Du weißt, dass das mit der Wurzel hier Zufall ist (wenn es passen würde)?
[ ] Ja
[ ] Nein

Du hast schon einmal in Deinem Leben die Quadratwurzel von 366 berechnet?
[ ] Ja
[ ] Nein

Du definierst "roundup" als int(x)+Daumen mit der Situation angemessenem Daumen.
[ ] Ja
[ ] Nein

Die 23 bekommst Du, wenn Du 365/365 * 364/365 * 363/365 * ... * (365-i/365)
berechnest, dann ergibt dieser Wert für i=23 das erste Mal eine
"Gegenwahrscheinlichkeit" von < 50%.

Carsten, der noch versucht zu verstehen, woher die Wurzel beim MD5-Hash kommt.

[Sebastian Gottschalk]

Post by Carsten Aulbert
Äh, Du weißt, dass das mit der Wurzel hier Zufall ist (wenn es passen würde)?
[ ] Ja
[X] Nein

Lässt sich auch so beweisen.

Post by Carsten Aulbert
Du hast schon einmal in Deinem Leben die Quadratwurzel von 366 berechnet?
[X] Ja
[ ] Nein

Ist ~19,1.

Post by Carsten Aulbert
Du definierst "roundup" als int(x)+Daumen mit der Situation angemessenem Daumen.
[X] Ja
[ ] Nein
Die 23 bekommst Du, wenn Du 365/365 * 364/365 * 363/365 * ... * (365-i/365)
berechnest, dann ergibt dieser Wert für i=23 das erste Mal eine
"Gegenwahrscheinlichkeit" von < 50%.

Für 365 ist das ja noch trivial zu berechen, für n gegen unendlich
konvergiert i aber gegen sqr(n).

Post by Carsten Aulbert
Carsten, der noch versucht zu verstehen, woher die Wurzel beim MD5-Hash kommt.

Genau daher.
2**128/2**128 * (2**128-1)/(2**128) * ... is für i=2**64 das erste mal
<50%.

[Rudolf Polzer]

Post by Carsten Aulbert

Post by Sebastian Gottschalk

Post by Carsten Aulbert
Frage bleibt nur, was ist das Paradoxe am Geburtstagsparadoxon?

Wieviele Menschen braucht man in einem Raum damit die Chance, daß zwei von
ihnen an gleichem Tag im Jahr Geburtstag haben, 50% beträgt? Nur 23 =
roundup(sqr(366)). Bei 2^128 Inputs reichen dann nur die vergleichsweise
lächerliche Anzahl von 2^64 Inputs aus um eine Kollision verbeizuführen.

Äh, Du weißt, dass das mit der Wurzel hier Zufall ist (wenn es passen würde)?

[...]

Post by Carsten Aulbert
Du hast schon einmal in Deinem Leben die Quadratwurzel von 366 berechnet?

[...]

Post by Carsten Aulbert
Du definierst "roundup" als int(x)+Daumen mit der Situation angemessenem Daumen.

[...]

Post by Carsten Aulbert
Die 23 bekommst Du, wenn Du 365/365 * 364/365 * 363/365 * ... * (365-i/365)
berechnest, dann ergibt dieser Wert für i=23 das erste Mal eine
"Gegenwahrscheinlichkeit" von < 50%.
Carsten, der noch versucht zu verstehen, woher die Wurzel beim MD5-Hash kommt.

Also, wir hätten da bei k aus n Elementen:

p = n/n * (n-1)/n * (n-2)/n * ... * (n-k+1)/n

Das will ich jetzt von oben abschätzen. Es ist ja:

(n-k)/n = 1-k/n <= (1-1/n)^k

Also:

p <= (1-1/n)^0 * (1-1/n)^1 * (1-1/n)^2 * ... * (1-1/n)^(k-1)
<= (1-1/n)^((k^2 - k) / 2)

Nun ist aber auch (1-1/n)^n < e^(-1), also:

< e^(-(k^2 - k) / (2n))

Für p >= 1/2 gilt damit

1/2 < e^(-(k^2 - k) / (2n))
-ln 2 < -(k^2 - k) / (2n)
k^2 - k < 2n ln 2

Ist also k^2 - k >= 2n ln 2, dann ist zwingend p < 1/2, wir haben also
über 50% Kollisionswahrscheinlichkeit. Das bedeutet nun für k:

k >= 1/2 + sqrt(1/4 + 2n ln 2) =: f(n)

und man sieht schnell:

f(n) ~ sqrt(2n)
f(n) = Theta(sqrt(n))
(folglich ist das minimale k für >=50% Kollisionswahrscheinlichkeit
O(sqrt(n)))

Ich komme bei 366 auf k >= 27.055..., das ist zwar "zuviel", liegt aber
an den groben Abschätzungen.

Naja, es sollte zumindest erklären, woher diese Wurzel kommt. Ja, manche
Leute vergessen gerne das O bei der O-Notation, wie hier geschehen.

Ja, es wäre sicher auch noch einfacher gegangen.

[Urs [Ayahuasca] Traenkner]

Post by Bjoern Tantau
Ich hoffe das klingt jetzt nicht zu dämlich, aber der mit MD5 erzeugte
Hash hat doch eine Vorgegeben Länge, oder? Das heißt doch auch, das es
nur eine endliche Anzahl an möglichen Hash-Werten gibt und das
ermöglicht ja schon von vorneherein, dass es zwei (oder mehr) Dateien
geben kann, die den gleichen Hash-Wert haben.

Ja. Aber gewoehnlich ist der Anspruch an eine vernuenftige
Hash-Funktion, dass eben eine solche Datei eben nicht trivial,
sondern de facto nur per brute force gefunden werden kann, und
das braucht natuerlich Zeit.

Post by Bjoern Tantau
Oder bin ich hier total am eigentlichen Topic vorbei geschossen?

Nicht wirklich.

Aber um hier mal eine Frage in den Raum zu werfen: ist MD5 jetzt
tot oder wie muss ich das verstehen?

Wieso liest man zuerst hier davon? Das duerfte ja dann doch
weitreichende Konsequenzen haben, da sich doch recht viele
Verfahren auf MD5-hashes verlassen.

Gruss Urs...

[Bjoern Tantau]

Post by Urs [Ayahuasca] Traenkner
Aber um hier mal eine Frage in den Raum zu werfen: ist MD5 jetzt
tot oder wie muss ich das verstehen?
Wieso liest man zuerst hier davon? Das duerfte ja dann doch
weitreichende Konsequenzen haben, da sich doch recht viele
Verfahren auf MD5-hashes verlassen.

Ich denke nicht. Solange man das speziell konstruieren muss und sich das
nicht auf bestehende Daten anwenden lässt sollte man doch sicher sein.

Björn

[Sebastian Gottschalk]

Post by Urs [Ayahuasca] Traenkner
Aber um hier mal eine Frage in den Raum zu werfen: ist MD5 jetzt
tot oder wie muss ich das verstehen?

MD5 war mit 128 Bit = birthday 64 Bit für zukünftige praktische
Anwendungen, wegen den Pseudo-Kollisionen (Rivest hat nie erklärt warum
genau er diese IVs gewählt hat) und vor allem wegen der endgültigen
Brechbarkeit (man benötigt ca. 2**86 Schritt um aus einer Nachricht eine
andere mit gleichem MD5-Hash zu generieren, was weit unter den theoretisch
optimalen 2**127 liegt) einfach nicht mehr geeignet. Deshalb wurde ja der
Einsatz von SHA-1 und RIPEMD-160 so stark gefördert

Post by Urs [Ayahuasca] Traenkner
Wieso liest man zuerst hier davon? Das duerfte ja dann doch
weitreichende Konsequenzen haben, da sich doch recht viele
Verfahren auf MD5-hashes verlassen.

In sci.crypt las man schon eher davon. Ansonsten ACK - das dürfte der Grund
sein warum die Leutz das Verafhren zunächst erstmal verschweigen und nur
Zero-Knowledge-Beweise anbringen.

[Ralf Muschall]

Post by Sebastian Gottschalk
Anwendungen, wegen den Pseudo-Kollisionen (Rivest hat nie erklärt warum
genau er diese IVs gewählt hat) und vor allem wegen der endgültigen

IIRC hat er bewusst welche gewählt, die man *nicht* erklären muss.
Ansonsten gäbe es ähnlichen Grund für Misstrauen wie bei DES.

Ralf

[Florian Weimer]

Post by Ralf Muschall

Post by Sebastian Gottschalk
Anwendungen, wegen den Pseudo-Kollisionen (Rivest hat nie erklärt warum
genau er diese IVs gewählt hat) und vor allem wegen der endgültigen

IIRC hat er bewusst welche gewählt, die man *nicht* erklären muss.

Ja, der IV ist sehr regelmäßig (und wenn's viele schwache gäbe, wäre
MD5 auch noch deswegen kaputt), und auch für die anderen magischen
Konstanten gibt es eine einfache Erklärung.

[Florian Weimer]

Post by Urs [Ayahuasca] Traenkner
Aber um hier mal eine Frage in den Raum zu werfen: ist MD5 jetzt
tot oder wie muss ich das verstehen?

Solange der eigentliche Angriff nicht veröffentlicht wird, ist das
schwer zu sagen. 8-) Im Moment schaut es nur danach aus, als ob extrem
exotische Protokolle ein Problem hätten.

Auf jeden Fall ist das eine spannende Entwicklung.

[Sebastian Gottschalk]

Post by Florian Weimer
Solange der eigentliche Angriff nicht veröffentlicht wird, ist das
schwer zu sagen. 8-) Im Moment schaut es nur danach aus, als ob extrem
exotische Protokolle ein Problem hätten.

Nein. Laut Behauptung der Wissenschaftler funktioniert das Verfahren für
jeden IV, also auch den originalen. Damit wäre MD5 gebrochen und das hätte
Einfluss auf sehr viele Protokolle und Anwendungen.

[Florian Weimer]

Post by Sebastian Gottschalk

Post by Florian Weimer
Solange der eigentliche Angriff nicht veröffentlicht wird, ist das
schwer zu sagen. 8-) Im Moment schaut es nur danach aus, als ob extrem
exotische Protokolle ein Problem hätten.

Nein. Laut Behauptung der Wissenschaftler funktioniert das Verfahren
für jeden IV, also auch den originalen. Damit wäre MD5 gebrochen und
das hätte Einfluss auf sehr viele Protokolle und Anwendungen.

Natürlich sollte man MD5 spätestens jetzt als gebrochen betrachten,
aber die Angriffsmöglichkeiten, die sich auf jeden Fall ergeben,
reichen für Angriffe auf real existierende Protokolle nicht wirklich
aus: Man kann damit noch nicht zu einer vorgegebenen Nachricht eine
Kollision erzeugen. Höchstens kann man die Nachricht unterschiedlich
verlängern und so eine Kollision bekommen (die dann aber nicht mehr
zum ursprünglichen Hash paßt), aber das dürfte einem bei den wenigsten
Protokollen weiterhelfen.

[Michael Sçheer]

Post by Florian Weimer
Höchstens kann man die Nachricht unterschiedlich
verlängern und so eine Kollision bekommen (die dann aber nicht mehr
zum ursprünglichen Hash paßt)

Dann wäre es aber doch keine Kollision.

[Sebastian Gottschalk]

Post by Michael Sçheer

Post by Florian Weimer
Höchstens kann man die Nachricht unterschiedlich
verlängern und so eine Kollision bekommen (die dann aber nicht mehr
zum ursprünglichen Hash paßt)

Dann wäre es aber doch keine Kollision.

Doch, das wäre eine. Und sogar ein sehr guter Angriff, denn man könnte den
Rest bei der einen Nachricht als weitere Nachricht und bei der anderen als
wahrscheinliches Random Padding bezeichnen.

[Michael Sçheer]

Post by Sebastian Gottschalk

Post by Michael Sçheer

Post by Florian Weimer
Höchstens kann man die Nachricht unterschiedlich
verlängern und so eine Kollision bekommen (die dann aber nicht mehr
zum ursprünglichen Hash paßt)

Dann wäre es aber doch keine Kollision.

Doch, das wäre eine. Und sogar ein sehr guter Angriff, denn man könnte den
Rest bei der einen Nachricht als weitere Nachricht und bei der anderen als
wahrscheinliches Random Padding bezeichnen.

*rätsel*rätsel* Ach so...
Für die, bei denen der Groschen noch nicht fiel: Florian meint also
eine Kollision aus zwei neuen Nachrichten, die beide die alte
enthalten, aber beide untersch. Verlängerungen dazu haben.

[Sebastian Gottschalk]

Post by Michael Sçheer
*rätsel*rätsel* Ach so...
Für die, bei denen der Groschen noch nicht fiel: Florian meint also
eine Kollision aus zwei neuen Nachrichten, die beide die alte
enthalten, aber beide untersch. Verlängerungen dazu haben.

Genau. Entweder kannst du bei der einen die Verlängerung sinnvoll wählen
und bei der anderen erhältst du pseudozufälligen Müll, oder du erhältst bei
beiden pseudozufälligen Müll und verpasst dem einen Müll entwedre direkt
oder mit OTP eine Bedeutung, während der andere Müll bedeutungslos bleibt.
Das Dedeutungslose wird mitsigniert und dann die Nachricht im Nachhinein
durch die mit dem bedeutungsvollen Padding ausgetauscht.

[Florian Weimer]

Post by Sebastian Gottschalk
Genau. Entweder kannst du bei der einen die Verlängerung sinnvoll wählen
und bei der anderen erhältst du pseudozufälligen Müll,

Und wie willst Du das erreichen, wenn Du bloß zu einer vorgegebenen
Nachricht m zwei Nachrichten m' und m'' erzeugen kannst, daß
MD5(m m') = MD5(m m'') gilt?

Das ist mir im Moment überhaupt nicht klar.

Post by Sebastian Gottschalk
oder du erhältst bei beiden pseudozufälligen Müll und verpasst dem
einen Müll entwedre direkt oder mit OTP eine Bedeutung, während der
andere Müll bedeutungslos bleibt.

Und bei welchem Protokoll soll das bitte funktionieren?

[Sebastian Gottschalk]

Post by Florian Weimer
Und wie willst Du das erreichen, wenn Du bloß zu einer vorgegebenen
Nachricht m zwei Nachrichten m' und m'' erzeugen kannst, daß
MD5(m m') = MD5(m m'') gilt?
Das ist mir im Moment überhaupt nicht klar.

Wie schon gesagt: _nur_ wenn das Verfahren das zulässt.

Post by Florian Weimer

Post by Sebastian Gottschalk
oder du erhältst bei beiden pseudozufälligen Müll und verpasst dem
einen Müll entwedre direkt oder mit OTP eine Bedeutung, während der
andere Müll bedeutungslos bleibt.

Und bei welchem Protokoll soll das bitte funktionieren?

Z.B. schriftlicher Vertrag oder Online-Payment, wo pseudozufällige
Bytefolgen als Zahlungseinheiten interpretiert werden, sofern sie von der
Bank gegen Bezahlung des entsprechenden Betrags signiert werden.

[Roman Racine]

Post by Carsten Krueger
Kannst du das mal näher erklären?
Ich kenn mich bei Hashfunktionen nicht aus.

Die Autoren wollen wohl im Vorfeld einer Konferenz ihr Verfahren noch nicht
im Detail darlegen. Grundsaetzlich dienen kryptografische Hashfunktionen
dazu, einer beliebig langen Datei einen eindeutigen String von fixer Laenge
zuzuordnen, so dass es berechenmaessig nicht moeglich ist, eine Kollision
zu erzeugen oder ein zu einem bestimmten Hash passenden Input zu finden. Da
beliebig langer Input auf einen fixen Input abgebildet wird, ist es
grundsaetzlich klar, dass es Kollisionen geben muss. Relevant ist, dass
sich diese nicht schneller als mit Brute Force erzeugen lassen. Dies wuerde
bedeuten, dass man im Durchschnitt fuer MD5 2^127 Inputs ausprobieren muss,
um einen Input zu finden, der zu einem gegebenen Hashwert passt oder 2^64,
um zwei kollidierende Inputs zu finden. Wenn es keine besseren Verfahren
als Brute Force gaebe, koennte man eine kryptografische Hashfunktion mit
einer Laenge von 128 Bit im Moment noch als sicher bezeichnen. Aber
offenbar gibt es bessere Verfahren, wenn die Zeitangaben (ca. eine Stunde,
um eine Kollision zu finden) stimmen, muss es sogar sehr viel schnellere
Verfahren geben.

Post by Carsten Krueger
Kann man jetzt trivial eine Datei erzeugen die den gleichen MD5-Hash
hat wie eine vorgegebene?

Darueber ist AFAIK noch nichts bekannt. Im verlinkten Paper war die Rede
davon, dass Inputs gezielt konstruiert werden, um Kollisionen zu erzeugen,
aber allzuviel steht da ja nicht.

Post by Carsten Krueger
Was ist dann zur Zeit sicher? SHA-1?

Vermutlich.

Gruss

Roman

[Roman Racine]

Post by Roman Racine
[2] http://www.trash.net/~roman/weiteres/md5_coll.tar.gz

Ach ja, passende Zugriffsberechtigungen habe ich nun auch noch gesetzt.

Gruss

Roman

[Michael Sçheer]

Post by Roman Racine
Gemäss [1] ist es einer Gruppe von chinesischen Wissenschaftern gelungen,
ein Verfahren zu konstruieren, mit dem binnen Stunden Kollisionen in MD5,
sowie weiteren Hashverfahren (RIPEMD, MD4, HAVAL-128) erzeugt werden
können.

Angenommen md5(M)== m ==md5(M'). Welche Szenarien hältst Du für
praktisch relevant insofern, als md5 nicht den Anforderungen genügen
wird wenn davon ausgegangen werden kann, dass für die Kollision
gefundene neue Menge M' inhaltlich wahrscheinlich sinnlos wäre? Anders
gesagt: Gibt es Szenarien, in denen keine Kollision vorkommen darf,
egal wie "sinnlos" das gefundene M' sein wird?

Szenario 1: Ich bilde md5 über Text, über Quelltext, über irgendwelche
"sinnhaften" Inhalte. Dann könnte ein Angreifer interessiert sein, ein
M' zu finden, dann aber hat er wiederum kaum etwas davon, da M'
wahrscheinlich offensichtlich sinnlos.

Szenario 2: Sammeln einer Liste von md5 beispielsweise um irgendwelche
abgearbeiteten Zustände (z.B. "bereits virengescannte Mails") zu
speichern. Wenn ich in einem solchen Szenario aber keine Angreifer
erwarten kann, interessiert doch nur die Wahrscheinlichkeit einer
Kollision, und die ist sicher irgendwo nachschlagbar.

Bei Hash-Kollisionen habe ich immer den Eindruck, dass die Erkenntnis
über dieselben noch fern jeder praktischen Relevanz sind. Oder?

(Was natürlich nicht bedeutet, dass man dann nicht besser gleich
kollisionsfreiere Funktionen nehmen soll, wenn machbar)

BrothomStates (Lassi Nikko) - (05) Abdea [Kobn-Tich-Ey]

[Christoph 'Mehdorn' Weber]

Hallo!

Post by Michael Sçheer
Angenommen md5(M)== m ==md5(M'). Welche Szenarien hältst Du für
praktisch relevant insofern, als md5 nicht den Anforderungen genügen
wird wenn davon ausgegangen werden kann, dass für die Kollision
gefundene neue Menge M' inhaltlich wahrscheinlich sinnlos wäre? Anders
gesagt: Gibt es Szenarien, in denen keine Kollision vorkommen darf,
egal wie "sinnlos" das gefundene M' sein wird?

Unter unixoiden Systemen werden unter anderem Triple-DES und
md5-Hashes über Paßwörter gebildet. Wenn du den md5-Hash klauen kannst
und dazu innerhalb von etwa einer Stunde ein passendes Paßwort findest,
kannst du dich damit einloggen. Ohne das echte Paßwort zu kennen.

Post by Michael Sçheer
Szenario 1: Ich bilde md5 über Text, über Quelltext, über irgendwelche
"sinnhaften" Inhalte. Dann könnte ein Angreifer interessiert sein, ein
M' zu finden, dann aber hat er wiederum kaum etwas davon, da M'
wahrscheinlich offensichtlich sinnlos.

Wandele es etwas ab. Du hast ein Binary-Zeugs, beispielsweise ein
CD-Image. Der Angreifer hat es ein wenig abgespeckt und böse Malware mit
hineingetan. Mit der Methode berechnet er jetzt, welche Daten er noch an
das verkleinerte Image anhängen muß, damit es etwa so groß ist wie das
Original und die Summe mit der anderen Summe übereinstimmt. Dann schiebt
er es seinem Opfer unter. Das Opfer prüft nicht die gesamte Datei mit
dem Original gegen, sondern besorgt sich nur die Summe und ist
glücklich.

Digital signierte Download könnten in nächster Zeit deutlich zunehmen.
Aber MD5 war sowieso meist nicht viel mehr als eine Überprüfung, ob die
Datei auch korrekt übertragen wurde.

Christoph

[Florian Weimer]

Post by Christoph 'Mehdorn' Weber
Unter unixoiden Systemen werden unter anderem Triple-DES und
md5-Hashes über Paßwörter gebildet. Wenn du den md5-Hash klauen kannst
und dazu innerhalb von etwa einer Stunde ein passendes Paßwort findest,
kannst du dich damit einloggen. Ohne das echte Paßwort zu kennen.

Die Daten, die bislang präsentiert wurden, legen aber nahe, daß ein
derartig mächtiger Angriff eben nicht existiert.

[André Malo]

Post by Florian Weimer

Post by Christoph 'Mehdorn' Weber
Unter unixoiden Systemen werden unter anderem Triple-DES und
md5-Hashes über Paßwörter gebildet. Wenn du den md5-Hash klauen kannst
und dazu innerhalb von etwa einer Stunde ein passendes Paßwort findest,
kannst du dich damit einloggen. Ohne das echte Paßwort zu kennen.

Die Daten, die bislang präsentiert wurden, legen aber nahe, daß ein
derartig mächtiger Angriff eben nicht existiert.

Zumal zumindest bei MD5-crypt kein reiner Digest berechnet wird, sondern ein
bisschen mehr. Ich gehe mal davon aus, dass die Kollisionsberechnung dadurch
deutlich erschwert wird.

nd

[Michael Sçheer]

Post by André Malo

Post by Florian Weimer
Die Daten, die bislang präsentiert wurden, legen aber nahe, daß ein
derartig mächtiger Angriff eben nicht existiert.

Zumal zumindest bei MD5-crypt kein reiner Digest berechnet wird, sondern ein
bisschen mehr. Ich gehe mal davon aus, dass die Kollisionsberechnung dadurch
deutlich erschwert wird.

Was macht es denn noch? Ein salt wäre aber bei einem solchen Angriff
unnütz, oder?

[Florian Weimer]

Post by Michael Sçheer

Post by André Malo
Zumal zumindest bei MD5-crypt kein reiner Digest berechnet wird, sondern ein
bisschen mehr. Ich gehe mal davon aus, dass die Kollisionsberechnung dadurch
deutlich erschwert wird.

Was macht es denn noch?

Es gibt noch ein Padding:

| 3.1 Step 1. Append Padding Bits
|
| The message is "padded" (extended) so that its length (in bits) is
| congruent to 448, modulo 512. That is, the message is extended so
| that it is just 64 bits shy of being a multiple of 512 bits long.
| Padding is always performed, even if the length of the message is
| already congruent to 448, modulo 512.
|
| Padding is performed as follows: a single "1" bit is appended to the
| message, and then "0" bits are appended so that the length in bits of
| the padded message becomes congruent to 448, modulo 512. In all, at
| least one bit and at most 512 bits are appended.

<http://www.rfc-editor.org/rfc/rfc1321.txt>

[Michael Sçheer]

Post by Christoph 'Mehdorn' Weber

Post by Michael Sçheer
Angenommen md5(M)== m ==md5(M'). Welche Szenarien hältst Du für
praktisch relevant insofern, als md5 nicht den Anforderungen genügen
wird wenn davon ausgegangen werden kann, dass für die Kollision
gefundene neue Menge M' inhaltlich wahrscheinlich sinnlos wäre? Anders
gesagt: Gibt es Szenarien, in denen keine Kollision vorkommen darf,
egal wie "sinnlos" das gefundene M' sein wird?

Unter unixoiden Systemen werden unter anderem Triple-DES und
md5-Hashes über Paßwörter gebildet. Wenn du den md5-Hash klauen kannst
und dazu innerhalb von etwa einer Stunde ein passendes Paßwort findest,
kannst du dich damit einloggen. Ohne das echte Paßwort zu kennen.

Stümmt, das würde dann sicher Logins vieler Systeme betreffen. Es
deckt sich aber nicht ganz mit dem vom OP geschilderten. Da war, um
bei Deinem Beispiel zu bleiben, auch das ursprüngliche Paßwort
bekannt, vielleicht ist das ja für deren Methode entscheidend.

[Christoph 'Mehdorn' Weber]

Hallo!

Post by Michael Sçheer

Post by Christoph 'Mehdorn' Weber
Unter unixoiden Systemen werden unter anderem Triple-DES und
md5-Hashes über Paßwörter gebildet. Wenn du den md5-Hash klauen kannst
und dazu innerhalb von etwa einer Stunde ein passendes Paßwort findest,
kannst du dich damit einloggen. Ohne das echte Paßwort zu kennen.

Stümmt, das würde dann sicher Logins vieler Systeme betreffen. Es
deckt sich aber nicht ganz mit dem vom OP geschilderten. Da war, um
bei Deinem Beispiel zu bleiben, auch das ursprüngliche Paßwort
bekannt, vielleicht ist das ja für deren Methode entscheidend.

Nun ja, vielleicht werden wir es ja in absehbarer Zeit erfahren, ob es
möglicherweise doch möglich ist. Und wenn ja, wird das vermutlich erst
mal ziemlich unschön. Zumindest für Einrichtungen, die viele Nutzer
betreuen und entsprechende Paßwörter benutzen.

Christoph

[Adrian Knoth]

Post by Christoph 'Mehdorn' Weber

Post by Michael Sçheer

Post by Christoph 'Mehdorn' Weber
Unter unixoiden Systemen werden unter anderem Triple-DES und
md5-Hashes über Paßwörter gebildet. Wenn du den md5-Hash klauen kannst

Stümmt, das würde dann sicher Logins vieler Systeme betreffen. Es

Nun ja, vielleicht werden wir es ja in absehbarer Zeit erfahren, ob es
möglicherweise doch möglich ist.

Die Frage ist doch ohnehin, ob ich für den gleichen Hash dann
ein Paßwort der Länge 2^30 Bytes eingeben muß oder ob die
Kollision auftritt, bevor die getline-Routine schlapp macht.

[Alexander Skwar]

Post by Adrian Knoth
Die Frage ist doch ohnehin, ob ich für den gleichen Hash dann
ein Paßwort der Länge 2^30 Bytes eingeben muß oder ob die
Kollision auftritt, bevor die getline-Routine schlapp macht.

Wobei man bei Passwörtern oft ja noch nichtmal den kompletten
Bereich von 0 bis 255 als zulässige Werte eines Zechens verwenden
kann (0x00 dürfte z.B. Probleme bereiten). Dadurch wird die
Findung einer "Kollisionsmessage" schon wieder schwieriger.

Alexander Skwar

[Frank Dittrich]

Post by Michael Sçheer

Post by Christoph 'Mehdorn' Weber
Unter unixoiden Systemen werden unter anderem Triple-DES und
md5-Hashes über Paßwörter gebildet. Wenn du den md5-Hash klauen kannst
und dazu innerhalb von etwa einer Stunde ein passendes Paßwort findest,
kannst du dich damit einloggen. Ohne das echte Paßwort zu kennen.

Stümmt, das würde dann sicher Logins vieler Systeme betreffen.

Das klingt fast so, als ob man für die Implementation eines kaputten
Hash-Algorithmus unter Verwendung von MD5 auf Kollisionen *in* MD5
angewiesen wäre.
Diese bösartige Unterstellung möchte ich nicht unkommentiert lassen:

http://groups.google.com/groups?selm=63466f05.0408162245.679aaa26%40posting.google.com

Frank

[Michael Sçheer]

Post by Frank Dittrich

Post by Michael Sçheer
Stümmt, das würde dann sicher Logins vieler Systeme betreffen.

Das klingt fast so, als ob man für die Implementation eines kaputten
Hash-Algorithmus unter Verwendung von MD5 auf Kollisionen *in* MD5
angewiesen wäre.
Diese bösartige Unterstellung

Na dass man natürlich im Falle von Zugangskennungen z.B. auf
Übereinstimmung des bekannten Hashwerts mit Hash(wordlist) untersucht,
ist wohl klar. Kollision IN md5 wäre ja auch erst interessant, wenn
trivial berechenbar.

[Roman Racine]

Post by Michael Sçheer
Welche Szenarien hältst Du für
praktisch relevant insofern, als md5 nicht den Anforderungen genügen
wird wenn davon ausgegangen werden kann, dass für die Kollision
gefundene neue Menge M' inhaltlich wahrscheinlich sinnlos wäre? Anders
gesagt: Gibt es Szenarien, in denen keine Kollision vorkommen darf,
egal wie "sinnlos" das gefundene M' sein wird?

So wie sich die konstruierten Kollisionen bisher präsentieren, wären
möglicherweise im Moment nur dort Auswirkungen zu spüren, wo jedes M einen
Sinn haben könnte.

Ein Beispiel: Angenommen, ein RSA Schlüssel M wird mit MD5 gesichert (z.B.
von jemandem signiert); dann könnte ein kollidirendes M' mit äquivalentem
Hash einen Schlüssel ergeben, dessen RSA Modulus relativ leicht
faktorisierbar ist und der damit leicht zu brechen ist. Möglicherweise gibt
es auch noch andere Bereiche, in denen jedes M einen Sinn haben könnte.

Gruss

Roman

[Christian Thöing]

Post by Roman Racine
Gemäss [1] ist es einer Gruppe von chinesischen Wissenschaftern gelungen,
ein Verfahren zu konstruieren, mit dem binnen Stunden Kollisionen in MD5,
sowie weiteren Hashverfahren (RIPEMD, MD4, HAVAL-128) erzeugt werden
können. [...]

Die Nachricht bestätigt eine Entwicklung, die seit längerem abzusehen
war: hatten doch schon vor Jahren Hans Dobbertin u.a. zeigen können,
dass die MD5-Kompressionsfunktion wie der Vorgänger MD4 anfällig für
Kollisionen ist, obschon sich diese Schwäche bisher -- im Gegensatz zu
MD4 -- nicht praktisch ausnutzen ließ (möglicher Geburtstags-Angriff
durch zu kurzen Hashwert von 128 Bit mal beiseite). Es bleibt abzusehen,
welche weiteren Hashfunktionen vom vorgestellten Angriff noch betroffen
sein könnten...

[Roman Racine]

Post by Roman Racine
Gemäss [1] ist es einer Gruppe von chinesischen Wissenschaftern gelungen,
ein Verfahren zu konstruieren,

[...]

[1] ist mittlerweile aktualisiert und enthält Kollisionen für den
Standard-IV von MD5. Ich habe es soeben ausprobiert, es gibt tatsächlich
eine Kollision, allerdings nicht mit den dort angegebenen Hashwerten. Für
die erste angegebene Kollision habe ich zwei Files mit den angegebenen
Werten erstellt [2].

Gruss

Roman

Post by Roman Racine
[1] http://eprint.iacr.org/2004/199.pdf

[2] http://www.trash.net/~roman/weiteres/collision.tar.gz

[Georg Dingler]

Zum Thema:

http://www.heise.de/newsticker/meldung/50148

[Lutz Donnerhacke]

Post by Georg Dingler
http://www.heise.de/newsticker/meldung/50148

*gähn*

[Urs [Ayahuasca] Traenkner]

Post by Lutz Donnerhacke

Post by Georg Dingler
http://www.heise.de/newsticker/meldung/50148

*gähn*

Was sagst Du eigentlich zu der ganzen Geschichte? Du hast Dich ja
noch gar nicht zu Wort gemeldet, was mich ein bisschen wundert...

Gruss Urs...

[Lutz Donnerhacke]

Post by Urs [Ayahuasca] Traenkner

Post by Lutz Donnerhacke

Post by Georg Dingler
http://www.heise.de/newsticker/meldung/50148

*gähn*

Was sagst Du eigentlich zu der ganzen Geschichte? Du hast Dich ja
noch gar nicht zu Wort gemeldet, was mich ein bisschen wundert...

;-) Ich habe es mir erstmal in Ruhe angesehen.

Es schaut so aus, als ob man einen Fehler in der Behandlung der
höchstwertigen Bits der Statusvariablen gefunden hat (Überträge heben sich
einfach raus), indem man das Hineinrollen dieser Bits geschickt ausmaskiert
und somit ein Gleichungssystem in n¹ bit bekommt. Das erklärt auch die
Unabhängigkeit vom IV.

Wenn man also kein Protokoll benutzt, daß zufälliges Padding direkt vor der
Hashfunktion benutzt, ist man fein raus. Eine kurze Diskussion mit Thomas
Walpuski (derzeit Praktikant hier) ergab, daß er sich auch nicht an Routinen
erinneren könne, die die "Nulligkeit" des Paddings prüfen. Und das ist ein
Problem.


1 Anzahl der Statusworte.

[Florian Weimer]

Post by Lutz Donnerhacke
Es schaut so aus, als ob man einen Fehler in der Behandlung der
höchstwertigen Bits der Statusvariablen gefunden hat (Überträge heben sich
einfach raus), indem man das Hineinrollen dieser Bits geschickt ausmaskiert
und somit ein Gleichungssystem in n¹ bit bekommt. Das erklärt auch die
Unabhängigkeit vom IV.

War das dem Webcast zu entnehmen?

[Lutz Donnerhacke]

Post by Florian Weimer

Post by Lutz Donnerhacke
Es schaut so aus, als ob man einen Fehler in der Behandlung der
höchstwertigen Bits der Statusvariablen gefunden hat (Überträge heben sich
einfach raus), indem man das Hineinrollen dieser Bits geschickt ausmaskiert
und somit ein Gleichungssystem in n¹ bit bekommt. Das erklärt auch die
Unabhängigkeit vom IV.

War das dem Webcast zu entnehmen?

Nein, dem Paper, dem Algorithmus und einer Tüte Schlaf.

[highKO Moye]

Post by Lutz Donnerhacke
;-) Ich habe es mir erstmal in Ruhe angesehen.
...
Es schaut so aus, als ob man einen Fehler in der Behandlung der
höchstwertigen Bits der Statusvariablen gefunden hat (Überträge heben sich
einfach raus), indem man das Hineinrollen dieser Bits geschickt ausmaskiert
und somit ein Gleichungssystem in n¹ bit bekommt...
Wenn man also kein Protokoll benutzt, daß zufälliges Padding direkt vor der
Hashfunktion benutzt, ist man fein raus...

Was macht den Content vorm hashen ohne zufälliges Padding denn besser?
Hier fehlt mir irgendwas an Wissen.
Sind bei hinreichender Größe die höchstwertigen Bits nicht auch
ohne Padding so verteilt?

Mir ist noch aufgefallen, dass IPsec zufälliges Padding benutzt.
Würde das heißen das auch IPsec in Verbindung mit MD5 nicht mehr zu trauen ist?

Naja, jedenfalls ist es seit '94 endlich mal wieder jemanden aufgefallen ;-)

Mit http://www.rtfm.com/md5coll.tar.gz lässt sich die Geschichte mal praktisch
angucken.

..highKO..

[highKO Moye]

Post by highKO Moye

Post by Lutz Donnerhacke
;-) Ich habe es mir erstmal in Ruhe angesehen.
...
Es schaut so aus, als ob man einen Fehler in der Behandlung der
höchstwertigen Bits der Statusvariablen gefunden hat (Überträge heben sich
einfach raus), indem man das Hineinrollen dieser Bits geschickt ausmaskiert
und somit ein Gleichungssystem in n¹ bit bekommt...
Wenn man also kein Protokoll benutzt, daß zufälliges Padding direkt vor der
Hashfunktion benutzt, ist man fein raus...

Was macht den Content vorm hashen ohne zufälliges Padding denn besser?
Hier fehlt mir irgendwas an Wissen.

Vielleicht sollte man dann statt mit Zufällen einfach mit absichtlich
berechenbaren Bitfolgen auffüllen?
Klingt irgendwie unlogisch, kann mal einer von meiner Leitung runtersteigen?

..highKO..