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

[glkgereon]

Zitat von 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.

Aua.
Dann denke ich ausnahmsweise mal nach...und dann sowas^^
is ja klar, denn 2^128 + 2^896 ist ja nicht 2^1024 sonder es muss eben * sein...und damit gibt es für jeden wiederum 2^896 kollisionen

[negaH]

Anders ausgedrückt:

Es ist mathematisch hinfällig eine Hashfunktion zu Brute Forcen, denn es läuft immer darauf hinaus das man ein Inputset brute forcen muß indem man von jedem solchen Input den Hashdigest berechnet und diesen mit dem vorhandenen Digest vergleicht. Eine Hashfunktion ist quasi mathematisch ein "Durchlaufposten". Diese Betrachtungsweise gilt zumindestens so lange wie man einen ganz spezifischen Input 1 zu 1 finden möchte. Allerdings besteht eben das Problem eines realen Informationsverlustes wenn man zb. die Menge aller möglichen 1024 Bit Inputs auf diese Weise Brute Forcebn möchte. Denn 2^1024 mögliche Inputs können einfach nicht eineindeutig auf 2^128 mögliche Outputs gemappte werden. Es gehen dabei 896 Bits an Informationen verloren, ins Nirwana, sie lösen sich in Rauch auf.

D.h. sollte der gesuchte Input größer 128 Bits sein dann ist es mathematisch beweisbar das man ausgehend von einem 128 Bits Digest niemals exakt diesen Input reproduzieren kann. Je größer der Input wird desto mehr Kollisionen treten auf, um so mehr muß in der Differenzierung dieser Kollisionen auf igendwelche anderen Mittel zurückgegriffen werden um die fehlenden Informationen wieder herstellen zu können. Ist der Input theoretisch eine unendlich große Menge so wird dieser Informationsverlust auch unendlich groß sein, bzw. eben nur 2^128 mal kleiner als unendlich.

Gruß Hagen

[negaH]

Anders ausgedrückt:

Es ist mathematisch hinfällig eine Hashfunktion zu Brute Forcen, denn es läuft immer darauf hinaus das man ein Inputset brute forcen muß indem man von jedem solchen Input den Hashdigest berechnet und diesen mit dem vorhandenen Digest vergleicht. Eine Hashfunktion ist quasi mathematisch ein "Durchlaufposten". Diese Betrachtungsweise gilt zumindestens so lange wie man einen ganz spezifischen Input 1 zu 1 finden möchte. Allerdings besteht eben das Problem eines realen Informationsverlustes wenn man zb. die Menge aller möglichen 1024 Bit Inputs auf diese Weise Brute Forcebn möchte. Denn 2^1024 mögliche Inputs können einfach nicht eineindeutig auf 2^128 mögliche Outputs gemappte werden. Es gehen dabei 896 Bits an Informationen verloren, ins Nirwana, sie lösen sich in Rauch auf.

D.h. sollte der gesuchte Input größer 128 Bits sein dann ist es mathematisch beweisbar das man ausgehend von einem 128 Bits Digest niemals exakt diesen Input reproduzieren kann. Je größer der Input wird desto mehr Kollisionen treten auf, um so mehr muß in der Differenzierung dieser Kollisionen auf igendwelche anderen Mittel zurückgegriffen werden um die fehlenden Informationen wieder herstellen zu können. Ist der Input theoretisch eine unendlich große Menge so wird dieser Informationsverlust auch unendlich groß sein, bzw. eben nur 2^128 mal kleiner als unendlich.


Praktisch gesehen heist das:

Will man mit einer 128 Bit Hashfunktion ein Passwort schützen so gilt:

1.) Passwort sollte 128 Bit groß sein
2.) ein Zufallssalt von 128 Bit sollte vor dem hashen hinzugefügt werden

