Seite 2: Länge ist nicht alles

Inhaltsverzeichnis

Länge ist nicht alles

Den Kryptanalytiker jedoch beeindrucken große Schlüssellängen wenig, er sucht gezielt nach Schwachstellen. Ein simples Beispiel soll das verdeutlichen: Substitutionsverfahren, bei denen einfach ein Buchstabe durch einen anderen ersetzt wird, sind uralt und werden schon lange von Hobbykryptologen gebrochen. Wie das geht, wird in Edgar Allan Poes Erzählung "Der Goldkäfer" sehr gut beschrieben. Es ist ein statistischer Angriff: Das Zeichen, das den Buchstaben "e" ersetzt, wird (im Englischen wie im Deutschen) am häufigsten im Geheimtext vorkommen -- in der Erzählung war es die "8". Auch die nächsthäufigsten Buchstaben wird man mit einiger Sicherheit so noch erkennen können. Poes Kryptanalyse war jedoch intelligenter: Relativ oft kam im Text "88" vor, was die Hypothese, "e" sei durch "8" ersetzt worden, erhärtete, und oft stand am Ende eines dreibuchstabigen Wortes eine "8". Wahrscheinlich handelte es sich dabei um "the" -- und schon war die Codierung für "t" und "h" bekannt. So rekonstruierte der Analytiker Schritt für Schritt die Substitutionstabelle.

Aus naiver Sicht heraus ist der Angriff erstaunlich, denn bei einem Zeichensatz von nur 26 Buchstaben sind bereits 2⁸⁸ Substitutionstabellen möglich (26! = 4 · 10²⁶ = 2⁸⁸). Schlüssellängen von 88 Bit dürften heute noch Geheimdienst-resistent sein, aber kein Substitutionsverfahren, denn es verbirgt die Klartextstruktur kaum, und sowohl die Häufigkeiten einzelner Zeichen als auch die von Paaren und Tripeln lassen sich unmittelbar ablesen.

Poe beschreibt Handarbeit, ein Gefühl für die Sprache ist Voraussetzung. Heutige Kryptanalytiker würden vermutlich anders vorgehen. Sie würden Paare von fast nie aufeinanderfolgenden Buchstaben sammeln und bei Probe-Dechiffrierungen auf das Auftreten solcher "verbotener" Paare im erzeugten Klartext testen. Ein geschickt programmiertes Branch-and-Bound-Verfahren könnte die Entzifferung von nur wenig Dutzend Zeichen langen Geheimtexten in Sekundenbruchteilen ermöglichen.

So primitiv die Substitutionsmethode ist, so lehrreich ist ihre Kryptanalyse. Angreifer werden immer nach der schwächsten Stelle suchen. Eine feste Methode gibt es dafür nicht. Ist jedoch erst einmal ein Bit entziffert, folgt oft das nächste -- und dann ist es meist nicht mehr weit bis zum Erfolg. Deswegen werden Algorithmen schon beim ersten Anzeichen einer Schwäche verworfen.

"Selbstgebackene" scheitern oft daran, dass sie eben nicht eingehend geprüft wurden. Selbst ein erfahrener Kryptanalytiker, der weiß, wo sich typischerweise Schwachstellen befinden, kann alleine kaum alle finden. Die verwirrend komplizierte und trotzdem unsichere Pkzip-Chiffrierung (siehe Kasten) liefert ein schönes Beispiel hierfür.

Alles ist erlaubt

Bisher gibt es nur ein Verfahren, dessen Sicherheit beweisbar ist: Das One-Time-Pad, bei dem eine zufällige Bitfolge per XOR mit dem Klartext verknüpft wird. Die Methode hat allerdings zwei Nachteile: Erstens dürfen One-Time-Pads nur einmalig verwendet werden und zweitens muss die Bitfolge (der Schlüssel) genauso lang sein wie der Klartext. In der Praxis ist dieses Verfahren daher kaum anwendbar. An den Schwierigkeiten des "Schlüsselnachschubs" scheiterte der KGB nach dem zweiten Weltkrieg in den USA. Agenten tauschten untereinander ihre Pads. Das war ein grober Fehler. Wenn zwei verschiedene Texte mit dem gleichen Pad chiffriert werden, dann ergibt das XOR-Produkt beider Geheimtexte keinen "reinen Zufall" mehr, sondern hat Struktur. Auf diese Weise fand der damalige Vorläufer der NSA zunächst die kritischen Paare von Nachrichten heraus.

Damit besaßen die amerikanischen Geheimdienstler noch keine Klartexte, nur XOR-Produkte von Klartexten: C = P1 ^ P2. Nun konnten sie die Zickzack-Methode anwenden: Sie nahmen ein möglichst langes Wort, das beispielsweise in P2 wahrscheinlich auftreten würde, an und schoben es über C entlang. In bestimmten Stellungen ergab sich beim XOR mit C ein sinnvolles Stückchen Klartext aus P1, vielleicht "hite hou". Das könnte von "white house" stammen. Ergab das XOR von "white house" mit dem entsprechenden Stück von C ein sinnvolles Fragment von P2, konnte man damit fortfahren. Schritt für Schritt wurden so die Klartextportionen vergrößert. Im Zickzack sprang man dabei zwischen P1 und P2 hin und her. Genauso geht man übrigens vor, wenn Ausschnitte aus Shakespeares Werken oder von Bundestagsreden aus dem Internet als One-Time-Pad verwendet werden.

Diese Kryptanalyse brachte Julius und Ethel Rosenberg als Atomspione auf den elektrischen Stuhl, wobei ihre Schuld niemals eindeutig bewiesen wurde [1]. Das One-Time-Pad bleibt trotzdem hundertprozentig sicher -- wenn es denn richtig angewendet wird.