Crash (Kryptologie)
Als Crash (/kræʃ/; Plural: Crashes; deutsch Zusammenstoß, Krach, Absturz; deutscher Fachbegriff: Kollision) wird in der Kryptologie das Zusammentreffen eines identischen Buchstabens an derselben Position sowohl im Klartext als auch im Geheimtext bezeichnet, im Jargon dann auch mit dem Verb to crash (deutsch „crashen“) bezeichnet.[1] Das Gegenteil ist Admit (deutsch zulassen; frei übersetzt: „Passt“).[2]
Crash darf nicht mit Clash (dem wiederholten Auftreten derselben Enigma-Walze an zwei aufeinanderfolgenden Tagen) verwechselt werden.
Bedeutung
Von großer Bedeutung sind Crashes in der klassischen Kryptologie bei den polyalphabetischen Chiffrierungen, die der Bedingung genügen „in jedem Alphabet wird kein Zeichen durch das selbe Zeichen chiffriert“.[3] Dazu gehören involutorische Chiffrierungen. Ein prominentes Beispiel ist die Rotor-Schlüsselmaschine Enigma, die während des Zweiten Weltkriegs von der deutschen Wehrmacht eingesetzt wurde. Wird dort beispielsweise ein U in ein X verschlüsselt, dann würde bei dieser Stellung umgekehrt ein X in ein U verschlüsselt.
Diese besondere Eigenschaft der Involution vereinfachte Bedienung und Konstruktion der Maschine, denn man muss nicht zwischen Verschlüsselung und Entschlüsselung unterscheiden. Gleichzeitig wird so aber auch eine kryptographische Schwäche verursacht, nämlich, dass niemals ein Buchstabe in sich selbst verschlüsselt wird (fixpunktfreie Permutation). Die britischen Codeknacker im englischen Bletchley Park (B.P.)[4] kannten diese Schwäche und nutzen sie zu ihrem Vorteil beim Bruch der Maschine. Die von ihnen zur Entzifferung der deutschen Enigma-Funksprüche erfolgreich eingesetzte elektromechanische „Knackmaschine“, die Turing-Bombe (auch: Turing-Welchman-Bombe oder Welchman-Turing-Bombe; kurz Bombe), benötigt für ihre Funktion Klartextpassagen, deren Auftreten und genaue Position im Text von den Codeknackern erraten werden mussten. Dabei half ihnen die Beobachtung von Crashes.
Als Admit, frei übersetzt „passt“, wurde das Gegenteil von crashen bezeichnet, also ein passender Crib an einer bestimmten Position innerhalb des Textes, der zu keinerlei Crashes führt. Genau solch passende Crib-Lagen waren die begehrten Stellen, die mithilfe der Turing-Bombe anschließend näher untersucht wurden und die nicht selten zur Lösung des Geheimtextes führten.
Beispiel
Ein seit Jahrhunderten bekanntes und bewährtes Entzifferungsverfahren ist die „Methode des Wahrscheinlichen Worts“.[5][6] Hierbei errät, vermutet oder weiß der Angreifer, dass im Text eine bestimmte Phrase (englisch Crib, französisch Mot probable) auftritt, beispielsweise „OBERKOMMANDODERWEHRMACHT“. Liegt dem Angreifer zum Beispiel ein mit der Enigma verschlüsseltes Geheimtextfragment wie das folgende vor, so kann er ganz leicht ermitteln, an welcher Stelle im Text das vermutete Wahrscheinliche Wort sich nicht befinden kann, indem er für jede mögliche Lage prüft, ob ein Zeichen in sich selbst verschlüsselt würde, was, wie er von der Enigma weiß, unmöglich ist. Dazu schreibt er das Wahrscheinliche Wort in den verschiedenen Lagen unter den Geheimtext und prüft auf Kollisionen,[7] die im unteren Beispiel rot und unterstrichen hervorgehoben sind:
BHNCXSEQKOBIIODWFBTZGCYEHQQJEWOYNBDXHQBALHTSSDPWGW 1 OBERKOMMANDODERWEHRMACHT 2 OBERKOMMANDODERWEHRMACHT 3 OBERKOMMANDODERWEHRMACHT 4 OBERKOMMANDODERWEHRMACHT 5 OBERKOMMANDODERWEHRMACHT 6 OBERKOMMANDODERWEHRMACHT 7 OBERKOMMANDODERWEHRMACHT 8 OBERKOMMANDODERWEHRMACHT 9 OBERKOMMANDODERWEHRMACHT 10 OBERKOMMANDODERWEHRMACHT 11 OBERKOMMANDODERWEHRMACHT 12 OBERKOMMANDODERWEHRMACHT 13 OBERKOMMANDODERWEHRMACHT 14 OBERKOMMANDODERWEHRMACHT 15 OBERKOMMANDODERWEHRMACHT 16 OBERKOMMANDODERWEHRMACHT 17 OBERKOMMANDODERWEHRMACHT 18 OBERKOMMANDODERWEHRMACHT 19 OBERKOMMANDODERWEHRMACHT 20 OBERKOMMANDODERWEHRMACHT 21 OBERKOMMANDODERWEHRMACHT 22 OBERKOMMANDODERWEHRMACHT 23 OBERKOMMANDODERWEHRMACHT 24 OBERKOMMANDODERWEHRMACHT 25 OBERKOMMANDODERWEHRMACHT 26 OBERKOMMANDODERWEHRMACHT 27 OBERKOMMANDODERWEHRMACHT BHNCXSEQKOBIIODWFBTZGCYEHQQJEWOYNBDXHQBALHTSSDPWGW |
Die Anzahl der durch Crashes auszuschließenden Lagen lässt sich nach folgender Überlegung abschätzen: Bei einem Wahrscheinlichen Wort der Länge 1 (also nur ein einzelner wahrscheinlicher Buchstabe) ist die Wahrscheinlichkeit für eine Kollision 1/26. Folglich ist die Wahrscheinlichkeit für keinen Crash 1−1/26. Bei einem Wahrscheinlichen Wort wie oben mit der Länge 24 ist dann die Wahrscheinlichkeit für keine Kollision (1−1/26)24, das sind etwa 39 %. Das heißt, bei 27 untersuchten Lagen erwartet man im Mittel für 27·(1−1/26)24 der Fälle keine Crashes. Der Ausdruck ergibt etwa den Wert 10,5 und stimmt recht gut mit den im Beispiel beobachteten (und grün gekennzeichneten) acht kollisionsfreien Crib-Lagen überein. Mithilfe dieser äußerst simplen kryptanalytischen Angriffsmethode lassen sich so von den 27 möglichen Lagen des Wahrscheinlichen Worts hier 19, also mehr als zwei Drittel, als unmöglich eliminieren – eine erhebliche Arbeitsvereinfachung für den Angreifer.
Literatur
- Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, ISBN 3-540-67931-6.
- Tony Sale: The Bletchley Park 1944 Cryptographic Dictionary. Publikation, Bletchley Park, 2001. PDF; 0,4 MB, abgerufen am 27. August 2018.
Weblinks
Einzelnachweise
- Tony Sale: The Bletchley Park 1944 Cryptographic Dictionary. Publikation, Bletchley Park, 2001, S. 22. PDF; 0,4 MB, abgerufen am 27. August 2018.
- Tony Sale: The Bletchley Park 1944 Cryptographic Dictionary. Publikation, Bletchley Park, 2001, S. 1. PDF; 0,4 MB, abgerufen am 27. August 2018.
- Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 270.
- Gordon Welchman: The Hut Six Story – Breaking the Enigma Codes. Allen Lane, London 1982; Cleobury Mortimer M&M, Baldwin Shropshire 2000, S. 11. ISBN 0-947712-34-8
- Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 276.
- Claude Shannon: Communication Theory of Secrecy Systems. Bell System Technical Journal, Vol 28, 1949 (Oktober), S. 710f. PDF; 0,6 MB, abgerufen: 27. August 2018.
- David Kahn: Seizing the Enigma – The Race to Break the German U-Boat Codes, 1939–1943. Naval Institute Press, Annapolis, MD, USA, 2012, S. 131. ISBN 978-1-59114-807-4.