Lösen alter Verschlüsselungen mit modernen Algorithmen

Die Codeknacker

Klaus Schmeh

Von der verschlüsselten Postkarte bis zum Enigma-Funkspruch aus dem Zweiten Weltkrieg sind aus den letzten Jahrhunderten unzählige verschlüsselte Texte erhalten geblieben. Dechiffrierexperten versuchen, diese alten Kryptogramme mit spezieller Software und neuen Algorithmen zu entziffern – oft mit beachtlichem Erfolg.

Die Enigma war im Zweiten Weltkrieg die wichtigste Verschlüsselungsmaschine der Deutschen. Originale Enigma-Funksprüche, wie dieser aus dem Konzentrationslager Flossenbürg, sind heute bei historisch interessierten Codeknackern sehr begehrt (Abb. 1).

Im Jahr 2001 tauchten im Nachlass eines Wehrmachtveteranen etwa 800 verschlüsselte Botschaften aus dem Zweiten Weltkrieg auf. Der Verdacht lag nahe, dass es sich dabei um Funksprüche handelte, die mit der legendären Verschlüsselungsmaschine Enigma erzeugt worden waren (Abbildung 1). Für Enigma-Experten war dieser Fund ein Glücksfall, denn von den über eine Million Enigma-Sprüchen, die die Deutschen während des Kriegs versendeten, sind die meisten verschollen.

Die Enigma-Experten Frode Weierud und Geoff Sullivan nutzten die Gelegenheit und machten sich daran, die gut 800 Funksprüche zu dechiffrieren. Anders als die Briten im Zweiten Weltkrieg konnten sie dazu moderne Computertechnik nutzen. Außerdem stand ihnen ein neuer Algorithmus zum Lösen von Enigma-Verschlüsselungen zur Verfügung, den der US-Kryptologe Jim Gillogly einige Jahre zuvor entwickelt hatte. Dieser Algorithmus sieht vor, einen Teil des jeweiligen Enigma-Schlüssels durch Durchprobieren aller infrage kommenden Möglichkeiten (Brute Force) zu ermitteln und den Rest mit einem Hill-Climbing-Algorithmus (davon wird noch die Rede sein) zu erledigen. Derart gerüstet konnten Weierud und Sullivan einen Großteil der über 800 Enigma-Funksprüche knacken. 320 davon, so zeigte sich, stammten aus der Funkstation des Konzentrationslagers Flossenbürg im Bayerischen Wald. Als besonders interessant erwies sich ein Spruch vom 15. April 1945. Er vermeldete den Tod des inhaftierten Widerstandskämpfers Friedrich von Rabenau – der entschlüsselte Funkspruch war für Historiker der erste Hinweis auf dessen Todestag.

Codeknacker aus Leidenschaft

Frode Weierud und Geoff Sullivan sind nicht die Einzigen, die verschlüsselte Texte (Kryptogramme) aus geschichtlichem Interesse lösen. Längst hat sich eine ganze Szene solcher Codeknacker gebildet, die sich verschlüsselte Funksprüche, Briefe, Telegramme, Tagebücher, Postkarten und andere Dokumente aus den letzten Jahrhunderten vornehmen. Da immer wieder neue verschlüsselte Texte aus Archiven, Bibliotheken und Dachböden zum Vorschein kommen, mangelt es ihnen nicht an Arbeit [1].

Da sich die Verschlüsselungstechnik (Kryptologie) seit Aufkommen des Computers stark verändert hat, hat die Arbeit der Codeknacker alter Texte kaum etwas mit der Kryptoanalyse moderner Chiffrierverfahren (beispielsweise AES oder Triple-DES) gemein. So geht man in der modernen Kryptoanalyse davon aus, dass das verwendete Verfahren genau bekannt ist – nur der Schlüssel wird als geheim angenommen. Dem Kryptoanalytiker stehen hierbei beliebig viele Klartext-Geheimtext-Paare zur Verfügung, wobei es bereits als Erfolg gilt, wenn ein Angriff besser funktioniert als das Durchprobieren aller möglichen Schlüssel. Letzteres ist bei einer Schlüssellänge von 128 Bit eine Sache von Jahrtrilliarden.