Der Input zur Hashfunktion besteht also aus 256 Bits und wird durch diese auf 128 Bit Digest reduziert. Zu einem der 128 Bit Passwörter gibt es also 2^128 Möglichkeiten ein Salt zu erzeugen. Das bedeutet aus Sicht des Angreifers das die Wahrscheinlichkeit zwischen Salt und Passwort exakt 50% ist, er kann also nicht mehr differenzieren was er nach einer Brute Force Attacke vor sich hat: Passwort oder Salt, oder 50% Bits vom Passwort und 50% Bits vom Salt, oder 50% Bits von einem spezifischen aber falschen Salt und 50% Bits eines falschen Passwortes.

Jede weitere Vergrößerung vom Passwort oder eben Salt erhöht nun nur noch den Rechentechnischen Zeitaufwand aber nicht mehr die effektive Sicherheit. Will man also MEHR reale Sicherheit dann geht dies nur indem man eine größere Hashfunktion benutzt. Die Hashfunktion ist also ein "Durchlaufposten" dessen Bitgröße aber als "Flaschenhals" eine eventuell größere Sicherheit eines größeren Passwortes reduzieren kann aber real bei einem kürzeren Passwort niemals erhöhen kann (wo nichts ist kann eine Hashfunktion auch nichts sicherer machen). Die letzendliche Sicherheit definiert sich also immer wieder aus dem Passwort. Die Hashfunktion könnte nur unter Umständen die Sicherheit negativ beeinflussen wenn sie kürzer als das Passwort ist.


Gruß Hagen

[generic]

rsa mit 128 bit ist unüblich. meist werden schlüssel mit 1024/2048 bit genommen.

die 128 bit beziehen sich warscheinlich auf die verschluesselung die durchgefuehrt wird (z.B. AES).

mal ab - ich denke das rsa sowieso unsicher ist. die nsa wird sicherlich bereits alle primzahlen bis 2^4096 auf ihren clustern ausgerechnet haben.
somit ergibt sich das problem der primfaktoren zerlegung nicht. was bedeutet das jeder private key ausgerechnet werden kann.
stand neulich nicht bei heise das die 42. mersennsche prim.zahl gefunden wurde (2^24036583 -1)?

[negaH]

@generic:

Zitat:

rsa mit 128 bit ist unüblich. meist werden schlüssel mit 1024/2048 bit genommen.

die 128 bit beziehen sich warscheinlich auf die verschluesselung die durchgefuehrt wird (z.B. AES).

mal ab - ich denke das rsa sowieso unsicher ist. die nsa wird sicherlich bereits alle primzahlen bis 2^4096 auf ihren clustern ausgerechnet haben.
somit ergibt sich das problem der primfaktoren zerlegung nicht. was bedeutet das jeder private key ausgerechnet werden kann.
stand neulich nicht bei heise das die 42. mersennsche prim.zahl gefunden wurde (2^24036583 -1)?

1.) es geht hier nicht um RSA
2.) AES arbeitet minimal mit 128 Bit Schlüsseln, kann aber 192 und 256 Bit Schlüssel benutzen
3.) RSA ist ansich als mathematisches Problem sehr wohl absolut sicher, bisher ist nur ein Weg bekannt RSA mathematisch zu knacken, die Primfaktoerzerlegung des public Moduls N. Es gibt defakto keinen mathematischen Algorithmus der vom Aufwand her effizienter dieses N faktorisiert als es ein solches N zu produzieren. Dieses "Ungleichgewicht" ist die primäre Trapdoor Funktion eines RSA und macht es mathematisch sicher.Denn technisch praktisch egsehen bedeutet dies das man die Primzahlengröße = Größe des Modules N einfach nur so groß setzen muß das einerseits die Erzeugung eines Moduls N technisch möglich bleibt andererseits aber deren Zerlegung praktisch unmöglich wird.
4.) PI(x) ist definiert als Pi(x) = x / log(x) und bestimmt die angenährter Anzhal der Primzahlen bis X.

