Kryptographie, Teil 4: Enigma

Im dritten Teil der Serie über Kryptographie wurde unter anderem die Vigenère-Chiffre besprochen. Die große Gefahr und die Anfälligkeit dieses Algorithmus für Angriffe, bei denen ein Teil des Klartextets bekannt ist, begründeten sich durch die verhältnismäßig kurze Schlüssellänge. Bei der One-Time-Pad-Verschlüsselung wird das Problem dadurch umgangen, dass der Schlüssel genau so lang wie der Klartext gewählt wird. Bei allen damit verbundenen praktischen Problemen ist dies jedoch in den meisten Fällen kein anwendbares Verfahren.

Enigma
Detailaufnahme einer Enigma-Maschine mit Tastatur, Ausgabe-Lämpchen und Steckbrett

Ein Lösungsansatz ist der Versuch, vereinfacht gesprochen aus einem kurzen Schlüssel einen langen zu machen. Das One-Time-Pad ist deswegen sicher, weil eine lange Folge von Zufallswerten als Schlüssel dient. Ein praxistaugliches Verschlüsselungsverfahren nach diesem Prinzip muss also darauf basieren, aus einem kurzen Schlüssel eine lange Folge von Pseudo-Zufallszahlen zu generieren. Diese müssen sich deterministisch aus dem Schlüssel ergeben, sonst wäre auch mit Kenntnis des Schlüssels ein Dechiffrieren unmöglich.

Anfang des 20. Jahrhunderts gab es erste Entwicklungen, dieses Problem elektromechanisch zu lösen. Bei diesen elektrisch betriebenen Maschinen wurde über eine Schreibmaschinentastatur der Klartext eingegeben und über Lämpchen bei jedem Tastendruck der entsprechende Buchstabe des Geheimtexts angezeigt. Die Maschinen sind mit elektrisch betriebenen Walzen, sogenannten Rotoren, ausgestattet, die sich bei jedem Tastendruck weiter drehen, bei jeder Stellung eine andere Verdrahtung haben und somit für jeden Tastendruck eine andere Zuordnung von Klartext- zu Geheimtext-Buchstaben hervorrufen. In Abhängigkeit von der Stellung der Rotoren vor Beginn des Verschlüsselungsvorgangs ergibt sich bei diesen Rotormaschinen eine verschiedene, sehr lange Folge von unterschiedlichen Verdrahtungen. Aus einem kurzen Schlüssel, nämlich der Grundstellung der Rotoren, ergibt sich quasi eine Vigenère-Verschlüsselung mit einem sehr langen Schlüssel.

Engima
Zwei Varianten der Enigma-Maschine im Museum für Kommunikation in Frankfurt am Main

Eine Vertreterin dieser Klasse ist die 1918 entwickelte Enigma-Maschine, die ihre große Bekanntheit ihrer Verwendung durch die deutsche Wehrmacht, insbesondere der Marine, im 2. Weltkrieg verdankt. Die Enigma wurde in mehreren Varianten mit 3 oder 4 Rotoren und einer zusätzlichen Verwürfelung über die freie Verkabelung eines Steckbretts eingesetzt.

Schon bei der Ausführung mit 3 Rotoren erzeugt die Enigma eine Verschlüsselung, die sich erst nach über 17.000 Zeichen wiederholt. Dies stellt einen erheblichen Sicherheitsgewinn gegenüber einer simplen Vigenère-Chiffre dar. Dennoch konnte die Enigma-Verschlüsselung durch die Briten (nach Vorarbeit durch Polen) unter Führung des Mathematikers Alan Turing gebrochen werden.

Skulptur Alan Turings
Skulptur Alan Turings, Foto von Jon Callas, CC BY 2.0

Die Enigma hatte einige Schwächen, die für Angriffe ausgenutzt werden konnten. So wurde zum Beispiel niemals ein Klartext-Buchstabe im Geheimtext auf den selben Buchstaben abgebildet, also ein “A” im Klartext wurde niemals ein “A” im Geheimtext, ein “B” niemals ein “B”, und so weiter. Was auf den ersten Blick wie eine gute Idee aussieht, ermöglicht in Wahrheit einen Angriff über eine sogenannte negative Mustersuche. Ist beispielsweise bekannt, dass das Wort “UBOOT” irgendwo im Klartext stehen muss, kann man versuchen, die Stelle im Geheimtext zu bestimmten, an der dieses Wort steht. Man muss dazu wie im folgenden Beispiel nach Übereinstimmungen von Klartext- und Geheimtext-Buchstaben suchen und kann bestimmte Positionen ausschließen.

 Geheimtext: NVGOXUBNKSLTPT
