MD5 Hash "zurückrechnen"

[everdream]

Hallo Liebe Delphi Gemeinde,

Ich habe mir für heute vorgenommen ein kleines Programm zu schreiben, das einen MD5 Hash "zurückrechnet". Ich hab' via Suchfunktion schon einige Threads gefunden, in denen Fragen zu diesem Thema gestellt wurden, allerdings habe ich noch nicht alles zusammen, was ich brauche.

Das Programm soll (rekursiv) jede mögliche Zeichenkombination in einen Hash umrechnen und ihn dann mit dem vorgegebenen vergleichen. Bei Übereinstimmung erfolgt dann die Ausgabe. Abbruchbedingung ist die Länge der Zeichenfolge.

Allerdings habe ich leider wenig Ahnung von Assambler und Co, weswegen ich keinen wirklich effizienten Umrechnungsalgo schreiben kann.
Kann mir jemand einen besonders schnellen Algo empfehlen (Code-Library?)?

Vielen Dank schonmal im Voraus!

lg, everdream

P.s: Ich werde mich wohl vorerst aus "A"-"Z", "a"-"z" und "0"-"9" beschränken.

[Dax]

Zwei Worte: UN MÖGLICH (hi Phoe ;) )

Was du vorhast, wird sehr sehr langsam und in den seltensten Fällen funktionieren. Allerdings wirst du auch mit Assembler deinen gewünschten Algorithmus nicht besonders beschleunigen können. In der Codelib gibt es zwar eine optimierte Methode, einen MD5-Hash zu berechnen (wenn auch mit Einschränkungen), und auch einen Permutationsalgorithmus haben wir, aber schon unter Annahme eines Zeitverbrauchs von 10 µs pro String-Hash brauchst du für alle Strings der Länge genau 6 schon 6,5 Tage.

[mkinzler]

Das Wesens eines Hashalgorithmuses ist ja gerade, daß er bicht umkehrbar ist.

[everdream]

Okay, soweit hatte ich nicht gerechnet.

Dann würde ich vielleicht mal einen Gedanken weiterverfolgen, den ich zu Anfang hatte:
Ein Programm schreiben, das Hashs berechnet und archiviert (alphabetisch sortiert, jeweils mit dem string dahinter, aus dem es erzeugt wurde).
Das müsste dann erst einige zeit laufen, und ich müsste mal eine meiner Partitionen für die Datenbank frei machen, aber wenn ich genug Zeit und Speicherplatz habe, bereitstelle, dann müsste es mir doch möglich sein auch Hashs mit 6 oder mehr Stellen zu identifizieren.

Zugegebenermaßen sehr umständlich, vor allem, weil meine Kenntnisse zum Speichern von Daten grade bis zur textdatei reichen -.-

[mkinzler]

Du wist aber schon das Hashfunktionen nicht eineindeutig sind?

[everdream]

Ja, aber wenn bei den wenigen Zeichen wirklich mal ein Hash auf mehrere Zeichenfolgen zutrifft, dann kann man ja aus denen auswählen.

[WordsBG]

Wenn ich mich mal nicht täusche ist so ein md5 String 32-stellig in Hex geschreiben. Damit hätten wir um einen String in einer Datei zu speichern schon mal 32 Byte. Dann speichern wir den String aus dem er kommt und dahinter ein #0 um das Ende zu siganlisieren. Das wären bei sehr kurzen Strings von durchschnittlich 8-Char also insgesammt 41 Byte pro MD5-Wert. Nun gibt es aber 32^36 MD5-Strings (36 = a bis z (26) + 1 bis 0 [über 9] (10)). Damit bräuchten wir (32^36)*41 Byte im Durchschnitt. Das wären 6.283231718 * 10^55 wenn mich mein Schultaschenrechner nicht täuscht. Wenn wir das im GB umrechnen (/ 1024 / 1024 / 1024) sind das immerhin noch 5.85171554 * 10^46, also eine Zahl 47-stellige Zahl. Ich weiß ja nicht wie groß deine Festplatte ist, aber meine würde das nicht schaffen. Eventuell könnte man da auch mit Kompression ran, aber auch bei großzügigen 80% Kompression oder gar mehr wäre es nicht möglich das zu speichern denke ich.

