Erfolgsgeschichten
Seit ihrer Einführung sind TMTOs erfolgreich gegen eine Vielzahl von kryptografischen Algorithmen eingesetzt worden. Ein erstes Ziel waren die LM-Hashes von Windows-Passwörtern. Unabhängig von deren Länge speichert Windows ein lokales Nutzerkennwort in Blöcken zu sieben Zeichen, was zu der paradoxen Situation führt, dass ein Passwort mit zehn Zeichen unter Umständen schwächer ist als ein Passwort mit sieben Zeichen. Der Grund ist, dass der Hash über die letzten drei Zeichen sehr leicht zu knacken ist und der errechnete Klartext Aufschluss über die ersten sieben Zeichen Passwortes geben kann.
Die Anzahl der in einem Angriff zu berücksichtigenden Passwörter hängt stark davon ab, welche Arten von Zeichen ein Benutzer wählt beziehungsweise wählen kann. Als Maßeinheit für die Güte eines Passwortes hat sich die Entropie etabliert. Sie gibt an, wie viele mögliche Zustände es annehmen kann und somit, wie viele Passwörter bei einem Angriff durchzuprobieren wären. Sieben Zeichen lange Windows-Passwörter, die nur aus Buchstaben bestehen, entsprechen der Entropie von 33 zufällig gewählten Bits. Kommen Sonderzeichen und Ziffern zum Zeichenvorrat hinzu, sind es immerhin schon 36 Bit. Beliebte Kombinationen wie Namen oder Wörter mit einer Zahl oder einem Ausrufezeichen am Ende haben aber eine weit geringere Entropie.
Typische Windows-Passwörter sind daher ein leichtes Ziel für TMTOs. Tabellen mit 99-prozentiger Trefferrate brauchen etwa zwei Sekunden, um ein 14-stelliges alphanumerisches LM-Passwort zu finden und belegen nur etwa ein GByte Speicher [2]. Zu diesen zwei Sekunden kommt natürlich noch die Zeit, um die Tabellen von der Festplatte in den Arbeitsspeicher zu laden, die sich aber amortisiert, wenn große Mengen an Passwörtern geknackt werden. Aufgrund der hohen Kollisionsrate in der LM-Hash-Funktion benötigt die Vorberechnung der Tabellen etwa die zehnfache Zeit eines Brute-Force-Angriffs, also einige Wochen auf einem PC. Fertige Tabellen gibt es aber auch beispielsweise unter www.shmoo.com zum Download. Die hohe Kollisionsrate macht außerdem Rainbow Tables etwa zehnmal schneller als Distinguished Points.
Genau andersherum verhält es sich bei der Handy-Gesprächs- und SMS-Verschlüsselung A5/1, einer Stromchiffre mit 64 Bit langen Schlüsseln. Sie verwendet einen zufälligen Anfangszustand, um TMTO-Angriffe zu vereiteln. Doch aufgrund einer kryptografischen Schwäche lässt sich dieser Schutz umgehen. In einem verschlüsselten GSM-Paket, etwa einer SMS, finden sich mehr als 200 überlappende Segmente zu je 64 Bit. Um die gesamte Nachricht zu entschlüsseln, muss ein Angreifer nur eines dieser Segmente knacken, da sich die Chiffre von dort sowohl vorwärts als auch rückwärts berechnen lässt, um die fehlenden Bits aufzufüllen. Selbst mit lückenhaften Tabellen ist die Wahrscheinlichkeit vergleichsweise hoch, dass mindestens einer der 200 Werte enthalten ist.
Diese Optimierung ermöglicht es, GSM-Schlüssel mit Tabellen zu knacken, die nur etwa eineinhalb Prozent des Platzes belegen, der rechnerisch für eine 64-Bit-Chiffre benötigt würde. Die Optimierung disqualifiziert allerdings Rainbow Tables, da vor einem Fund im Schnitt einige dutzend Male ins Leere gelaufen wird und dieser Fall bei ihnen besonders ungünstig ist.
Aufgrund der niedrigeren Kollisionsrate ist der Aufwand zur Vorberechnung von GSM-Tabellen weit geringer als bei Windows-Passwörtern und braucht gerade mal die doppelte Brute-Force-Zeit. Die 259 Berechnungen dauern aber immerhin noch mehrere Monate auf teurer Spezialhardware mit FPGAs.
Aber wie bei den Windows-Hashes haben andere diesen Aufwand bereits getrieben. Das "GSM Cracking Project" hat kürzlich Tabellen für A5/1 fertiggestellt, die sie mit Forschern teilen, die drei TByte freien Speicherplatz haben. Mit den Tabellen lässt sich der geheime Schlüssel mit über 95-prozentiger Wahrscheinlichkeit innerhalb von 30 Sekunden finden. Ist ein Schlüssel erst einmal gefunden, lässt sich die komplette Gesprächs- oder SMS-Verbindung mithören beziehungsweise -lesen.
Ebenfalls anfällig für einen TMTO-Angriff ist die Verschlüsselung Crypto1 des Funkbezahlsystems "Mifare Classic" [3], das nicht nur in Fahr- und Mensakarten, sondern auch in Zugangskontrollsystemen weit verbreitet ist. Der in Crypto1 vorgesehene Schutz gegen TMTO verlässt sich darauf, dass die individuelle Chip-ID in die Verschlüsselung einfließt und ein Angreifer somit für jeden Chip eine eigene Tabelle vorberechnen müsste. Doch Schlüssel und ID sind mit einer umkehrbaren Funktion miteinander verknüpft, weshalb sich ein Satz Tabellen für alle Chip-IDs einsetzen lässt. Außerdem benutzt Crypto1 recht kurze 48-Bit-Schlüssel, was den Angriff zusätzlich erleichtert. Ein Satz Distinguished-Points-Tables konnte in gerade einmal 50 Minuten auf dem FPGA-Cluster generiert werden, den auch das GSM-Cracking-Projekt verwendete. Mit Hilfe dieser Tabelle lassen sich die Schlüssel in Sekunden finden.