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

[jim_raynor]

Ihr verdreht ihr einiges. MD5 hat nichts mit RC5 zu tuen. Bei dem RC5 Projekt gibt es einen verschlüsselten String, der per Brute-Force entschlüsselt wird. Dabei hat der Schlüssel eine Feste länge (nämlich 72Bit). Bei MD5 wird ein Hashwert erzeugt, wobei dort die Eingabelänge variieren kann. theoretisch kann man auch einen 1 GB String per MD5 hashen. Das dauert aber dementsprechend lange. Es ist also überhaupt nicht vergleichbar.

P.S: Du kannst dir die Sourcecodes für die Entschlüsselung bei RC5 herunterladen. Aber ob man daraus wirklich schlauer wird. Ist alles hoch optimiertes Assembler für die verschiedenen Prozessoren.

[ripper8472]

Also ich meine MD5 und in dem Zusammenhang Hashes von Passwörtern, die man möglicherweise bruteforcen kann. Und ich persönlich suche auf Geschwindigkeit optimierte Implementationen von MD5.

[negaH]

260 Zyklen auf einem ASIC sind eigentlich kein Problem mit dem RC4/5 Algo. Es gibt weit performantere Algorithmen wie AES Rijndael zb. Überlicherweise implementiert man aber solche Brute Forcer nicht auf ASIC's oder RISC's sondern auf multiplen FPGA Systemen. Theoretisch kann dann eine FPGA Node in einer solchen Matrix innerhalb eines einzigsten Taktzyklus einen Schlüssel brute forcen. Die FPGA's werden meistens mit weit mehr als 100Mhz getaktet. Man kann also mit professionellen Systeme weit mehr als 100 Millionen Schlüssel pro Sekunde testen. Das Problem dabei ist aber immer das man sehr viel Manpower, Knownlegde und Geld investiren muß und das man in der FPGA Hardware immer nur einen ganz speziellen Brute Force Algorithmus programmieren muß. So bald sich nur 1 Bit verändert muß man alles erneut programmieren.
Den FPGA's kommt der Fakt zu gute das die modernen Verschlüsselungsalgorithmen wie zb. AES Rijndael vom Design her stark parallelisierbar sind und meistens nur mit simplem Boolschen Operationen arbeiten.

Gruß Hagen

[negaH]

Zitat:

Also ich meine MD5 und in dem Zusammenhang Hashes von Passwörtern, die man möglicherweise bruteforcen kann. Und ich persönlich suche auf Geschwindigkeit optimierte Implementationen von MD5.

Hier im Forum solltest du fündig werden. Im DoubleCheck Thread hatte ich glaube ich einen MD4/5 Algorithmus gepostet der durchschnittlich mit 250Mb/sec arbeitet. Er benötigt ca. 5.9 respektive 9.0 Taktzyklen pro Byte.
Anbei mal mein Source.

Gruß Hagen


Auszug aus "DECTest.test"

THash_MD2 : 261.3 cycles/byte 5.74 Mb/sec
THash_MD4 : 5.9 cycles/byte 252.53 Mb/sec
THash_MD5 : 9.0 cycles/byte 167.01 Mb/sec
THash_SHA : 21.0 cycles/byte 71.31 Mb/sec
THash_SHA1 : 20.7 cycles/byte 72.43 Mb/sec
THash_SHA256 : 47.2 cycles/byte 31.76 Mb/sec
THash_SHA384 : 86.1 cycles/byte 17.43 Mb/sec
THash_SHA512 : 88.0 cycles/byte 17.05 Mb/sec
THash_Sapphire : 55.0 cycles/byte 27.25 Mb/sec
THash_Panama : 8.1 cycles/byte 185.24 Mb/sec
THash_Tiger : 24.7 cycles/byte 60.81 Mb/sec
THash_RipeMD128 : 15.1 cycles/byte 99.08 Mb/sec
THash_RipeMD160 : 26.5 cycles/byte 56.63 Mb/sec
THash_RipeMD256 : 14.8 cycles/byte 101.69 Mb/sec
THash_RipeMD320 : 25.7 cycles/byte 58.31 Mb/sec
THash_Haval128 : 13.9 cycles/byte 108.01 Mb/sec
THash_Haval160 : 14.1 cycles/byte 106.43 Mb/sec
THash_Haval192 : 33.4 cycles/byte 44.95 Mb/sec
THash_Haval224 : 34.7 cycles/byte 43.28 Mb/sec
THash_Haval256 : 26.2 cycles/byte 57.23 Mb/sec
THash_Whirlpool : 98.9 cycles/byte 15.17 Mb/sec
THash_Whirlpool1 : 99.3 cycles/byte 15.10 Mb/sec
THash_Square : 46.4 cycles/byte 32.34 Mb/sec
THash_Snefru128 : 168.2 cycles/byte 8.92 Mb/sec
THash_Snefru256 : 250.0 cycles/byte 6.00 Mb/sec

