Von Wörterbüchern und Regenbögen
Seite 2: Hellman und Rivest
Weites Feld
Der vom Diffie-Hellman-Verfahren bekannte Kryptograph Martin Hellman war es, der erstmals 1980 einen praktikablen Kompromiss zwischen den beiden Extremen vorschlug, der sich Zeiteffizienz beim Angriff mit Platzverbrauch durch vorberechnete Daten erkauft. Als Begriff für solche Techniken hat sich "Time Memory Trade-Off" oder kurz TMTO eingebürgert. Ihnen liegt die Idee zu Grunde, das Wörterbuch nur teilweise oder komprimiert zu speichern und während der Schlüsselsuche die fehlenden Teile zu berechnen oder die Suche so oft leicht modifiziert zu wiederholen, bis ein Treffer im Wörterbuch vorkommt. Seitdem hat die TMTO-Technik viele Anwendungen gefunden, etwa zum Online-Knacken von Windows-Passwörtern und zum Entschlüsseln von Handygesprächen [1].
Hellman hatte die Idee, das Wörterbuch in Form von langen Ketten zu speichern. Am Beginn einer solchen Kette steht ein zufällig gewählter Schlüssel, mit dem eine festgelegte Nachricht verschlüsselt wird. Die Ausgabe dieser ersten Runde dient in der Folgerunde als Schlüssel zur Verschlüsselung der Ursprungsnachricht. Die Ausgabe dieser Runde liefert den nächsten Rundenschlüssel und so weiter, bis die Kette eine vorgegebene Länge erreicht hat. Um Platz zu sparen, speicherte Hellman von diesen Ketten jeweils nur den ersten und letzten Wert. Das derart komprimierte Wörterbuch ist eine nach den Endwerten sortierte zweispaltige Tabelle.
Um einen Schlüssel zu knacken, muss der Angreifer das Zielsystem zunächst dazu bringen, die zu den Ketten passende Nachricht zu verschlüsseln. Die anschließende Suche in dem Wörterbuch ist ein zweistufiges Verfahren. Im ersten Schritt vollzieht der Angreifer mit der verschlüsselten Nachricht dieselben Kettenschritte wie bei der Wörterbucherstellung – und zwar so lange, bis er seinen Zwischenstand als Kettenendwert im Wörterbuch findet.
Im zweiten Schritt muss er ausgehend vom zugehörigen Startwert die Kette nur noch einmal bis zu der Stelle nachrechnen, an der er die verschlüsselte Nachricht findet. Der vorangehende Wert in der Kette ist der gesuchte Schlüssel – so zumindest die vereinfachte Theorie.
Je nach Verschlüsselungsfunktion können aber Kollisionen auftreten, wenn unterschiedliche Zwischenwerte zu demselben Folgewert führen. Da nach einer Kollision stets dieselbe Reihe von Kettengliedern folgt, kann es zu einem Endwert mehrere Kettenstartwerte geben. Falls kein Startwert erwischt wurde, der unterwegs am gesuchten Schlüssel vorbeiführt, bleibt die Suche erfolglos.
Durch die zufällige Wahl des Startwerts entstehen außerdem unweigerlich Lücken in der Abdeckung – nicht alle möglichen Schlüssel sind in den Ketten enthalten. Statistisch gesehen ist die Menge der berechneten Ketten zu verdoppeln, um die Menge der nicht von einem Kettenglied abgedeckten Schlüssel zu halbieren, was schnell zu großen redundanten Datenmengen führt, wenn man es auf eine gute Abdeckung des Schlüsselraums abgesehen hat.
Die maximale Schrittzahl für das Knacken ist durch die Länge der Ketten bestimmt, und der nötige Speicherplatz ist durch die Anzahl der Ketten gegeben. Je weniger Ketten berechnet wurden, desto länger müssen diese sein und desto länger dauert es, einen Schlüssel zu finden. Mit perfekten Tabellen wäre es möglich, den Schlüssel eines Systems mit N möglichen Schlüsseln in N1/2 (Wurzel aus N) Schritten in einem Wörterbuch der Größe 2·N1/2 zu finden. Solche perfekten Tabellen existieren aber für die gängigen Verschlüsselungsverfahren und deren große Schlüssellängen nicht. Selbst wenn es sie gäbe, ließen sie sie nicht in realistischer Zeit durchsuchen. Hellman präsentiert in seiner Arbeit einen Trade-off mit N2/3 Suchzeit, 2·N2/3 Speicherplatz und N2/3 Vorberechnungszeit der Tabellen. Für viele Jahre war dies der beste bekannte Trade-Off.
Hellmans Trade-Off ist in vielen Fällen jedoch nicht optimal. Der Flaschenhals bei der Wörterbuchsuche ist heute typischerweise nicht der Prozessor, sondern die Festplatte. Der Algorithmus muss nach jedem Schritt prüfen, ob das erzeugte Element in der Tabelle vorkommt, und dafür in der Regel mehrere Festplattenzugriffe tätigen. Der Prozessor kann daher die Daten meist weit schneller generieren, als sie die Festplatte auftreiben kann.
Um den Flaschenhals "Festplatte" möglichst wenig in Anspruch nehmen zu müssen, schlug der Kryptologe Ronald "Das R aus RSA" Rivest, der auch maßgeblich an Algorithmen wie MD5 und RC4 beteiligt war, 1982 eine Optimierung von Hellmans Methode vor: Es landen nur Endwerte in der Wörterbuchtabelle, die einem bestimmten Kriterium wie "die letzten zwölf Bits sind Nullen" entsprechen. Beim Generieren der Ketten werden diese – wiederum von Zufallswerten ausgehend – nur jeweils soweit durchlaufen, bis ein Wert das Kriterium erfüllt und als Endpunkt dienen kann. Rivests Ansatz ist daher auch als "Distinguished Points" (etwa "besondere Punkte") bekannt. Entspricht bei der Wörterbuchsuche ein Zwischenwert nicht dem Distinguished-Point-Kriterium, braucht er erst gar nicht auf der Festplatte nachgeschlagen werden.
Da der Endpunkt zu einem Startwert nicht vorhersehbar ist, ohne die Kette durchzurechnen, sind die Ketten unterschiedlich lang. Das ändert nichts am durchschnittlichen Bedarf an Suchzeit und Speicherplatz, sehr wohl aber an der Häufigkeit von Kollisionen. Die längeren Ketten haben ein größeres Risiko für Kollisionen, was im Schnitt die geringere Kollisionswahrscheinlichkeit in den kürzeren Ketten nicht wettmachen kann. Zudem ist das Ablaufen einer langen Kette zeitintensiver, was die Nachteile durch die Kollisionen noch einmal verschlimmert.