edit: ups, es ist natürlich 36^32, womit die Ergebnisse sich natürlich ändern, aber dennoch überdimensioniert sind.

[everdream]

Man könnte eventuell noch Platz sparen, indem man das Trennzeichen und den String dahinter weg lässt. Dann müsste man zwar die komplette Datei durchsuche, aber man würde erstmal ne Menge Platz sparen. Zudem könnte man sich ja vorerst auf 5-6 Stellen beschränken. Dazu dann noch Kompression, dann wäre es zumindest im rahemn des Möglichen.

Allerdings weiß ich auch nicht wie lange die Speicher/Kompressionsprozesse dauern, das wäre dann wieder ein Problem.
Weniger Speicher -> mehr Zeit, warum muss die Welt so logisch sein?!

[Apollonius]

Vergiss es. Wie eben festgestellt, brauchen die Hashs den meisten Platz, und selbst mit einer Kompression, bei der du 90% einsparst, hast du dann immernoch eine 45-stellige GB-Zahl.

[everdream]

Naja gut, jetzt weiß ich wenigstens, warum man auf so vielen Pages ein Passwort mit 8 oder mehr Stellen wählen muss :wink:

Trotzdem Danke für die fachmännische Beratung :-D


-> Jetzt brauch' ich ne neue Aufgabe!

[moritz]

Ich habe mich selber mal mit dieser Thematik beschäftigt, wie sicher ist md5, etc. Gibt es eine Möglichkeit zurückzurechnen, ...

2005 haben Chinesische Forscher erste Kollisionen im md5-Algorithmus gefunden, diese Forschungen wurden afaik allerdings nicht vertieft. (Siehe auch Wikipedia zu md5)

Der Ansatz, individuelle md5-Rückrechenversuche zu starten wurde afaik schon seit längerem verworfen, zur Zeit wird versucht, große Rainbow Tables aufzubauen.

Als Beispiel sei hier nur plain-text.info genannt.

Liebe Grüße,
Mo

[Dax]

WordsBG: ich widerspreche dir uns sage, dass es im Falle aller String der Länge 1 bis einschließlich 8 mit allen Zeichen a..z, A..Z, 0..9 (62 + 62^2 + 62^3 + 62^4 + 62^5 + 62^6 + 62^7 + 62^8)*41 Byte benötigt werden. Das wär dann "nur" noch eine siebenstellige Zahl, gemessen in Gigabyte.

[Thorben_Ko]

Egal welche Zahl nun stimmt, beide überschreiten die leistungen eines Home PC bei weitem :)

Also diese Idee musst du wohl oder über aufgeben

[everdream]

Mir ist grade noch eingefallen, dass ich - glaube ich - irgendwo mal gelesen hab, jemand hätte es hinbekommen ein Programm zu schreiben, das aus nem Hash den Ausgangsstring berechnen kann, sofern die Länge dieses Strings bekannt ist. Kann das sein?!

[Torpedo]

Zitat:

Zitat von everdream

Mir ist grade noch eingefallen, dass ich - glaube ich - irgendwo mal gelesen hab, jemand hätte es hinbekommen ein Programm zu schreiben, das aus nem Hash den Ausgangsstring berechnen kann, sofern die Länge dieses Strings bekannt ist. Kann das sein?!

Soweit ich weiß ist es unmöglich den String zu berechnen. Das ist glaube ich sogar mathematisch bewiesen. Also stimmt das was du gehört hast wohl nicht. Wenn man aber die Länge weiß, muss man nicht mehr so viele Möglichkeiten ausprobieren, was aber z.B. bei einem Passwort mit 10 Zeichen immer noch viel zu lang dauern würde.

