Rainbow-Tables in eigener Sache ...

[Hackse]

Hallo @all,
prinzipiell ist mir die Funktionsweise von Rainbow-Tables bis auf eine Sache klar.

Ich habe einen Algorithmus entwickelt um Rainbow Tables zu generieren und bin nun dabei die Suche des bekannten Hashes innerhalb des Rainbow-Tables zu programmieren.

Ich zitiere mal folgende Seite: http://kestas.kuliukas.com/RainbowTables/

The algorithm is:
1) Look for the hash in the list of final hashes, if it is there break out of the loop.
2) If it isn't there reduce the hash into another plaintext, and hash the new plaintext.
3) Goto the start.
4) If the hash matches one of the final hashes, the chain for which the hash matches the final hash contains the original hash.

... und auch das ist klar. In der Praxis ist es nun so, dass ich für eine Chain mit 10.000 Hashes auch 10.000 verschiedene Reduktionsalgorithmen verwende. Daher stelle ich mir die Frage, mit welchem Reduktionsalgorithmus ich den zu findenden Hash reduzieren soll? Gäbe es nur einen Reduktionsalgorithmus, wäre das alles kein Problem, aber man möchte ja Kollisionen vermeiden und verwendet daher für jede Spalte einen eigenen Algorithmus.

Greetz
Hackse

 

[Elderan]

Hallo,
für jeden einen eigen Reduktionsalgorithmus zu nutzen macht keinen Sinn. Nutze einen Algorithmus. Mit Kollisionen musst du leben.

Sprich:
In deiner Rainbowtable steht:
hash(red(hash(red(hash(red(hash(....red(Start1)....)
hash(red(hash(red(hash(red(hash(....red(Start2)....)
hash(red(hash(red(hash(red(hash(....red(Start3)....)
....

Das es dabei zu Kollisionen kommen kann ist nunmal so und eigentlich kein Problem.

 

[Hackse]

Hallo Elderan,
warum die statistische Wahrscheinlichkeit auf Kollisionen derart immens erhöhen? Ich sehe den Vorteil nicht. Bitte um Erläuterung.

Greetz
Hackse

 

[Elderan]

Hallo,
wenn du 10 000 verschiedene Reduktionsalgorithmen verwendest, wie kannst du dann ausschließen, dass diese keine Kollisionen produzieren?
Die Wahrscheinlichkeit ist die selbe.


Sagen wir f ist ein Reduktionsalgorithmus, dieser geht doch von:
f: {0,1}^128 -> {a,b,c,...,0,1,...,9}^8

Also f bildet einen 128 bit String auf ein 8 stelliges Wort aus a-z,0-9 ab.


Wenn man nun noch ein g hat:
g: {0,1}^128 -> {a,b,c,...,0,1,...,9}^8


Dann ist die Wahrscheinlichkeit, dass f(m) = f mit n != m die selbe wie f(m) = g, sofern f und g Random Oracles sind.

Dass eine Kollision bei hash() Auftritt ist mehr als unwahrscheinlich, bei guten Hashalgorithmen. BeiMD5 hat man beispielsweise auch versucht per Brute Force eine Kollision gefunden, und trotz enormer Rechenpower hat man es nicht geschafft.


Durch mehrere Reduktionsalgorithmen gewinnt man nichts, man macht alles nur komplizierter.

 

[Hackse]

Original von Elderan
Hallo,
wenn du 10 000 verschiedene Reduktionsalgorithmen verwendest, wie kannst du dann ausschließen, dass diese keine Kollisionen produzieren?
Die Wahrscheinlichkeit ist die selbe.
(...)

Dann ist die Wahrscheinlichkeit, dass f(m) = f mit n != m die selbe wie f(m) = g, sofern f und g Random Oracles sind.

Hallo Elderan,
für jede Chainspalte wird ein anderer Reduktionsalgorithmus verwendet. Sei N die Anzahl der Chainspalten und s eine Funktion, die innerhalb einer Chain die aktuell zu verarbeitende Spaltenzahl ausgibt, dann hat f(m) = f mit n != m nur genau dann die selbe Eintrittswahrscheinlichkeit wie f(m) = g, wenn zusätzlich die Bedingung s(f[1]) = s(f[2]) erfüllt ist. Dies ist ein weiteres Kriterium, das die Wahrscheinlichkeit einer Kollision verringert.

In Worten:
Verwende ich nur einen Reduktionsalgorithmus, dann tritt eine Kollision genau dann auf, wenn ich an irgend einer Stelle der Rainbow-Table zwei verschiedene Hashes auf ein und denselben Klartext reduziere. Die Funktion wäre damit nicht mehr injektiv.
Verwende ich jedoch spaltenweise verschiedene Reduktionsalgorithmen, dann könnte eine Kollision nur dann auftreten, wenn ich in zwei Chains jedoch in genau der selben Spalte der Rainbow-Table zwei verschiedene Ciphers auf ein und denselben Klartext reduziere. Bei 10.000 Iterationen ist das Ganze somit sehr viel unwahrscheinlicher (Faktor 10.000).

Dass unter der Verwendung verschiedener Reduktionsalgorithmen und verschiedenen Ciphers in verschiedenen Spalten dennoch gleiche Ergebnisse resultieren können, sprich f(x) = g mit x != y und s1 != s2, würde zu keiner Kollision führen, da unter der Verwendung verschiedener Reduktionsalgorithmen der weitere Chainverlauf unterschiedlich wäre, d.h. die Folgeglieder n wären wieder unterschiedlich: n(f(x)) != n(g) mit x != y und s1 != s2

Greetz
Hackse

 

[Elderan]

Hallo,

Ergebnisse resultieren können, sprich f(x) = g mit x != y und s1 != s2, würde zu keiner Kollision führen, da unter der Verwendung verschiedener Reduktionsalgorithmen der weitere Chainverlauf unterschiedlich wäre,

Okay da hast du recht. Die Kollisionswahrscheinlichkeit der Reduktionsfunktion für einen Hashwert wäre die selbe, aber der weitere Verlauf bzw. die weitere Produktion der Wörter wäre verschieden.


Allerdings kommt da dann deine ursprüngliche Frage wieder ins Spiel:

Daher stelle ich mir die Frage, mit welchem Reduktionsalgorithmus ich den zu findenden Hash reduzieren soll

Antwort: Man müsste alle Startpositionen ausprobieren. Bei einer Chain Länge von 10 000 also 10 000 Startpositionen.

Man muss eben abwegen was man benötigt. Dies erhöht natürlich den Aufwand für das Heraussuchen des Hashwertes.

Man könnte auch über weniger Reduktionsalgorithmen nachdenken, beispielsweise über nur 100 oder 1000. Die man dann immer nacheinander verwendet.