| Cryptography & Encryption Ver- und Entschlüsselung, Algorithmen, Kryptoanalyse ? Kryptographie in der Praxis. Blowfish, Triple-DES, XOR u.a. |
Diskussion: Rainbow-Tables in eigener Sache ... im Forum Cryptography & Encryption, in der Kategorie Security Area; Hallo @all, prinzipiell ist mir die Funktionsweise von Rainbow-Tables bis auf eine Sache klar. Ich habe einen Algorithmus entwickelt um ...
![]() |
|
|
#1 (permalink) | |
|
Registriert seit: 31.07.06
![]() |
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/ Zitat:
Greetz Hackse |
|
|
|
|
|
|
#2 (permalink) |
|
Moderator
![]() Registriert seit: 30.03.04
![]() ![]() ![]() ![]() ![]() |
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. |
|
|
|
|
|
#3 (permalink) |
|
Themenstarter
Registriert seit: 31.07.06
![]() |
Hallo Elderan,
warum die statistische Wahrscheinlichkeit auf Kollisionen derart immens erhöhen? Ich sehe den Vorteil nicht. Bitte um Erläuterung. Greetz Hackse |
|
|
|
|
|
#4 (permalink) |
|
Moderator
![]() Registriert seit: 30.03.04
![]() ![]() ![]() ![]() ![]() |
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(n) mit n != m die selbe wie f(m) = g(n), 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. |
|
|
|
|
|
#5 (permalink) | |
|
Themenstarter
Registriert seit: 31.07.06
![]() |
Zitat:
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(n) mit n != m nur genau dann die selbe Eintrittswahrscheinlichkeit wie f(m) = g(n), wenn zusätzlich die Bedingung s(f[1](n)) = s(f[2](n)) 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(y) 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(y)) mit x != y und s1 != s2 Greetz Hackse |
|
|
|
|
|
|
#6 (permalink) | ||
|
Moderator
![]() Registriert seit: 30.03.04
![]() ![]() ![]() ![]() ![]() |
Hallo,
Zitat:
Allerdings kommt da dann deine ursprüngliche Frage wieder ins Spiel: Zitat:
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. |
||
|
|
|
![]() |
| Themen-Optionen | |
| Ansicht | |
|
|
Ähnliche Themen
|
||||
| Thema | Autor | Forum | Antworten | Letzter Beitrag |
| verteiltes Rainbow Tables berechnen | SyneX | Cryptography & Encryption | 1 | 01.01.09 20:09 |
| Darf man Rainbow tables Verkaufen? | p-g | Cryptography & Encryption | 11 | 29.11.08 15:38 |
| Erzeugen von rainbow tables | Iceman39 | Cryptography & Encryption | 2 | 26.09.06 21:35 |
| LM Rainbow Tables | piOo | Cryptography & Encryption | 1 | 05.12.05 10:19 |
| Rainbow Tables im Cluster erzeugen? | Taucha | Cryptography & Encryption | 2 | 14.05.05 12:48 |