Historische Verschlüsselungsverfahren

Geheimschriften, wie diese aus dem 17. Jahrhundert, lassen sich meist über die Buchstabenhäufungen lösen (Abb. 2). Quelle: Wellcome Library

Die Praxis, Texte durch Verschlüsselung vor ungebetenen Mitlesern zu schützen, war bereits im Mittelalter verbreitet. Viele der damaligen Verschlüsselungen waren Geheimschriften – man ersetzte also jeden Buchstaben des Alphabets durch ein Symbol (Abbildung 2). Spätestens im 14. Jahrhundert war bekannt, dass man eine solche Geheimschrift knacken kann, indem man die unterschiedlichen Häufigkeiten der Buchstaben ausnutzt. Im Deutschen ist beispielsweise das E der häufigste Buchstabe, gefolgt von N, I und S. Mit diesem Wissen lässt sich ein Text ab einer Länge von ungefähr 40 Buchstaben knacken.

Ein Nomenklator hält für die Buchstaben des Alphabets sowie für häufige Wörter und Silben je ein Symbol (hier eine mehrstellige Zahl) bereit (Abb. 3). Quelle: Karl de Leeuw

Um diese Schwachstelle zu beheben, führte man Verfahren ein, die für häufige Buchstaben mehrere Symbole (sogenannte Homofone) bereitstellten, aus denen der Verschlüssler wählen konnte. Etwa zur gleichen Zeit fing man an, eigene Symbole für Silben und ganze Wörter vorzusehen. So entstanden Verfahren, die man als Nomenklatoren bezeichnet. Da es recht lästig ist, sich für alle Buchstaben (inklusive Homofonen), Silben und Wörter unterschiedliche Symbole auszudenken, nutzte man statt Symbolen mit der Zeit lieber mehrstellige Zahlen oder Buchstabenfolgen (Abbildung 3).

Ein Codebuch listet für alle gängigen Wörter einer Sprache (und oft auch für ganze Sätze und Redewendungen) je ein Symbol auf. Noch im Zweiten Weltkrieg spielten Codebücher eine wichtige Rolle (Abb. 4).

Ein einfacher Nomenklator (ohne Homofone) sieht beispielsweise wie folgt aus: A=1, B=2, C=3, D=4, E=5 […] Z=26, LONDON=27, FRANKFURT=28, HAMBURG=29, BERLIN=30. Der Satz FAHRE MORGEN VON HAMBURG NACH BERLIN verschlüsselt sich damit in 6 1 8 18 5 13 15 18 7 5 14 22 15 14 29 14 1 3 8 30. Nomenklatoren waren in der frühen Neuzeit sehr beliebt. Aus Sicherheitsgründen konstruierte man immer umfangreichere Exemplare, die immer mehr Silben und ganze Wörter enthielten. Als im 19. Jahrhundert die Telegrafie aufkam und dadurch die Nachfrage nach Verschlüsselung weiter stieg, erreichten die Ersetzungstabellen oft Buchstärke – man spricht dann nicht mehr von einem Nomenklator, sondern von einem Codebuch (Abbildung 4). Das Verschlüsseln einzelner Buchstaben spielt bei einem Codebuch nur noch eine untergeordnete Rolle, da es für alle gängigen Wörter Entsprechungen gibt. Noch im Zweiten Weltkrieg wurden zahlreiche Codebücher eingesetzt.

Nomenklatoren und deren Nachfolger, die Codebücher, waren zwar über Jahrhunderte hinweg die bedeutendsten Verschlüsselungsverfahren, aber natürlich nicht die einzigen. Manche Kryptologen setzten lieber auf Werkzeuge wie Chiffrierscheiben oder Chiffrierschieber. Auch Verfahren, bei denen es nicht um die Ersetzung, sondern um die Umordnung von Buchstaben ging (Umordnungsverfahren), spielten oft eine Rolle. Eine passwortbasierte Umordnung der Spalten eines Klartexts bezeichnet man auch als Würfel. Als besonders sicher und nahezu unlösbar gilt die doppelte Ausführung eines Würfels (Doppelwürfel).

