Von Wörterbüchern und Regenbögen
Seite 3: Regenbogentabelle
Alles so bunt hier!
Eine weitere Verbesserung gegenüber Hellmans Technik, die nicht zu vermehrten Kollisionen führt, schlug 2003 Philippe Oechslin vor. Sein Angriff verhindert Kollisionen fast vollständig. Wie bei den anderen TMTO-Techniken wird beginnend mit einem Zufallsschlüssel eine zuvor gewählte Nachricht verschlüsselt. Das Ergebnis wird aber mit einer rundenabhängigen Funktion für die nächste Runde vorbereitet. Bei den anderen Techniken kommt es zu einer Kollision, wenn nach der Rundenverschlüsselung ein bereits zuvor berechneter Wert herauskommt. Die zusätzliche Rundenfunktion sorgt jedoch dafür, dass der abgeleitete Schlüssel für die nächste Runde unterschiedlich ist. Zu Kollisionen kommt es nur dann, wenn die gleiche Ausgabe in zwei Ketten in der gleichen Runde auftritt.
Die Rundenfunktion kann recht einfach sein, etwa: Addiere 1 nach der ersten Runde, addiere 2 nach der zweiten Runde und so weiter. Je nach den kryptografischen Eigenschaften der Verschlüsselungsfunktion führen aber kompliziertere Rundenfunktionen zu besseren Ergebnissen, also zu weniger Kollisionen und besserer Abdeckung aller Schlüssel. Metaphorisch gesehen wandern die Daten durch einen Regenbogen, wo erst die rote Funktion angewendet wird, dann die orange, die gelbe, grüne und so fort. Dies hat der Technik den Namen Regenbogentabellen (Rainbow Tables) eingebracht.
Zum Finden eines Schlüssels mit Hilfe einer Regenbogentabelle muss ein Angreifer mehrere Abschnitte einer Kette wiederherstellen, denn aufgrund der Rundenfunktion ist es nicht mehr egal, an welcher Stelle die Berechnung beginnt. Als Erstes durchläuft die verschlüsselte Nachricht des anvisierten Systems die letzte Runde, also deren Rundenfunktionen sowie die Verschlüsselung. Liefert die Regenbogentabelle keinen Treffer für den Endwert, durchläuft die Nachricht die vorletzte und die letzte Runde, dann von der drittletzten Runde aus und so weiter, bis ein Endwert in der Tabelle auftaucht. Statistisch wird durchschnittlich die Hälfte der Schlüssel gefunden, sobald die halbe Kettenlänge erreicht ist.
Da die ersten zu berechnenden Unterketten vergleichsweise kurz sind, werden bei der Suche im Durchschnitt nur halb so viele Kettenglieder nachgerechnet wie bei den anderen TMTO-Techniken, was die Schlüsselsuche um bis zu Faktor zwei beschleunigt. Dieser Geschwindigkeitsgewinn tritt allerdings nur dann auf, wenn der gesuchte Schlüssel tatsächlich in der Tabelle vorhanden ist. Andernfalls müssen alle Unterketten generiert werden, um festzustellen, dass das gesuchte Element fehlt, was erheblich aufwendiger ist als bei den anderen Techniken.
Zwischen Oechslins Rainbow Tables und Rivests Distinguished Points gibt es folglich keinen klaren Gewinner und je nach den Eigenschaften der Verschlüsselungsfunktion ist das eine oder das andere Verfahren schneller. Rainbow Tables benötigen wesentlich mehr Festplattenzugriffe, Distinguished Points hingegen verursachen mehr Kollisionen, weil die Menge möglicher Endpunkte kleiner ist.
