Zitat:
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(n) mit n != m die selbe wie f(m) = g(n), 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(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