Auch im Ersten Weltkrieg waren neben Codebüchern, die für den Schützengraben kaum zu gebrauchen waren, viele andere Ersetzungs- und Umordnungsverfahren (und Kombinationen der beiden Ansätze) in Gebrauch. Fast alle diese Methoden erwiesen sich als unsicher und wenig praktikabel. Viele wurden von den Gegnern geknackt. Ab etwa 1920 drängten daher zahlreiche Maschinen zur Verschlüsselung auf den Markt, die sich schnell durchsetzten. Zu diesen Verschlüsselungsmaschinen zählt die legendäre Enigma. Im Zweiten Weltkrieg spielte sie eine wichtige Rolle.

Der historisch interessierte Codeknacker, der sich einen alten verschlüsselten Text vornimmt, weiß dagegen oft nicht, mit welchem Chiffrierverfahren er es zu tun hat. Zudem steht ihm nur so viel Analysematerial zur Verfügung, wie das Kryptogramm hergibt. Andererseits sind die Verfahren der Vor-Computer-Ära (siehe Kasten „Historische Verschlüsselungsverfahren“) deutlich weniger sicher als beispielsweise der AES, was die Arbeit wiederum erheblich erleichtert.

Nachrichten eines Partisanen

Ein typisches Beispiel für ein historisches Kryptogramm ist das verschlüsselte Tagebuch des italienischen Partisanen Antonio Marzi (1924–2007). Marzi übermittelte in den Jahren 1944 und 1945 kriegswichtige Informationen per Funk aus der besetzten Stadt Udine an eine Kontaktperson. Zum Schutz vor feindlichen Lauschern verschlüsselte er seine täglichen Funksprüche mit einer Variante des Doppelwürfels (siehe Kasten „Historische Verschlüsselungsverfahren“). Seine Schlüsselwörter entnahm er einem Gedicht. Da Marzi seine täglichen Mitteilungen aufbewahrte, entstand ein verschlüsseltes Kriegstagebuch von historischem Wert. In späteren Jahren gelang es Marzi jedoch nicht mehr, seine eigenen Notizen zu entschlüsseln.

2011 gelangte Marzis Tagebuch auf MysteryTwister C3, eine Webseite für kryptologische Knobeleien (www.mysterytwisterc3.org). Dort bissen sich zwei Jahre lang selbst die erfolgreichsten Mitspieler die Zähne daran aus. An der Spitze der „Hall of Fame“ von MysteryTwister C3 stand damals der Freiburger Hobby-Codeknacker Armin Krauß. Dieser nahm sich Marzis Tagebuch vor. Er probierte sämtliche Wörter, die in dem von Marzi angegebenen Gedicht vorkamen, als mögliche Schlüssel durch. Doch in allen Fällen spuckte der Computer nur Kauderwelsch aus.

Auf die richtige Spur führte Krauß schließlich die Hypothese, dass der Fünf-Buchstaben-Block am Anfang jedes Eintrags nicht zur verschlüsselten Nachricht gehörte, sondern angab, welche Wörter aus dem Gedicht als Schlüssel zu verwenden waren. Nun gab der Computer plötzlich sinnvolle Wörter aus. „Situazione locale tranquilla“ („die Lage hier ist ruhig“) lautete das erste Klartextstück, das zum Vorschein kam. Die Verschlüsselung war gebrochen. Erstmals nach fast 70 Jahren konnte man das Tagebuch wieder lesen. Eine typische Passage darin lautet: „Die Deutschen sind sehr deprimiert. Sie halten sich zurück, sind aber immer noch kämpferisch und gehorchen den Befehlen.“