[HaBo]

Nimda05

Anzeige

Hallo!

Ich code gerade an einem Programm dass per Aufruf einen MD5 Hash übergeben bekommt und dann guckt ob dieser Hash in einer MySQL Datenbank vorhanden ist und bei Erfolg den Plaintext zurückliefert.
Da das ganze aber bei ein paar Millionen Einträgen ziemlich groß wird frage ich mich wie man das ganze beschleunigen kann.
1. Wie kann man also so eine MySQL Datenbank beschleunigen?
Ich habe dabei 3 Spalten: ID, Plaintext und Hash

2. Lohnt es sich 16 Tabellen zu machen in denen dann die Hash nach Anfangsbuchstaben geordnet sind (aus sicht der Geschwindigkeit)?
Also ein Hash der mit 'a' beginnt wird in Tabelle a geschrieben bzw in Tabelle a wird geguckt ob der Hash dadrin steht.

Ich hoffe Ihr könnt mir helfen

Nimda05

2Bios

Ich würde den MD5-Hash als ID verwenden. Dann geht das mit dem Zugriff deutlich schneller.

mauralix

Für diesen Zweck gibt es sowieso schon Rainbowtables. Aber ist vielleicht ja nur ein Übungsprojekt.

__________________

http://chm0815.blogspot.com

bitmuncher

Wenn er das tut, muß er bei mehreren Gigabyte Hashes auch einberechnen, daß er genauso viel RAM braucht, wie alle Hashes zusammen groß sind. Schließlich wird der Tabellenindex (die MYI-Datei) beim Zugriff auf die Tabelle komplett in den RAM geladen. Deswegen sollte man (wenn möglich) INTs als Index nutzen.

Ich denke daher, daß es schon sinnvoll sein kann, wenn man für jedes Anfangszeichen eine eigene Tabelle nutzt, so daß die Tabellen dadurch kleiner werden. Alternativ nutzt man ein NDB-Cluster um somit die Queries entsprechend aufteilen zu können. Macht aber nur Sinn, wenn mehrere Queries gleichzeitig ausgeführt werden müssen, da ein Query oder eine Transaction immer auf einem Node läuft.

__________________

Nimda05

Ich kenne Rainbowtables. Habe selbst über 300GB inzwischen.
Ich will das ganze aber net mit RTs machen. Zumindest noch nicht. Erstmal muss das ganze mit "Wordlisten"/RTs in ner MySQL laufen.
Das andere ist mir zu einfach

Elderan

Hallo,
warum greifst du den Gedanken/die Funktionweise von Rainbowtables nicht für deine DB auf?

Nimda05

Naja mache ich ja quasi.
In der Datenbank habe ich wie gesagt 3 Spalten. 1. Eine eindeutige ID für jeden Hash 2. den Plaintext 3. den Hash.

Wenn du jetzt meinst warum ich nicht "richtige" Rainbowtables generieren lasse ist das relativ einfach zu erklären: 1. Ich will das so machen 2. Ich kapier das verfahren zum RTs generieren nicht und 3. das dauert idR ne kleine ewigkeit

Elderan

Hallo,
also das Prinzip von Rainbowtables ist relativ einfach, findet man bei Google auch genug.

Du hast einen Startwert x (z.B. 'Hallo Welt').
Dann in deiner DB würdest du ja x und H(x) abspeichern (H(x) ist die Hashfunktion).

Dies geht aber deutlich effektiver, indem man z.B.:

x und H(H(x)) abspeichert.
Der User gibt eine Hashwert ein, dann guckst du, ob dieser in der DB ist. Wenn dies nicht der Fall ist, berechnest du davon den Hashwert und schaust ob er in der DB ist.
So könnte man mit dem Datensatz x|H(H(x)) zwei Hashwerte finden, einmal der für 'Hallo Welt' und dann nochmal das Ergebnis von H('Hallo Welt').

So nun sind aber "zufällige" 16-Byte folgen recht unattraktiv, so dass man folgendes Abspeichert:

x und H(G(H(x)))

Das G(x) erstellt aus den 16-byte input eine neue Zeichenkette/Passwort, die für dein Cracker intressant ist, z.B. eine 8 zeichen Lange (a-z) Eingabe, oder evt. eine andere Kombination aus der Wörterliste.

