Reference / Paper · 2014
Julian Weyers, "Kryptoanalyse der SIGABA" (MA thesis, in German)
SIGABA history and mechanism, a daily key-list example, CrypTool 2 implementation and presentation, cryptanalysis with pseudo-rotors, MTC3 challenge [writer B]
Reference / Paper · 2014
SIGABA history and mechanism, a daily key-list example, CrypTool 2 implementation and presentation, cryptanalysis with pseudo-rotors, MTC3 challenge [writer B]
UNIVERSITÄT DUISBURG-ESSEN FAKULTÄT FÜR INGENIEURWISSENSCHAFTEN ABTEILUNG INFORMATIK UND ANGEWANDTE KOGNITIONSWISSENSCHAFT Masterarbeit Kryptoanalyse der SIGABA B.Sc. Julian Weyers Matrikelnummer: 2232616 Abteilung Informatik und Angewandte Kognitionswissenschaft Fakultät für Ingenieurwissenschaften Universität Duisburg-Essen 3. März 2014 Erstprüfer: Prof. Dr. Arno Wacker Zweitprüfer: Prof. Dr.-Ing. Torben Weis Betreuer: M.Sc. Nils Kopal Inhaltsverzeichnis Eidesstattliche Erklärung 1 1 Einleitung 3 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Aufgabenstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Ziele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Aufbau der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Grundlagen 7 2.1 Kryptografie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Verschlüsselung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Kerckhoffs Prinzip . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Substitution und Transposition . . . . . . . . . . . . . . . . . . . . 9 2.5 Monoalphabetisch und Polyalphabetisch . . . . . . . . . . . . . . . 10 2.6 Zufallszahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.7 One-Time-Pad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.8 Kryptoanalytische Verfahren . . . . . . . . . . . . . . . . . . . . . . 13 2.8.1 Verfahren mit bekanntem Klartext . . . . . . . . . . . . . . 13 2.8.2 Nur-Chiffre Verfahren . . . . . . . . . . . . . . . . . . . . . 13 2.8.2.1 Erschöpfende Schlüsselsuche . . . . . . . . . . . . . 13 2.8.3 Kostenfunktion . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.8.4 Teile und Herrsche . . . . . . . . . . . . . . . . . . . . . . . 14 3 Die SIGABA 17 3.1 Rotorverschlüsselungsmaschinen . . . . . . . . . . . . . . . . . . . . 17 3.2 Rotoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.3 Die SIGABA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.4 Geschichte der SIGABA . . . . . . . . . . . . . . . . . . . . . . . . 20 iii Inhaltsverzeichnis 3.5 Schwächen der Enigma . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.5.1 Die Umkehrwalze . . . . . . . . . . . . . . . . . . . . . . . . 22 3.5.2 Die regelmäßige Fortschaltung der Rotoren . . . . . . . . . . 23 3.6 Funktionsweise der SIGABA . . . . . . . . . . . . . . . . . . . . . . 23 3.7 Alphabet-Labyrinth . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.8 Fortschaltungs-Labyrinth . . . . . . . . . . . . . . . . . . . . . . . . 25 3.9 Bedienung der SIGABA . . . . . . . . . . . . . . . . . . . . . . . . 27 3.9.1 Schritt Eins . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.9.2 Schritt Zwei . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.9.3 Schritt Drei . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.9.4 Schritt Vier . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.9.5 Schritt Fünf . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.9.6 Schritt Sechs . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.10 Implementierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.10.1 CrypTool 2.0 . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.10.1.1 Aufbau von CrypTool 2.0 . . . . . . . . . . . . . . 30 3.10.1.2 Arbeitsflächen-Editor . . . . . . . . . . . . . . . . . 30 3.10.1.3 Parameter-Leiste . . . . . . . . . . . . . . . . . . . 31 3.10.1.4 Komponenten-Browser . . . . . . . . . . . . . . . . 31 3.10.2 Steuerungs-Leiste . . . . . . . . . . . . . . . . . . . . . . . . 31 3.10.3 Komponenten . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.10.3.1 Präsentation . . . . . . . . . . . . . . . . . . . . . 32 3.10.3.2 Einstellungen . . . . . . . . . . . . . . . . . . . . . 32 3.10.3.3 Protokoll . . . . . . . . . . . . . . . . . . . . . . . 32 3.10.3.4 Daten . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.10.3.5 Hilfe . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.10.4 Integrierte-Komponenten . . . . . . . . . . . . . . . . . . . . 32 3.10.5 Verwendete Technologien . . . . . . . . . . . . . . . . . . . . 33 3.10.6 Die SIGABA Komponente . . . . . . . . . . . . . . . . . . . 33 3.10.6.1 Implementierung der Methode zum Verschlüsseln von Nachrichten . . . . . . . . . . . . . . . . . . . 34 3.10.6.2 Einstellungen . . . . . . . . . . . . . . . . . . . . . 37 3.10.6.3 Präsentation . . . . . . . . . . . . . . . . . . . . . 38 4 Kryptoanalyse 4.1 iv Nur-Chiffre-Angriffe 43 . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Inhaltsverzeichnis 4.2 Angriff mit bekanntem Klartext von Stamp/Chan (2007) . . . . . . 4.2.1 Phase I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Phase II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Entwicklung eines eigenen Angriffs . . . . . . . . . . . . . . . . . . 4.3.1 Ansatz zur Verbesserung von Phase II . . . . . . . . . . . . 4.3.1.1 Der Widerspruchsbeweis . . . . . . . . . . . . . . . 4.3.1.2 Der Distanztest . . . . . . . . . . . . . . . . . . . . 4.3.1.3 Vollständiges Testen der Mehrdeutigkeiten im Pseudorotor . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1.4 Das Verfahren zur Schlüsselsuche . . . . . . . . . . 4.3.1.5 Das Verfahren zur schnellen Dechiffrierung . . . . . 4.3.1.6 Schlüsselraum Phase II . . . . . . . . . . . . . . . . 4.3.2 Ansatz zur Verbesserung von Phase I . . . . . . . . . . . . . Vergleich der Angriffe . . . . . . . . . . . . . . . . . . . . . . . . . . 45 46 48 50 50 52 57 5 Implementierung 5.1 Komponente SIGABA-Schlüsselsucher . . . . . . . . . . . . . . . . 5.1.1 Einstellungen . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.2 Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1.3 Präsentation . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Komponente SIGABA-Widerspruchsbeweis . . . . . . . . . . . . . . 5.2.1 Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.2 Widerspruchsbeweis Algorithmus . . . . . . . . . . . . . . . 5.2.3 Verfahren zur Schlüsselsuche Algorithmus . . . . . . . . . . 5.2.4 Verfahren zur schnellen Dechiffrierung . . . . . . . . . . . . 5.2.5 Einstellungen . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2.6 Präsentaion . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Vergleich der Komponenten nach Durchsatz . . . . . . . . . . . . . 5.4 MysteryTwister C3 - The Crypto Challenge Contest . . . . . . . . . 5.4.1 SIGABA - Teil I . . . . . . . . . . . . . . . . . . . . . . . . 5.4.2 SIGABA - Teil II . . . . . . . . . . . . . . . . . . . . . . . . 71 71 71 72 74 76 76 78 80 82 83 83 84 84 85 86 4.3 4.4 58 58 62 63 65 67 6 Zusammenfassung und Ausblick 87 6.1 Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Literaturverzeichnis 91 v Abbildungsverzeichnis 3.1 Darstellung eines orginal Rotors [Pek10] . . . . . . . . . . . . . . . 18 3.2 Schematische Darstellung der Substitution durch den Rotor . . . . . 19 3.3 Schematische Darstellung der Fortschaltungen eines Rotoren . . . . 20 3.4 Darstellung der SIGABA [Pek10] . . . . . . . . . . . . . . . . . . . 21 3.5 Darstellung der SIGABA als Schaltplan . . . . . . . . . . . . . . . . 25 3.6 Schematische Darstellung des Übertrags von 26 Kontakten auf 10 . 26 3.7 Schematische Darstellung des Übertrags von zehn Kontakten auf fünf 27 3.8 Original Tagesschlüssel der SIGABA . . . . . . . . . . . . . . . . . 27 3.9 Darstellung der Oberfläche von CrypTool 2.0 . . . . . . . . . . . . . 30 3.10 Darstellung der Integrierte-Komponenten-Schnittstelle in CrypTool 2.0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.11 Darstellung der Chiffre-Rotoren in der Präsentation . . . . . . . . . 38 3.12 Darstellung des Fortschaltungs-Labyrinths in der Präsentation . . . 39 3.13 Schema der Verdrahtung eines Rotoren in der Präsentation . . . . . 40 3.14 Ansicht einer Animation . . . . . . . . . . . . . . . . . . . . . . . . 41 4.1 Darstellung der Fortschaltungen als Baum . . . . . . . . . . . . . . 47 4.2 Darstellung der Zusammenfassung der Pfade . . . . . . . . . . . . . 48 4.3 Darstellung von Pseudorotor I und II . . . . . . . . . . . . . . . . . 51 4.4 Darstellung von P 4.5 Darstellung von P 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.6 Darstellung wie sich S entwickelt . . . . . . . . . . . . . . . . . . . 59 4.7 Darstellung wie sich S entwickelt . . . . . . . . . . . . . . . . . . . 62 4.8 Darstellung wie sich S entwickelt . . . . . . . . . . . . . . . . . . . 63 4.9 Vergleichende Darstellung der Verfahren . . . . . . . . . . . . . . . 65 . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.10 Darstellung des Widerspruchsbeweises für Phase I . . . . . . . . . . 66 4.11 Darstellung wie sich der Aufwand über k entwickelt . . . . . . . . . 68 4.12 Darstellung wie sich der Aufwand über k entwickelt . . . . . . . . . 69 4.13 Darstellung wie sich der Aufwand über k entwickelt . . . . . . . . . 69 vii Abbildungsverzeichnis 5.1 5.2 5.3 viii Darstellung der Präsentation . . . . . . . . . . . . . . . . . . . . . . 75 Darstellung des Algorithmus als Flussdiagramm . . . . . . . . . . . 77 Darstellung der Funktion Rekursion als Flussdiagramm . . . . . . . 79 Eidesstattliche Erklärung Hiermit versichere ich an Eides statt, die vorliegende Arbeit selbstständig und unter ausschließlicher Verwendung der angegebenen Literatur und Hilfsmittel erstellt zu haben. Die Arbeit wurde bisher in gleicher oder ähnlicher Form keiner anderen Prüfungsbehörde vorgelegt und auch nicht veröffentlicht. Duisburg, 3. März 2014 Unterschrift 1 1 Einleitung 1.1 Motivation Rotorverschlüsselungsmaschinen nehmen im Bereich der Kryptografie einen besonderen Stellenwert ein. Trotz ihrer vergleichsweise simplen Funktionsweise besitzen ihre Chiffren einen für den Anfang des 20. Jahrhunderts sehr großen Schlüsselraum. Dieser Schlüsselraum ist, wie in dieser Arbeit noch gezeigt wird, auch von heutigen Personal Computern nicht in dem Maße trivial zu durchsuchen, wie es bei anderen klassischen (hier definiert als nicht Computer gestützt“) Verschlüsselungstechniken, welche auf Substitution be” ruhen, der Fall ist. Innerhalb der Rotorverschlüsselungsmaschinen ist die SIGABA als wohl am weitesten entwickelt hervorzuheben. Desweiteren gibt es keine Belege, dass sie während der Zeit ihrer Verwendung jemals gebrochen worden wäre. Ziel dieser Arbeit ist es, aufzuzeigen, wie stark das Verfahren aus heutiger Sicht zu bewerten ist. Die Menge der möglichen Schlüssel muss daher durch logische Überlegungen und effiziente Programmierung der Analysewerkzeuge so stark wie möglich reduziert werden. Am Ende wird eine Approximation gegeben, wie viele Ressourcen zum Brechen einer Nachricht der SIGABA heute notwendig wären. 1.2 Aufgabenstellung Der Original Wortlaut der vom Lehrstuhl gegebenen Aufgabenstellung ist hier noch einmal abgedruckt: Die ECM Mark II“ war eine Chiffriermaschine, die von den Vereinigten ” Staaten von Amerika für die Verschlüsselung ihrer Kommunikation während des zweiten Weltkriegs und weiterhin bis in die 1950er Jahre benutzt wurde. Die Maschine war weiterhin bekannt als SIGABA“, Converter M-134” bei der US-Army, oder CSP-888/889“ ” ” ” bei der US-Navy. Die einer Schreibmaschine ähnelnde Maschine bestand, ähnlich wie die deutsche Enigma, aus mehreren sogenannten Walzen. Innerhalb jeder dieser Walzen befand sich eine Verdrahtung, welche einen Stromfluss über alle Walzen hinweg weiterleitete. Drückte man eine Taste auf dem Tastenfeld, so drehten sich die Rotoren in einer 3 1 Einleitung festgelegten Art und Weise und leiteten den Strom entsprechend unterschiedlich weiter. Im Gegensatz zu der Enigma bestand die SIGABA nicht aus drei, sondern aus insgesamt fünfzehn Walzen. Das aktuell ausgegebene Zeichen wurde auch nicht durch eine Lampe angezeigt, sondern mittels Papierstreifen ausgegeben. Eine Umkehrung des Stroms fand bei der SIGABA ebenfalls nicht statt (keine Umkehrwalze), im Gegensatz zu der Enigma, bei der dies eine ihrer Hauptschwächen war. Durch William Friedman wurde die Sicherheit der Maschine außerdem darüber hinaus erheblich verbessert. Er sorgte unter anderem dafür, dass die Rotoren unregelmäßig weiterschalteten. Aus diesen Gründen ist bis heute kein Angriff bekannt, welcher die SIGABA erfolgreich brechen konnte. Im Jahr 2007 untersuchte Wing On Chan innerhalb seines Masterprojekts [Cha07] Cryptanaly” sis of SIGABA“ die Sicherheit der SIGABA. CrypTool 2.0 – der Nachfolger der bekannten e-Learning Anwendung für Kryptographie und Kryptoanalyse CrypTool – ist ein Open-Source Projekt, welches Lernenden, Lehrenden und Entwicklern mit Interesse an der Kryptographie die Möglichkeiten eröffnet, selbst verschiedene kryptographische und kryptoanalytische Verfahren anzuwenden und auszuprobieren. Die moderne Benutzeroberfläche ermöglicht per einfachem und intuitiven Drag & Drop das Erstellen von einfachen bis hin zu sehr komplexen kryptographischen Algorithmen. Dies geschieht dabei mit einer graphischen Programmiersprache, welche speziell für diesen Zweck entwickelt wurde. Der Benutzer kann dabei ohne besondere Programmierkenntnisse die Algorithmen miteinander verbinden und so eigene neue Algorithmen und Abläufe erschaffen und testen. CrypTool 2.0 basiert auf modernsten Techniken wie z.B. das .net Framework (zurzeit 4.0 SP1) und der Windows Presentation Foundation (WPF). Darüber hinaus ist die Architektur von CrypTool 2.0 vollständig Plug-In-basiert und modular aufgebaut, wodurch die Entwicklung neuer Funktionalitäten stark vereinfacht wird. Im Rahmen dieses Projekts wurden bereits eine Mehrzahl von kryptographischen Algorithmen wie z.B. AES, SHA1 oder die Enigma als Komponenten entwickelt. Hauptgegenstand dieser Masterarbeit ist die Kryptoanalyse der SIGABA“ aufbau” end auf der Arbeit von Wing On Chan. Hierbei sollen kryptographische Stärken und Schwächen evaluiert und darauf aufbauend eine Sicherheitseinschätzung (u.a. die Komplexität von Angriffen“) erstellt werden. Praktische Ergebnisse ( Angriffe“) sollen inner” ” halb einer Analysekomponente in CrypTool 2.0 umgesetzt werden. Daneben muss für eine Simulation der SIGABA“ eine eigenständige Komponente erstellt werden, welche die ” vollständige Maschine simuliert. Diese Komponente soll das Ver- und Entschlüsseln von Texten ermöglichen. Hierfür muss ebenfalls eine geeignete Visualisierung (siehe Enigma) der Maschine für CrypTool 2.0 entworfen und umgesetzt werden. Nach der Fertigstellung müssen die CrypTool 2.0 Vorlagen sowie die für die Arbeit erstellten Komponenten in das bestehende Versionsverwaltungssystem von CrypTool 2.0 eingepflegt werden. 4 1.3 Ziele 1.3 Ziele Die Ziele dieser Arbeit können aus der Aufgabenstellung wie folgt definiert werden: • Umsetzung einer Komponente zur Ver- und Entschlüsselung von Texten nach dem Verschlüsselungsprinzip der SIGABA • Entwurf und Umsetzung einer Visualisierung der SIGABA in CrypTool 2.0 • Erstellung der Sicherheitseinschätzung unter Berücksichtigung der Komplexitäten aller vorgestellten Angriffe • Implementierung eines Angriffs auf die SIGABA als Komponente in CrypTool 2.0 Ein zusätzliches Ziel soll die Lösung der SIGABA Challenge Teil I und Teil II auf MysteryTwister C3 sein. 1.4 Aufbau der Arbeit Aus den Zielen ergibt sich der Aufbau dieser Arbeit. Dieser gestaltet sich wie folgt: Das erste nachfolgende Kapitel beschäftigt sich mit den Grundlagen der Kryptografie und der Kryptoanalyse. Diese sind sowohl relevant für die Analyse, wie auch die Implementierung der, in dieser Arbeit erstellten, Komponenten. Es wird ein kurzer Überblick über das Feld der Kryptografie gegeben, um das Verfahren von Schlüssel-Rotor-Maschinen besser einordnen zu können und ein Verständnis für das didaktische Vorgehen in dieser Arbeit zu erzeugen. Desweiteren wird auf Grundlagen zum Verständnis der SIGABA selbst eingegangen, um die Maschine selbst besser analysieren zu können. Abschließend werden noch diverse kryptoanalytische Verfahren vorgestellt, von denen später noch Gebrauch gemacht wird. Kapitel 3 beschäftigt sich mit der eigentlichen Maschine. Angefangen von ihrer Entstehung und der Verbreitung, über das Design und die Funktionsweise der Maschine, bis hin zur Bedienung. Am Ende des Kapitels wird bereits die Implementierung der SIGABA als Komponente in CrypTool 2.0 vorgestellt, um an dieser Stelle einen logischen Abschluss und eine Trennung zwischen Maschine- und Analyse-Teil der Arbeit zu erhalten. In Kapitel 4 werden Ansätze zur Kryptoanalyse der SIGABA diskutiert. Exemplarisch wird zunächst ein Angriff ohne die Verwendung von Klartext illustriert, um abschätzen zu können, wie groß der Schlüsselraum der Maschine tatsächlich ist. Danach folgt die Vorstellung des Angriffs mit bekanntem Klartext von Chan aus dem Jahr 2007. Darauf 5 1 Einleitung aufbauend wird im Folgenden ein neuer Angriff entwickelt und vorgestellt. Dabei wird der Begriff des Pseudorotors eingeführt und der Widerspruchsbeweis illustriert. Abschließend wird eine Approximation des Gesamtaufwands des neuen Angriffs gegeben. Im 5. Kapitel wird gezeigt, wie die Analysekomponenten für CrypTool 2.0 implementiert wurden. Es wurden insgesamt zwei verschiedene Komponenten entwickelt. Die erste Komponente analysiert Texte nach dem Prinzip der erschöpfenden Schlüsselsuche. In der zweiten Komponente wird die Chiffre nach dem, wie in der Kryptoanalyse vorgestellten, neuen Verfahren analysiert. Als letztes wird kurz auf die SIGABA Challenges auf MysteryTwister eingegangen. In Kapitel 6 werden die Ergebnisse der Kapitel Kryptoanalyse und Implementierung zusammengefasst. Es wird ein Fazit gezogen und ein Ausblick auf zukünftige Arbeiten gegeben. 6 2 Grundlagen Für eine Kryptoanalyse der SIGABA, müssen zunächst die Begriffe Kryptografie und Kryptoanalyse geklärt werden. 2.1 Kryptografie Das Wort Kryptografie (oder auch Kryptographie) setzt sich aus den altgriechischen Worten κρυπτ óς (kryptós), für verdeckt“ oder verborgen“ und γραϕειν (gráphein), ” ” für schreiben“, was gemeinsam so viel wie verdecktes schreiben“ bedeutet, zusammen. ” ” Der Begriff bezeichnet heute die Wissenschaft, welche sich mit der Widerstandsfähigkeit verschlüsselter Informationen gegen den Zugriff von Unbefugten beschäftigt. Demgegenüber steht die Kryptoanalyse. Der Begriff Analyse kommt von dem altgriechischen Wort αναλυσις (analysis) und bedeutet Auflösung“. Als Kryptoanalyse werden ” sowohl die Anwendung, als auch die Untersuchung von Praktiken zur Reduzierung oder zur Auflösung der Widerstandsfähigkeit von kryptografischen Verfahren bezeichnet, wie auch der wissenschaftliche Nachweis der Widerstandsfähigkeit der Verfahren und deren Bewertung. Die Kryptografie und die Kryptoanalyse bilden zusammen die Wissenschaft der Kryptologie. [Beu94] 2.2 Verschlüsselung Eines der wichtigsten Teilgebiete der heutigen Kryptografie ist die Verschlüsselung von Nachrichten. Die Nachricht, also die zu verschlüsselnden Informationen, im Folgenden nur noch Klartext“ genannt, werden zusammen mit dem Schlüssel“, einer Kette von ” ” Zeichen beliebiger Länge, durch den Verschlüsselungsalgorithmus in die Chiffre“, die ” verschlüsselten Informationen überführt. Der Sinn der Verfahrens ist, dass es nur mit 7 2 Grundlagen Hilfe des Schlüssels möglich ist, die Chiffre durch diesen Verschlüsselungsalgorithmus wieder in den Klartext zu überführen. Sei (K, C, S, fv , fe ) ein Tupel mit • K = die Menge aller Klartexte • C = die Menge aller Chiffren • S = die Menge aller Schlüssel • fv = K × S −→ C ein Verschlüsselungsalgorithmus • fe = C × S −→ K ein Entschlüsselungsalgorithmus Der Klartext k ∈ K kann mit Hilfe des Schlüssels s ∈ S in die Chiffre c ∈ C überführt werden durch die injektive Funktion fv (k, s) = c und durch die Umkehrfunktion fe (fv (k, s), s) = k wieder in den Klartext zurück überführt werden. Es wird hier die Konvention vereinbart, Größen von Schlüsselräumen allgemein in Potenzen der Form 2x anzugeben. 2.3 Kerckhoffs Prinzip Als allgemeine Konvention der modernen Kryptografie gilt, dass die Sicherheit eines kryptografischen Verfahrens nur in der Geheimhaltung des Schlüssels gewährleistet werden darf, nicht aber in der Geheimhaltung des kryptografischen Verfahrens selbst. Dieses Prinzip wird Kerckhoffs Prinzip genannt, benannt nach dem Kryptologen und Begründer dieser Maxime Auguste Kerckhoff[Beu94]. Die Argumentation an diesem Prinzip festzuhalten, stützt sich vor allem darauf, dass es eher schwieriger ist, ein unsicheres Verfahren als einen Schlüssel auszutauschen und/oder geheim zuhalten. Desweiteren schafft die Transparenz eines Verfahrens bei dessen Nutzern Vertrauen. Verfahren die ihre Sicherheit aus der Geheimhaltung ihrer Methodik beziehen, fallen heute in den Bereich der Steganografie, der Wissenschaft vom Maskieren von Informationen in anderen Informationen. 8 2.4 Substitution und Transposition 2.4 Substitution und Transposition Um die SIGABA kryptoanalytisch bewerten zu können, ist es wichtig, sie im Gebiet der Kryptografie richtig einordnen zu können. Die Verfahren zur Verschlüsselung in der Kryptografie teilen sich in zwei große Bereiche auf, die Transposition und die Substitution. Verfahren der Transposition verschleiern den Inhalt des Klartextes durch Permutation der Positionen der Zeichen im Klartext. Ein Beispiel: • Klartext: AUTO • AUTO −→ TAOU (Schlüssel: 3142) • Chiffre: TAOU Die Zahlen im Schlüssel stellen in diesem Beispiel die Positionen der Buchstaben im Klartext dar. Demgegenüber steht die Substitution, welche den Inhalt des Klartextes durch Ersetzen der Zeichen verschleiert. Ein Beispiel: • Klartext: AUTO • AUTO −→ BVUP • Chiffre: BVUP In dem Beispiel werden die Buchstaben des Klartextalphabetes, in diesem Fall des lateinischen, auf ein sogenanntes Substitutionsalphabet abgebildet, hier ebenfalls des lateinischen, wobei der Index der Buchstaben um i = (i + 1) mod 26 verschoben wurde. Diese Art der Substitution wird Caesar-Verschlüsselung genannt. 9 2 Grundlagen 2.5 Monoalphabetisch und Polyalphabetisch Es werden zwei Arten von Substitutionen unterschieden: Monoalphabetisch und Polyalphabetisch. Wird von dem Klartextalphabet auf nur ein einziges Substitutionsalphabet abgebildet, wird von einem monoalphabetischen Verfahren gesprochen. Ein Zeichen des Klartextalphabetes bildet dabei auf ein eindeutiges Zeichen des Substitutionsalphabetes ab. Ein Beispiel: • Klartextalphabet: ABCDE • Substitutionsalphabet BCDEA (Caesar +1) • Klartext: ABBA • Chiffre: BCCB Wird hingegen von einem Klartextalphabet auf mehrere Substitutionsalphabete abgebildet, wird von einem polyalphabetischen Verfahren gesprochen. Ein Zeichen des Klartextalphabete kann dabei, in Abhängigkeit vom Schlüssel, auf verschiedene Zeichen mehrerer Substitutionsalphabete abbilden. Ein Beispiel: • Klartextalphabet: – ABCDE • Substitutionsalphabete: 1. BCDEA 2. CDEAB 3. DEABC • Schlüssel: 3213 • Klartext: ABBA • Chiffre: DDCD In diesem kleinen Beispiel wird bereits klar, dass polyalphabetische Substitutionen auf Grund ihrer uneindeutigen Abbildungsweise, im Allgemeinen, Angriffen gegenüber widerstandsfähiger sind als monoalphabetische. [Beu94] 10 2.6 Zufallszahlen 2.6 Zufallszahlen Wie im weiteren Verlauf gezeigt wird, bedient sich die SIGABA eines pseudozufälligen Prinzips. Um dies zu verstehen, muss in diesem Kapitel zunächst auf die Grundlagen der Zufälligkeit eingegangen werden. Als Zufallszahlen werden die Ergebnisse eines echten Zufallsexperimentes bezeichnet. Es ist eine Folge von Zahlen mit den Eigenschaften, dass die Werte der Zahlen ohne erkennbares Muster statistisch gleich verteilt sind. Kriterien für ein echtes Zufallsexperiment sind, dass es sich um ein physisches Experiment handelt, dessen Parameter nicht vollständig überwacht werden können. In Folge dieser Bedingungen ergibt sich, dass die Vorhersage des nächsten Zeichens der Folge unmöglich und statistisch vollkommen unabhängig vom vorherigen ist. Beispiele für echte Zufallsexperimente sind weißes Rauschen, z.B. an einem Mikrofoneingang. Neben den Zufallszahlen gibt es die Pseudozufallszahlen. Als Pseudozufallszahlen wird eine Folge von Zahlen bezeichnet, deren Ursprung kein echtes Zufallsexperiment ist. Eine Folge von Pseudozufallszahlen ist, von außen betrachtet, nicht von einer Folge echter Zufallszahlen zu unterscheiden, da die Werte der Zahlen dieselben Eigenschaften bezüglich des nicht erkennbaren Musters und der statistischen Gleichverteilung besitzen. Pseudozufallszahlen können mit sogenannten Pseudozufallsgeneratoren erzeugt werden. Pseudozufallsgeneratoren sind deterministische Algorithmen, welche für eine Eingabe s, den sogenannten Seed“, der Länge k, als Ausgabe eine Zeichenfolge der Länge m >> k ” erzeugen. Es gilt zu beachten, dass es sich beim Seed um echt zufällige Zahlen handelt. Der Pseudozufallsgenerator liefert für einen bestimmten Seed stets dieselbe Ausgabe. Daher besteht die Gefahr, bei entsprechend aufwendiger Analyse der Folge, den Seed zu rekonstruieren. [Wac13] 2.7 One-Time-Pad Das One-Time-Pad ist eines der ältesten Beispiele für ein perfektes Verschlüsselungssystem. Das Verfahren gestaltet sich in der Form, dass der in Bit kodierte Klartext der Länge K mit einer (echt) zufälligen Folge von Bits z gleicher Länge, jeweils bitweise durch die Kontravalenz Operation in die Chiffre überführt wird. Ein Beispiel: 11 2 Grundlagen Klartext: 101010101010101010 One-Time-Pad: 110101001001001011 Chiffre: 011111100011100001 Das One-Time-Pad ist nach dem Satz von Shannon Perfekt sicher. In seinem Buch Diskrete Mathematik“ schreibt Martin Aigner dazu: ” Das System (T , C, K) hat perfekte Sicherheit, falls für alle T ∈ T , C ∈ C p(T | C) = p(T ) gilt, wobei p(T | C) die bedingte Wahrscheinlichkeit ist. Mit anderen Worten: Die Kenntnis des Kryptosystems C sagt absolut nichts darüber aus, welcher Text T gesendet wurde. Aus p(T |C)p(C) ) p(C | T ) = p(C∧T p(T ) = p(T ) folgt sofort die äquivalente Bedingung p(C | T ) = p(C) für alle T ∈ T , C ∈ C [Aig04] Für das One-Time-Pad bedeutet dies, gegeben ist ein Klartext K = x1 , x2 , . . . xn aus 0, 1 und eine echt zufällige Folge S = z1 , z2 . . . zn aus 0, 1, wobei jede Zahl unabhängig und mit Wahrscheinlichkeit 21 gezogen wird, S ist der Schlüssel. Die Chiffre C ist definiert durch C = c(T, z) = y1 , y2 . . . yn mit yi = xi ⊕ zi für alle i. Die Dekodierung ist dann d(yi ) = yi zi . Alle möglichen 2n Chiffren C sind gleich wahrscheinlich, also p(C) = 21n , und ebenso gilt p(CT ) = 21n , da jedes Zeichen yi in C mit Wahrscheinlichkeit 21 aus xi erzeugt wird. 12 2.8 Kryptoanalytische Verfahren 2.8 Kryptoanalytische Verfahren Kryptoanalytische Verfahren lassen sich innerhalb der Kryptoanalyse ihrer Methodik nach klassifizieren. Im Folgenden werden verschiedene Methoden vorgestellt, welche während der Kryptoanalyse der SIGABA zum Zuge kommen werden. 2.8.1 Verfahren mit bekanntem Klartext Angriffe auf Chiffren, deren Methoden darauf angewiesen sind, dass der Klartext oder Teile davon bekannt sind, werden als Angriffe mit bekanntem Klartext, bzw. dem gebräuchlicheren englischen Begriff Known-Plain-Text Attack“ bezeichnet. Gemein ist ” diesen Verfahren, dass der Klartext dazu benutzt wird, den Schlüsselraum einzugrenzen und auf diese Weise den Aufwand zu reduzieren. Wahrscheinlichkeit eines Erfolgs und Aufwand des Verfahrens hängt stark vom Verfahren selbst und von der Menge an benötigtem bekannten Klartext ab. Ziel eines Angriffs mit bekanntem Klartext besteht darin, die restliche Nachricht zu entschlüsseln, sowie den verwendeten Schlüssel zu ermitteln und/oder Aufschluss über die Funktionsweise von Teilen des Verschlüsselungsverfahrens zu gewinnen.[Beu94] 2.8.2 Nur-Chiffre Verfahren Die Begriffe Nur-Chiffre, oder der gebräuchlichere englische Term Cipher-Text-Only At” tack“ bezeichnen Angriffe, welche die Chiffre ohne zusätzliche Informationen über den Klartext oder den Schlüssel analysieren. Das bekannteste und trivialste Verfahren ist dabei die sogenannte erschöpfende Schlüsselsuche“, oder auch engl. Bruteforce Attack“. ” ” [Beu94] 2.8.2.1 Erschöpfende Schlüsselsuche Als Bruteforce oder erschöpfende Schlüsselsuche, werden jene Verfahren bezeichnet, deren Prinzip darauf beruhen, alle Varianten der Grundgesamtheit (z.B. Schlüssel) zu testen. Auf Grund der Tatsache, dass die korrekte Variante ebenfalls ein Teil der Grundgesamtheit ist, ist die Wahrscheinlichkeit des Erfolgs bei einer erschöpfenden Schlüsselsuche genau gleich 1,0. Die erschöpfende Schlüsselsuche stellt dabei aber auch per Definition stets die aufwendigste und ineffizienteste Art aller korrekten Verfahren dar. Durch diesen höchstmöglichen Aufwand, bzw. die sehr hohen Ressourcen die nötig sind, um diesen 13 2 Grundlagen bewältigen zu können, erklärt sich auch der Name Bruteforce, engl. für Rohe Gewalt“. ” [KR11] Beispiel: Ein Zahlenschloss mit drei Ringen, von denen jeder von 0-9 durchnummeriert ist, öffnet sich nur in der korrekten Stellung der drei Ringe. Eine erschöpfende Schlüsselsuche würde sich in der Form gestalten, alle Positionen der Ringe durchzuprobieren, bis sich das Schloss öffnet. Der Aufwand dieses Angriffs würde 310 betragen. Der Angriff ist dabei mit einer Wahrscheinlichkeit von 1,0 erfolgreich. Es ist kein Verfahren denkbar, welches den richtigen Schlüssel langsamer findet und dabei keinen Schlüssel zwei mal testet. 2.8.3 Kostenfunktion Viele kryptoanalytische Verfahren erzeugen nicht nur den einen Klartext, sondern auch teilweise sehr viele andere Texte, die durch ihre Eigenschaften und ohne weitere Informationen, vom Verfahren, nicht als Klartext ausgeschlossen werden können. In einer klassischen erschöpfenden Schlüsselsuche werden zum Beispiel, durch das Verfahren selbst, keine Ergebnis-Texte ausgeschlossen. Ist der Schlüsselraum demnach n groß, ist die Zahl der erzeugten Texte ebenfalls gleich n. Um diese Texte in eine Ordnung zu bringen, werden Kostenfunktionen verwendet. Als Kostenfunktionen werden in der Kryptoanalyse Verfahren bezeichnet, welche Texte im Hinblick auf ein bestimmtes Kriterium hin analysieren und einen sogenannten Kostenwert für diese ermitteln. In der Kryptoanalyse helfen diese Werte dabei, die Texte im Hinblick darauf zu bewerten, ob diese beispielsweise einer bestimmten natürlichen Sprache entstammen. Auf diese Weise kann eine Rangfolge der erzeugten Texte erstellt werden, in welcher jener Klartext einen sehr hohen Wert haben wird, der ebenfalls dieser natürlichen Sprache entstammt. 2.8.4 Teile und Herrsche Als Teile und Herrsche bzw. der gebräuchlichere englische Begriff Divide and Conquer“ ” werden Ansätze zur Lösung eines komplexen Problems bezeichnet, welche vorschlagen dieses in mehrere simplere Subprobleme zu unterteilen. Aus den Ergebnissen der Subprobleme kann dann das Ergebnis des Hauptproblems konstruiert werden. Die Motivation eines Teilen und Herrschen Ansatzes ist dabei stets, dass die Summe der Subprobleme 14 2.8 Kryptoanalytische Verfahren effizienter zu lösen ist, als das eigentliche Problem selbst. Es gibt viele Beispiele, wo dieser Ansatz zum Tragen kommt, zum Beispiel bei Sortierproblemen. [SKQ01] 15 3 Die SIGABA Für eine vollständige Kryptoanalyse ist es wichtig, das Prinzip und die Funktionsweise der Verschlüsselung durch die SIGABA in voller Gänze verstanden zu haben. Dazu muss zu aller erst auf das technische Prinzip von Rotorschlüsselmaschinen im Allgemeinen, wie im Speziellen eingegangen werden. 3.1 Rotorverschlüsselungsmaschinen Anfang des 20. Jahrhunderts entwickelten mehrere Erfinder gleichzeitig und unabhängig voneinander Maschinen, welche nach dem Prinzip der Rotorverschlüsselung arbeiten. Gründe dafür waren zum Einen das Aufkommen der Fernschreibertechnologie. Durch diese Technologie konnten Nachrichten schnell über große Distanzen elektronisch übertragen werden, was vorher mit manuellen Technologien nicht so ohne Weiteres möglich war. Diese Technik war jedoch äußerst anfällig gegenüber dem Mithören von Dritten, was schnell die Begehrlichkeit nach Verschlüsselung zur Geheimhaltung vertraulicher Nachrichten weckte. Da die Übertragung Zeichenweise erfolgte, war eine Verschlüsselung, welche ebenfalls zeichenweise funktionierte nur folgerichtig und logisch. Eine weitere Erfindung, welche die Entwickler maßgeblich inspirierte, war die der elektronischen Schreibmaschine. Erst das Prinzip der digitalen Kodierung durch Eingabe von Zeichen über die Tastatur machte eine elektronische Verschlüsselung durch die Rotoren praktikabel. 3.2 Rotoren Der Kern einer jeden Rotorverschlüsselungsmaschine ist der sogenannte Rotor“. Der ” physische Rotor besteht aus einer Deck- und einer Bodenplatte, mit jeweils 26 nach außen gerichteten, elektrischen Kontakten, einer respektive für jeden Buchstaben des Alphabets. Im Falle der SIGABA gab es auch kleinere Rotoren mit nur zehn Kontakten. 17 3 Die SIGABA Jeweils ein Kontakt der Bodenplatte, ist mit einem Kontakt der Deckplatte verbunden. Welcher Kontakt mit welchem verbunden ist, hängt allein von dem Verdrahtungsschema des Rotors ab. Wird von außen eine Spannung an einen Kontakt des Rotoren angelegt, fließt der Strom zu dem verdrahteten Kontakt weiter. Kryptografisch gesehen führt ein Rotor somit eine monoalphabetische Substitution durch. Erst durch das Fortschalten, die Rotation des Rotors, wird eine polyalphabetische Substitution erreicht. Abbildung 3.1: Darstellung eines orginal Rotors [Pek10] Beim Fortschalten dreht sich der komplette Rotor mechanisch in seinem Gehäuse genau so, dass der Eingangskontakt, welcher vorher als ’A’ interpretiert werden konnte, nun als ’B’ interpretiert werden muss. Da sich die Verdrahtung innerhalb des Rotors mitdreht, ändert sich auf diese Weise auch die Substitution. Mathematisch gesehen wird die Distanz zwischen den Interpretationen der Kontakte verschoben. Entscheidend für die Substitution ist also, neben der Verdrahtung, die Stellung“ des Rotoren. Auf der Hülle des Rotors ist ein fortlaufendes Alphabet ” aufgebracht. Jeder Buchstabe bezeichnet dabei eine jener Stellungen. Diese kann durch 18 3.2 Rotoren ein Sichtfenster in der Maschine abgelesen werden. Ein Beispiel: Der Rotor substituiert in Stellung ’A’ den Buchstaben ’A’ auf ’B’, dann beträgt der Abstand zwischen den Kontakten der durch den Draht im Inneren überbrückt wird +1 und den Buchstaben ’B’ auf ’D’, also +2. Schaltet der Rotor nun fort auf Stellung ’B’, substituiert der Rotor nicht mehr ’B’ auf ’D’, sondern ’B’ auf ’C’, da sich die Substitution von A nach B verschoben hat, also die +2 Substitution durch die +1 Substitution ersetzt wurde. In der nachfolgenden Grafik 3.2 ist dies noch einmal illustriert. Stellung A Stellung B A A A B B B C C D D D ... ... ... A B C +1 +2 +1 +2 C D ... Abbildung 3.2: Schematische Darstellung der Substitution durch den Rotor Mehrere Rotoren hintereinander geschaltet werden als Rotorbank bezeichnet. Über die Kontakte wird der Stromimpuls an den nächsten Rotor weitergeleitet. Die kryptografische Sicherheit dieses Verfahrens beruht auf der Vielzahl der möglichen Stellungen mehrerer Rotoren einer Bank zueinander. Die Summe aller Stellungen der Rotoren bilden demnach zusammen mit den korrekten Positionen der Rotoren innerhalb der Bank den Schlüssel. Ein Rotor kann im speziellen Fall der SIGABA auch falsch“ herum, also auf dem Kopf“ ” ” oder rückwärts“ eingelegt werden, was zu einer genau entgegengesetzten Substitution ” durch den Rotor führt. Sprich ’A’ substituiert nicht mehr auf ’B’, sondern ’B’ substituiert auf ’A’. Außerdem schaltet ein falsch herum eingelegter Rotor auch inkrementell, statt dekrementell. Also von der Stellung ’S’ nach ’T’, wie in dem folgenden Schema 3.3 veranschaulicht. 19 3 Die SIGABA normal Schritt P Q R S T U V ... Schritt O P Q R S T U ... Schritt rückwärts N O P Q R S T ... Schritt Schritt Schritt Schritt Schritt Abbildung 3.3: Schematische Darstellung der Fortschaltungen eines Rotoren 3.3 Die SIGABA Die SIGABA Rotorverschlüsselungsmaschine war eine von den Amerikanern im zweiten Weltkrieg und noch darüber hinaus bis in die 50er Jahre benutzter Apparat zum Verund Entschlüsseln von Nachrichten. Eine Rotorverschlüsselungsmaschine verschlüsselt dabei, ausgehend von einer Starteinstellung, die in diesem Zusammenhang als Schlüssel definiert werden kann, jeden Buchstaben einzeln. Dazu wurde die verschlüsselte Nachricht mittels einer Tastatur, Buchstabe für Buchstabe, wie in einer Art Schreibmaschine, in die Maschine eingegeben. Die Ausgabe erfolgte bei der SIGABA über einen Papierstreifen. Die Maschine führt dabei für jeden Buchstaben eine Substitution durch, welche nach jeder Eingabe eines weiteren Buchstabens permutiert. Es handelt sich daher um ein polyalphabtisches Kryptografieverfahren. [Lee03] 3.4 Geschichte der SIGABA Der Vorgänger der SIGABA war die M-134“. Diese Maschine wurde von William Frede” rick Friedmann 1933 vorgestellt. Friedmann griff die Idee der Rotorverschlüsselung, wie sie Edward Hebern in seinem Patent aus dem Jahre 1921 beschrieb [Heb21]. Er erkannte jedoch die kryptografische Schwäche der deterministischen Fortschaltung der Rotoren. Er schlug in seinem Entwurf hingegen ein zufälliges Fortschalten der Rotoren vor. Dieses Fortschalten sollte bei der M-134 zunächst durch ein Lochband erreicht werden, welches in die Maschine eingespannt wurde und auf dem die Fortschaltungen durch Löcher festgehalten waren. Dieses Lochband erwies sich in der Praxis jedoch als unpraktisch. Es wurde daher in den nachfolgenden Modellen, der M-134 A“ und M-134 C“, durch ” ” das M-229“ ersetzt, dem sogenannten Stepping Maze“, welches auf Friedmanns Mit” ” arbeiter Frank Byron Rowlett zurück geht. Dieses Bauteil sollte die Fortschaltung nach 20 3.4 Geschichte der SIGABA Abbildung 3.4: Darstellung der SIGABA [Pek10] einem pseudozufälligen Prinzip steuern. Dieses Prinzip sollte durch eine weitere Rotorverschlüsselung erreicht werden, welche die nun wieder deterministische Fortschaltung maskieren sollte. [Goe12] Auf Grund der erfolgreichen Brechung des Verschlüsselungssystems der japanischen Marine, erkannte der, damals noch US Navy Commander, Laurance F. Safford die Wichtigkeit eines sicheren Verschlüsselungssystems. Er erkannte im Winter 1936-1937 weiterhin das Potential der M-134, und machte sich für deren Einsetzung in der US Navy stark. Ab diesem Zeitpunkt wurde die M-134 mit dem Stepping Maze von der US Navy unter Verschluss gehalten und unter dem Namen ECM (Electronic Cipher Machine) Mark II weiterentwickelt, vor allem in Bezug auf die Zuverlässigkeit der mechanischen Teile. 1940 wurden die Einzelheiten der ECM Mark II mit der US Army geteilt und ab dem 01.08.1940 von beiden Militärs genutzt. Die San Francisco Maritime National Park Association betont die Wichtigkeit eines gemeinsam genutzten, hoch sicheren Kryptografiesystems. So ist auf ihrer Internetseite zu lesen: The use of a common system was of great military value, particularly during the early ” stages of the war when the distribution of machines and codewheels was incomplete. 21 3 Die SIGABA By 1943, over 10,000 machines were in use. The Stepping Maze“ and use of electronic ” control were a generation ahead of the systems employed by other countries before and after WW II. No other country is known to have ever broken the ECM Mark II cryptographic system.“ [Pek10] Die SIGABA war bei Außerbetriebnahme in den späte