Crash (Kryptologie)

Begriff aus der Kryptoanalyse

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

Bearbeiten

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 dasselbe 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

Bearbeiten

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

Bearbeiten
  • 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.
Bearbeiten
Wiktionary: crash – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen
Wiktionary: admit – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Einzelnachweise

Bearbeiten
  1. Tony Sale: The Bletchley Park 1944 Cryptographic Dictionary. Publikation, Bletchley Park, 2001, S. 22. PDF; 0,4 MB, abgerufen am 27. August 2018.
  2. Tony Sale: The Bletchley Park 1944 Cryptographic Dictionary. Publikation, Bletchley Park, 2001, S. 1. PDF; 0,4 MB, abgerufen am 27. August 2018.
  3. Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 270.
  4. 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
  5. Friedrich L. Bauer: Entzifferte Geheimnisse. Methoden und Maximen der Kryptologie. 3., überarbeitete und erweiterte Auflage. Springer, Berlin u. a. 2000, S. 276.
  6. Claude Shannon: Communication Theory of Secrecy Systems. In: Bell System Technical Journal. Band 28, Nr. 4, 1949, S. 710 f., doi:10.1002/j.1538-7305.1949.tb00928.x (englisch).
  7. 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.