PI(x) von Pi(2^4096) ist also rund

36785 51415 95294 63154 94562 21540 84372 51184 19829 16666 68366 74019 16920 20756 56909 71330 72358 23102 58931 01831 40546 15326 88230 10512 35569 58240 20235 75303 08238 76475 27238 69636 89768 90769 59797 31751 14115 43499 10651 80181 85934 46800 59767 14330 94162 00881 03176 69956 97291 14039 54014 56601 42244 21610 42211 66838 66981 22301 58924 82384 56387 46249 12765 31373 03212 11148 09726 80820 32790 68575 46291 01339 61045 35650 29730 23481 01702 30768 87318 24681 23301 08856 97847 09885 28826 35074 34927 54803 57571 55310 28871 36623 10660 84644 23754 41631 70795 33019 59386 08376 61086 07867 38223 66260 24290 49039 00972 39514 32366 28921 88556 87671 42786 07604 72930 38848 77878 45027 28494 43784 63161 84094 01848 74645 55841 72602 12808 40280 96276 50967 36573 01674 31864 87545 49933 87935 23898 98211 32963 95547 67555 98243 04784 57479 28096 36582 74784 24650 11638 62329 25473 71892 39027 01816 89392 47580 99387 66315 60178 55756 86894 33294 69692 21310 35840 29406 12514 81593 11446 94222 82894 13334 47110 73608 59959 77080 32859 92413 55883 55634 26704 14542 46113 76988 36264 50092 70721 17157 34172 63238 83225 81614 78292 71352 65333 61001 44173 95974 75428 18236 79482 77256 96525 36436 56476 58986 71973 88539 13303 40540 65687 67270 00469 89111 01349 16040 32028 48318 76641 00673 76403 86019 41274 77778 56648 07453 62433 53267 71261 58011 21786 69852 48730 12156 64265 85793 42656 40561 83416 98002 32613 01774 83727 13408 29733 02784

Wir benötigen durchschnittlich 2048 Bits für jede dieser Primzahlen um sie zu speichern. Das wären also 256 Bytes an Speicher pro Primzahl.

Der NSA benötigt also minimal 94 17091 62483 95425 67666 07927 14455 99363 03154 76266 66671 01885 48907 31573 13681 68886 60665 23707 14262 86340 68839 79815 23681 86906 91163 05813 09491 80352 77589 09123 77669 73106 27045 80840 37017 08113 28292 13551 35771 26861 26555 99223 80953 00388 68721 05474 25544 13235 08985 06531 94122 27728 89964 14519 32268 06187 10699 47193 09206 84754 90448 35190 39776 67920 31496 22300 53912 90062 90003 94415 55318 50499 42940 27611 26476 10940 11140 35790 76831 53471 18395 65078 67386 48857 30633 79545 79033 41452 29715 38317 59433 91069 75515 29176 68924 81130 57717 23604 53016 02837 44412 38036 14049 85257 62622 18365 53986 48933 15666 85770 04002 70560 43885 53235 46810 70179 45287 36883 26984 94576 08865 69431 28068 73279 09262 95481 86144 78951 11926 46786 47645 62692 28625 57408 11647 83073 11421 18139 42100 38772 60204 94331 50220 24851 14695 92669 65183 44767 10429 79487 56289 21272 04451 90916 65124 84473 80734 43241 76794 05710 73758 44949 23442 41206 55451 75115 27968 03792 87837 30417 21044 20898 13624 60348 43801 49701 32564 12140 57871 06190 42372 36261 22870 05125 09020 83712 23733 04619 92279 48193 89141 05808 93384 42934 66279 25404 16369 08533 69537 09614 68619 47589 77783 10493 27760 58007 00600 25314 66018 05671 78408 16044 21121 20292 12419 45385 06321 99291 69604 20097 72483 59388 20969 66343 11313 01907 08127 82984 36534 42964 50871 77394 82236 74911 12100 52059 63117 20039 83829 54746 88595 48932 54358 34146 32524 11655 12704