Wahrscheinliches Wort: UBOOT
 UBOOT 
  UBOOT 
   UBOOT 
    UBOOT 
     UBOOT 
      UBOOT 
       UBOOT 
        UBOOT 
         UBOOT

Nur an den bestimmten Stellen, hier kursiv dargestellt, kann das Wort “UBOOT” im Klartext stehen, an den anderen Stellen gibt es mindestens eine Übereinstimmung eines Klartext- mit einem Geheimtextbuchstaben, was bei der Konstruktion der Enigma aber nicht vorkommen kann.

Durch diese Schwachstelle allein kann die Verschlüsselung der Enigma noch nicht gebrochen werden, allerdings kann, wenn die Position eines Wortes erst einmal bekannt ist, mit anderen Angriffen fortgefahren werden, zum Beispiel mit der im 3. Teil gezeigten known-plaintext-Angriff. Dieser gestaltet sich immer noch schwieriger als bei Vigenère, da sich, wie schon gesagt, der Schlüssel erst nach über 17.000 Zeichen wiederholt, aber da die Erzeugung der Verschlüsselung über die Rotoren auch wieder bestimmten Gesetzmäßigkeiten unterliegt, konnte sich die Gruppe um Turing Schritt für Schritt zur Entschlüsselung vorarbeiten. Turing konstruierte zur vollständigen Entschlüsselung des Geheimtextes elektromechanische Maschinen, die einen Schlüsselraum systematisch durchsuchten. Diese Maschinen wurden wegen ihres charakteristischen Tickens auch als Turing-Bomben bezeichnet. Die Menge der auszuprobierenden Schlüssel konnte durch Analysen wie die eben beschrieben negative Mustersuche stark eingeschränkt werden, was ein effektives Brechen der Verschlüsselung erst ermöglichte.

Enigma mit drei Walzen
Detail einer Enigma-Maschine mit drei Rotoren

Übrigens wurden teilweise von den Allierten sogar gezielt Maßnahmen durchgeführt, um bestimmte Funksprüche auszulösen, die dann einen bekannten Klartext beinhalteten, der dann für Angriffe wie die oben beschriebenen ausgenutzt wurde. So wird berichtet, dass gezielt Leuchtbojen bombardiert wurden, um Funksprüche wie “Leuchttonne ist erloschen” zu provozieren. [1] [2] Ein solches Vorgehen führt zu einem in der Kryptologie auch als chosen plaintext attack bezeichneten Angriff; also ein Angriff basierend auf durch den Angreifer ausgesuchten Klartext.

Doch was können wir aus diesen Betrachtungen über Rotormaschinen wie die Enigma für heute ableiten? Folgende Punkte haben nach wie vor Gültigkeit:

  • Viele Verschlüsselsalgorithmen basieren darauf, aus einem relativ kurzen Schlüssel eine lange Folge von Pseudo-Zufallszahlen zu erzeugen.
  • Nicht jede vermeintliche Verbesserung führt tatsächlich zu einer Erhöhung der Sicherheit, sondern manchmal sogar zu einer Verschlechterung.
  • Ein Verschlüsselungsalgorithmus ist schlecht, wenn es Angriffe gibt, die bedeutend effektiver sind als ein banales Ausprobieren aller möglichen Schlüssel. Gute Verschlüsselungsverfahren müssen gegen viele Arten von Angriffen resistent sein, darunter auch chosen plaintext attacks.

Wegen des zweiten Punktes gelten aktuelle Verschlüsselungsalgorithmen nur dann als sicher, wenn sie offengelegt sind und jahrelang von Wissenschaftlern auf mögliche Schwachstellen untersucht wurden.

In den kommenden Folgen werden wir uns neueren Verschlüsselungsverfahren der Gegenwart widmen.

Quellen und weiterführende Literatur:

[1] Reinhard Wobst: “Abenteuer Kryptologie”

[2] Friedrich L. Bauer: “Kryptologie : Methoden und Maximen”