H('Hallo Welt') = 012345[... ein Hashwert]
G(H('Hallo Welt')) = Eisenbahn
H(G(H('Hallo Welt'))) = H('Eisenbahn') = abcdef[ein Hashwert]

Gespeichert wird:
Hallo Welt:abcdef...

So der User sucht nach:
012345...

Der Cracker schaut nach, ob 012345... in der DB vorkommt, wenn nicht wird G(x) auf die Eingabe angewendet (woraus 'Eisenbahn' resultiert) und dann davon der Hashwert gebildet, woraus dann abcdef... resultiert.
Dann wird wieder geschaut, ob abcdef... in der DB vorkommt, dies ist der Fall, und zwar mit dem Startwert 'Hallo Welt'.


Der nächste User sucht nach abcdef..., dieser kommt auch in der DB vor, mit dem Startwert 'Hallo Welt'.
Da aber abcdef... und 'Hallo Welt' nicht zusammen passen, wird:
G(H('Hallo Welt')) = Eisenbahn berechnet, und schon hat man den Hashwert.


So würdest du ca. die Hälfte an Platz sparen, aber es geht noch weiter.

Eine Rainbowtable benutzt pro Satz (Startwert + Endwert) nicht nur H(G(H(x))) sondern wendet dieses z.B. 40 000 mal an.
Um einen Hash in der Datenbank zu finden, muss man dann im Schnitt 20 000 mal (max. 40k) die Funktion H(G(x)) anwenden.
Dann findet man den entsprechenden Datensatz, und bildet dann vom Startwert aus H(G(x)) solange, bis das Ergebnis mit der Suche zusammen passt, und dass G(x) ist der zugehörige Klartext.

Dies ganze nennt man auch Time-Memory-Tradeoff. Je öfter man H(G(x)) anwendet, desto kleiner werden die Tabellen, aber desto Länger braucht man um 1 Hash zu finden und eben anders herum.


Hier noch nen paar Links:
http://en.wikipedia.org/wiki/Rainbow_table
http://kestas.kuliukas.com/RainbowTables/

Nimda05

Joa hört sich schon sinnvoll an. möchte ich aber trotzdem nicht machen ;-)
ich werds aber vieleicht zu einem späteren zeitpunkt mal ausprobieren!

aber um nochmal zu meiner lösung zurückzukommen: wie kann ich denn die geschwindigkeit optimieren? ich hab irgendwann mal das stichwort "index" aufgeschnappt... gibt es weitere möglichkeiten? Also es geht dabei um so 10-100Mio Einträge

bitmuncher

Wichtig ist hierbei am ehesten die Konfiguration der Datenbank um das ganze zu beschleunigen und die Art der Abfrage. Transactions z.B. werden etwas schneller abgearbeitet, verbrauchen aber mehr Speicher. Wenn der DB-Server ca. 8-12 GB RAM hat, dürfte es hilfreich sein die Buffer der DB hochzudrehen (key_buffer, max_allowed_packet, table_cache, thread_cache auf jeweils 2GB oder mehr). Wenn du InnoDB nutzt (die übrigens performanter ist als MyISAM), sollte die innodb_buffer_pool_size hochgedreht werden. Solltest du nicht soviel RAM haben, sorge wenigstens dafür, daß die Buffer-Größen + Größe der Index-Datei den RAM optimal füllen. Er sollte nicht überfüllt werden, damit kein Auslagerungsspeicher auf der Festplatte genutzt wird.

__________________

Elderan

Hallo,
zur Performance gibts verschiedene Möglichkeiten:
Du kannst aus dem 128-Bit-Hash eine 32-Bit Zahl machen, und diese speichern. Dieses Feld ist dann ein Index, sprich schneller Datenzugriff.

Oder alternativ die ersten paar Bytes des Hashs (z.B. die ersten 4 Bytes=32Bit) als Index festlegen.
So hälst du die Index-Tabelle klein (bei 10 Mio. Einträgen ca. 40 MB), hast dennoch den sehr schnellen Zugriff.

Die ganzen 128-Bit als Index zu verwenden, wäre unsinnig.

Und hoffentlich ist dir klar, den Hash nicht in Hexform abzuspeichern, sondern als Bytes.