Bytes an Speicher um das machen zu können was du behauptet hast.
Aber selbst wenn man eine solche Speichergröße zur Verfügung hätte bliebe das Problem das man erstmal alle Primzahlen bis 2^4096 berechnen müsste. Obige erste Zahl nimmst rechnest du nun / 1000 Millisekunden / 60 Sekunden / 60 Minuten / 24 Stunden / 365 Jahre, dann hast du die Zeit in Jahren die man benötigen würde wenn man 1000 der Primzahlen pro Sekunde berechnen könnte. In dieser Zeit sind schon mehrere Universen kollabiert, ein neuer Urknall und schon wieder kollabiert. Und falls du dich entscheiden solltest das ganze Silizium des Universums zu benutzen um damit viele Rechner zu bauen, dann würde
a) das denoch nicht ausreichen
b) der Stromverbrauch pro Sekunde dieser Rechner mindestens so hoch sein wie unsere Sonne in ihrem ganzemLeben produziert
c) die Masse dieser Rechner mehrere Schwarze Löcher ergeben


5.) Mersenne Primzahlen zu erzeugen ist mathematisch viel viele, unendlich viel leichter, als normale Primzahlen von nicht spezieller Form. Nur deswegen kann man solche Rekorde aufstellen. Davon abgesehen sind aber jede spezielle Form einer Primzahl absolut unsicher im Sinne der Kryptographie (bis auf einige Ausnahmen). Mersenne Primzahlen taugen somit nichts in der Kryptographie. (Auch wenn man mit dem Mersenne Twister etc.pp. supergroße Zufallsgeneratoren aufbauen kann).

Gruß Hagen

[Nicolai1234]

Was soll denn überhaupt geknackt werden? Also wpher stammt das Passwort bzw. der Hash?

Wenn es ein Passwort ist, dass geknackt werden soll, kann man ja vielleicht auch mit einer Art Wörterbuch vorgehen...

[Zacherl]

Zitat:

das wird schon ab 8-9 zeichen, je nach verwendetem zeichensatz für "normale" PCs so extrem, das es jahre dauern kann

Also ich habe letzt einen 6 Zeichen langen MD5 Hash unter Einbezug von [a..z, 0..9, A..Z, !"§$%&/()=?_:;,.-] innerhalb von 3h gebruteforced ...

CPU: 3,66 Dualcore
RAM: 1024 MB

Florian

[DGL-luke]

Um noch einmal ganz profan auf die praxis zurückzukommen:

Wenn es darum geht, einen Kollisionsstring zu einem Hash zu finden, mit dem man z.B. ein Login knacken kann, ist es ganz und gar nicht hinfällig, per SQL injection den hash zu bekommen und per rainbow-tables einen kollisionsstring. Insbesondere bei Open-Source CM / Forumssystemen ist sowas sehr zielführend.:

SQL-Lücke suchen -> passwort-hashes rausholen -> kollisionsstring suchen -> voila.

[Micha88]

Zitat:

Wenn du wissen willst wie lange dein Rechner daran zu knabern hat dann Rechne mal:
340.282.366.920.938.463.463.374.607.431.770.000.00 0 Schlüssel hat die Verschlüsselung
Und hier findest du raus wieviel Mio keys\sec dein Rechner schafft.


Achja, dein Rechner darf auf keinen Fall weniger als 562.636.188.692.027.880.710.606.163.081.630Keys\se c schaffen um die Verschlüsselung nach einer Woche zu knacken.

Also mein Rechner schafft es circa 470.000 MD5-Kombinationen zu erzeugen und mit einem bestehendem MD5-Hash zu vergleichen. (eine einfache MD5.pas-Datei, nichts Spezielles)
Kurz gesagt.. um die obigen Schlüssel alle zu errechnen, dürfte man schon viele Jahre brauchen.