[ripper8472]

Bin inzwischen auf ein paar Benchmarks gestoßen. Dort wird aber immer eine große Datenmenge gehasht und dann auf Cycles/Byte runtergerechnet. Wenn ich wirklich nur ein Byte hashen wollte, hat das sicher/leider keine 9 Cycles :(
Bin beim Suchen auf die ASM Sources von diesem Russen gestoßen. Mal sehn, ob ich da was draus machen kann.

Danke

[negaH]

Zitat:

Bin beim Suchen auf die ASM Sources von diesem Russen gestoßen. Mal sehn, ob ich da was draus machen kann.

Du meinst sicher Anatol, Spitzname Tol. Wenn ja, lass es und schaue dir meine Sourcen an, es sind Tol's Sourcen die er mit mir zusammen entwickelt hat, nur er hatte halt die Schweinearbeit :-)
Tol hat basierend auf dem alten DEC Part I seine Assembler-Optimierungen begonnen und dann von mir eine inoffizielle Version 4 von mir erhalten. Inzwischen habe ich aber obige Version 5.0 von Grund auf neu entwickelt und in diese mit einigen Änderungen Tol's Assemblersource integriert.

Gruß Hagen

[negaH]

Zitat:

..Cycles/Byte runtergerechnet. Wenn ich wirklich nur ein Byte hashen wollte, hat das sicher/leider keine 9 Cycles

Tja, das ist halt mal so. Du kannst ja versuchen es schneller als 9 Takte pro sekunde hinzubekommen, ich persönlich kenne aber keine andere Implementierung, egal ob in C, Assebler oder Pascal die schneller als Tol's Version ist. Die einzigste MD5 Implementierung die bei weitem Schneller ist die ich kenne wurde in VHDL bzw. Abel entwickelt. Das läuft aber nur auf FPGA's.

In deinem Falle würde ich dir raten MD5 ganz genau zu analysieren. Basierend auf dem Original Algorithmus würde ich an deiner Stelle nun versuchen einen sequentiellen Algorithmus zu bauen der die MD5 Funktionalität nur partiell ausführt. D.h. du könntest dann schon sehr frühzeitig mit sehr wenigen Operationen erkennen ob der Hash Digest sich in die richtige Richtung entwickelt.

Gruß Hagen

[ripper8472]

Zitat:

Zitat von negaH

In deinem Falle würde ich dir raten MD5 ganz genau zu analysieren. Basierend auf dem Original Algorithmus würde ich an deiner Stelle nun versuchen einen sequentiellen Algorithmus zu bauen der die MD5 Funktionalität nur partiell ausführt. D.h. du könntest dann schon sehr frühzeitig mit sehr wenigen Operationen erkennen ob der Hash Digest sich in die richtige Richtung entwickelt.

Uff, dazu bin ich nicht der Experte. Sowas hab ich mir auch schon vorgestellt, aber dann bin ich wieder zu faul, mir Gedanken zu machen. So wichtig ist mir die Sache nun auch nicht. Die original Implementation hat bei mir was um die 33 Zyklen pro Byte, über 100 MB gemessen. Aber sonst schaff ich nicht mehr als 450.000 Hashes pro Sekunde, wenn jeder über ~8 Zeichen geht. Hm, vll optimier ich es wirklich irgendwann... ;-)

[freaky13]

ich will nur noch kurz was anmerken wegen der Zeit: Brute Force Attacken

[glkgereon]

Zitat:

Zitat von negaH

Das bringt garnichts. Angenommen ich erzeuge aus verschiedenen Daten mit jeweils 1024 Bit Länge einen 128 Bit langen MD5 Hash dann gibt es pro Hash eben 2^1024 - 2^128 == 2^896 komplett verschiedene Eingangsdaten für jeden der 2^128 möglichen MD5 Hashs, sprich 2^896 Kollisionen. Und? welche der 2^896 möglichen Eingangsdaten ist dann die richtige zu deinem einen Hashwert ?

Auch wenn der Post schon was her ist :)

*MÖÖÖÖPPPP*

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?)

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.

Insgesamt sind es zwar alles kollisionen, doch auf den einen zu berechnenden wert bezogen sind nur ein 2^128stel der gesamten kollisionen relevant und werden als solche erkannt.