Seite 3: Klartext ist notwendig

Inhaltsverzeichnis

Klartext ist notwendig

Als 1977 der Chiffrierstandard DES verabschiedet wurde, bissen sich die besten Forscher die Zähne daran aus. Erst 1990 entwickelten die beiden israelischen Mathematiker Biham und Shamir die differenzielle Kryptanalyse, mit der DES erstmals schneller als mit Brute Force gebrochen werden konnte -- allerdings nur theoretisch. Der Gedanke dahinter ist folgender: Wenn man bei einem "ideal sicheren Blockalgorithmus" [3, 4, 1] in einem Klartextblock ein Bit ändert, dann müsste sich statistisch jedes der Bits im erzeugten Geheimtextblock mit genau 50% Wahrscheinlichkeit ändern, unabhängig vom verwendeten Schlüssel. In der Praxis kommt es jedoch vor, dass für bestimmte Bits die "Änderungswahrscheinlichkeit" im Geheimtext von einem bestimmten Schlüsselbit abhängt, etwa in der Art: Wenn man im Klartext die Bits 3, 11 und 45 gemeinsam ändert, dann ändert sich das Bit 17 im Geheimtext nur mit 49,999% Wahrscheinlichkeit, falls Bit 5 des Schlüssels gleich 1 ist, ansonsten mit 50%. Kann man dem Chiffrierer große Massen an ausgewähltem Klartext unterschieben, dann lässt die statistische Analyse Rückschlüsse auf einige Bits des verwendeten Schlüssels zu. Die restlichen Schlüsselbits ermittelt man per Brute Force.

Das Problem der Praxis ist, dass bei guten Verfahren der Unterschied zum "Idealverhalten" minimal ist und man riesige Mengen an Klar- und Geheimtext braucht, um an den Schlüssel heranzukommen. Konkret bei DES wären über ein Petabyte (1000 Terabyte) an gewähltem Klartext notwendig. Es nützt nichts, dass die anschließende Rechenarbeit schneller geht als bei Brute Force. Die Entdeckung der differenziellen Kryptanalyse war dennoch ein großer Fortschritt. Erstaunlicherweise war DES bereits von Anfang an gegen differenzielle Kryptanalyse optimiert -- offenbar von der NSA, die den Algorithmus damals für IBM "begutachtete". Es stellte sich heraus, dass jede Änderung der so genannten S-Boxen von DES (das sind spezielle nichtlineare Transformationen) einen schwächeren Algorithmus ergeben hätte. Die Entwickler des geplanten DES-Ersatzes FEAL hingegen kannten diese Art des Angriffs nicht.

Die Weiterentwicklung der Methode heißt lineare Kryptanalyse und wurde 1993 von Matsui veröffentlicht. Dabei verknüpft man ausgewählte Bits von Klar- und Geheimtext per XOR. Theoretisch müsste das Ergebnis für exakt 50% aller Schlüssel gleich 0 und für den Rest gleich 1 sein. Der Kryptanalytiker sucht Abweichungen von diesem Idealwert in Abhängigkeit von Schlüsselbits. Diese Methode ist deutlich leistungsfähiger: Zum Knacken von DES braucht man "nur noch" 70 Terabyte an ausgewähltem Klartext, und bei FEAL-4 lediglich 40 Byte (beim stark verbesserten FEAL-8 reduzierte sich die Zahl von 80 KByte auf 96 Byte).

In der Praxis lässt sich DES immer noch nur per Brute Force knacken, und gegen 3DES (drei DES-Chiffrierungen nacheinander, effektiv 112 Bit Schlüssellänge) spricht eher die sehr niedrige Geschwindigkeit als zu geringe Sicherheit bei Datenübertragungen.

Matsui stellte 1996 zwei Algorithmen unter dem Namen Misty vor, die erstmals vom Design her sicher gegen differenzielle und lineare Kryptanalyse sind. Eine Weiterentwicklung davon ist Kasumi, der in UMTS-Telefonen zum Einsatz kommt.

Wer Algorithmen entwickelt, muss auch differenzielle und lineare Kryptanalyse sicher beherrschen. Manchmal fällt das nicht so leicht. Das überraschend einfache Verfahren RC5 zum Beispiel (siehe Bild) nahm den Angreifern erst einmal den Wind aus den Segeln. Bits in 32-Bit-Wörtern werden zyklisch vertauscht; der Betrag der Rotation hängt dabei vom Klartext selbst ab und ist nicht vorhersagbar. Mit Mühe bewies man, dass differenzielle und lineare Kryptanalyse bei RC5 wenig fruchtet.

Dann hatten John Kelsey, Bruce Schneier und David Wagner (der Artikel findet sich auf der CD in [1]) eine sehr einfache Idee: Wenn "<<<" die Rotation um ein Bit nach links bedeutet, dann gilt für 32-Bit-Wörter x:

x <<< 1 ? 2x (mod 3)

Das heißt: Das um ein Bit rotierte Wort x lässt bei Teilung durch 3 den gleichen Rest wie 2x. Durch 3 teilbare Zahlen x bleiben also bei Rotation durch 3 teilbar -- das sind fast ein Drittel aller Zahlen. Bei den restlichen zwei Dritteln der Zahlen ist der Rest modulo 3 wieder der gleiche, wenn man sie zweimal nach links rotiert. Man folgert daraus, dass für zufällige x und n die Gleichung

x <<< n ? x (mod 3)

ungefähr mit Wahrscheinlichkeit 2/3 gilt.

Die datenabhängige Rotation, die den Kryptanalytikern soviele Kopfschmerzen bereitete, verwischt also doch eine Information nur ungenügend. Zusammen mit Computersimulation an einer Stelle, wo die Theorie nicht weiterführte, griff man eine Modifikation von RC5 an, die man für ebenso sicher wie RC5 selbst hielt. Glück gehabt, dass RC5 auf das richtige Pferd setzte! Als "Nebeneffekt" konnte das beim FireWire-Standard eingesetzte M6-Verfahren sogar praxiswirksam geknackt werden.