[everdream]

hm, schade xD

[arbu man]

Zitat:

Zitat von everdream

Mir ist grade noch eingefallen, dass ich - glaube ich - irgendwo mal gelesen hab, jemand hätte es hinbekommen ein Programm zu schreiben, das aus nem Hash den Ausgangsstring berechnen kann, sofern die Länge dieses Strings bekannt ist. Kann das sein?!

Wenn man davon ausgeht, dass ein PW selten länder ist als 20 Zeichen, müsste man dieses Programm nur 20mal ausführen und man hätte das PW geknackt. Das wäre ja schön...

mfg, Björn

[Cyberbob]

Zitat:

Zitat von everdream

Mir ist grade noch eingefallen, dass ich - glaube ich - irgendwo mal gelesen hab, jemand hätte es hinbekommen ein Programm zu schreiben, das aus nem Hash den Ausgangsstring berechnen kann, sofern die Länge dieses Strings bekannt ist. Kann das sein?!

Das Zauberwort hierfür lautet "Rainbow-Tables". Das sind tabellen, die aus dem MD5-Hash eine Zeichenfolge wiedergeben, die dem Hash gleichgesetzt ist. Damit ist es aber nicht möglich, das genaue Passwort oder was auch immer zu berechnen. Du erhälst nur einen String, der den selben Hash hat.
In der PC-Welt war vor einiger Zeit mal Artikel über dieses Verfahren, war ganz Interessant.

[Khabarakh]

Zu Rainbow-Tables gab es auch vor Kurzem einen Post bei CodingHorror - inklusive 110 Kommentare :mrgreen: .

[BUG]

Hi,

Es gibt sogar eine MD5-Mata-Suchmaschine: http://md5.thekaine.de/.

MfG,
Bug

[everdream]

wow, das teil leistet ja schon einiges... an mein PW ist es zum glück nich ran gekommen ^.^

[mkinzler]

Zitat:

Zitat von everdream

wow, das teil leistet ja schon einiges... an mein PW ist es zum glück nich ran gekommen ^.^

Dein Passwort wirst du damit auch nicht ermittlen können, höchstens ein anderes, welches den selben Hash generiert.

[everdream]

Zitat:

Zitat von mkinzler

Dein Passwort wirst du damit auch nicht ermittlen können, höchstens ein anderes, welches den selben Hash generiert.

Bei den anderen Wörtern, die ich gehasht versucht hab, hat das Programm immer genau das Wort zurück gegeben. Ich glaube auch nicht, dass es innerhalb der Zeichenkombinationen mit wenigen Zeichen so viele gibt, die den selben Hash erzeugen.

[mkinzler]

Zitat:

Ich glaube auch nicht, dass es innerhalb der Zeichenkombinationen mit wenigen Zeichen so viele gibt, die den selben Hash erzeugen.

Kommt auf die Länge des passworts und die Güte des Hash-Algorithmuses an.

[everdream]

Zitat:

Kommt auf die Länge des passworts...

Dazu:

Zitat:

Zeichenkombinationen mit wenigen Zeichen

Zitat:

...und die Güte des Hash-Algorithmuses an.

Und das Thema war ja der MD5 Hash.

[Nuclear-Ping]

Vor 'ner Weile habe ich mal mit 'nem Kumpel versucht, nen Kompressionsverfahren zu entwickeln, was eben auf Hashes basiert. Die Kompression war relativ simpel. Was unmöglich war, war die Dekompression ... Wenn du dir das Hirn verrenkst, kannst du (wenn du ein paar nötige Informationen mitspeicherst) 1-2 Byte wiederherstellen, aber sonst ... Jedenfalls haben wir's dann auch nach 'ner Woche wieder in die Schublade gesteckt ... War aber trotzdem n lustiger Versuch ... :mrgreen: