4.5. VERNAM-Verschlüsselung#
In diesem Abschnitt widmen wir uns einer Stromchiffre die besonders effizient in Computerhardware zu realisieren ist und unter Einhaltung einiger Voraussetzungen nicht durch eine Kryptoanalyse gebrochen werden kann und als informationstheoretisch sicher gilt. Die Idee bei der sogenannten VERNAM-Verschlüsselung ist es einen Klartext in binärer Codierung durch eine bitweise XOR Operation mit einem Schlüsselstrom zu verrechnen. Somit funktioniert dieses Kryptosystem analog zu Algorithmus 4.1 mit dem Unterschied, dass auf Ebene der kleinsten Informationseinheiten (den Bits) verschlüsselt wird.
Algorithmus 4.5 (VERNAM-Verschlüsselung:)
Wir wählen als zu Grunde liegendes Alphabet \(\Sigma\) die beiden möglichen Zustände eines Bits \(\Sigma = \{0,1\}\).
Schlüsselraum: Als Schlüssel dient ein Schlüsselstrom \(s \in \mathcal{K} = \Sigma^*\) bestehend aus Bits, der mindestens die Länge des zu chiffrierenden Klartexts besitzt.
Verschlüsselung: Den zu verschlüsselnden Klartext \(m \in \mathcal{P}\) fassen wir als Bitfolge \(m = a_1 a_2 a_3 \dots\) mit \(0\le a_i\le 1\) auf. Dieser wird nun durch ein boolsches exklusives-Oder bzw. durch die XOR Operation in Bemerkung 3.7 bitweise mit dem Schlüsselstrom durch
\[b_i \ = \ a_i \oplus s_i\]zur Bitfolge des Chiffretexts \(c = b_1 b_2 b_3 \dots\) verschlüsselt. Dies ist äquivalent zu einer einfachen Addition mit Modulus \(2\):
\[b_i \ = \ a_i + s_i \bmod 2.\]Entschlüsselung: Die Entschlüsselung funktioniert auf Grund der Eigenschaft, dass die XOR Operation invers zu sich selbst ist, genauso wie die Verschlüsselung durch
\[a_i \ = \ b_i \oplus s_i.\]Alternativ kann auch die modulare Arithmetik nutzen und die Entschlüsselung berechnen als:
\[a_i = b_i + s_i \bmod 2.\]
Das VERNAM-Kryptosystem hat schöne theoretische Eigenschaften aus Sicht der Kryptoanalyse, wie wir im Folgenden feststellen.
Bemerkung 4.3 (Kryptoanalyse für die VERNAM-Verschlüsselung)
Da die VERNAM-Verschlüsselung in Algorithmus 4.5 auf der bitweisen XOR-Operation basiert, ist dieses Kryptosystem nur unter den Voraussetzungen sicher, dass der verwendete Schlüsselstrom \(s = s_1 s_2 s_3 \dots\):
nur ein einziges Mal verwendet wird,
zufällig erzeugt wird.
Unter Berücksichtigung dieser beiden Voraussetzungen spricht man auch von einer sogenannten One-Time-Pad (OTP)-Verschlüsselung. Der Name leitet sich daraus ab, dass die zufällig generierte Bitfolge nur einmalig verwendet werden darf um Sicherheit zu gewährleisten. Zur Erzeugung des Schlüsselstroms im One-Time-Pad kann beispielsweise ein Pseudo-Zufallszahlengenerator genutzt werden.
Sollte eine dieser Annahmen verletzt sein, so bietet die OTP-Verschlüsselung keine Sicherheit mehr, wie wir im Folgenden diskutieren wollen.
Nehmen wir zunächst an, dass der zufällig generierte Schlüsselstrom mehrfach verwendet wird. Kann ein Angreifer zwei Chiffretexte \(c_1, c_2 \in \mathcal{C}\) abfangen, die beide mit dem gleichen Schlüsselstrom \(s \in \mathcal{K}\) OTP-verschlüsselt wurden, so wissen wir
\[c_1 \ = \ m_1 \oplus s, \quad c_2 \ = \ m_2 \oplus s.\]Die XOR Operation \(\oplus\) auf Klartext und Schlüsselstrom wird hier bitweise durchgeführt.
Verrechnet der Angreifer nun die beiden Chiffretexte mittels der XOR Operation, so ergibt sich aus der Assoziativität und der Eigenschaft der Selbstinversen des exklusiven-Oders:
\[c_1 \oplus c_2 \ = \ (m_1 \oplus s) \oplus (m_2 \oplus s) \ = \ (m_1 \oplus m_2) \oplus \underbrace{(s \oplus s)}_{=\, 0} \ = \ m_1 \oplus m_2.\]Man erhält also eine Mischung der beiden zu \(c_1\) und \(c_2\) zugehörigen Klartexte. Kennt man nun einen der beiden Klartexte im Sinne einer Known plaintext oder sogar Chosen plaintext Attacke, so kann man das Resultat mit einem dem bekannten Klartext verrechnen, um auf den anderen Klartext zu schließen, d.h. es gilt:
\[(c_1 \oplus c_2) \oplus m_1 \ = \ (m_1 \oplus m_2) \oplus m_1 \ = \ m_2 \oplus \underbrace{(m_1 \oplus m_1)}_{=\, 0} \ = \ m_2.\]Auch lässt sich so der zu Grunde liegende geheime Schlüsselstrom für zukünftige Entschlüsselungen rekonstruieren als:
\[c_1 \oplus m_1 \ = \ (m_1 \oplus s) \oplus m_1 \ = \ s \oplus \underbrace{(m_1 \oplus m_1)}_{=\, 0} \ = \ s.\]Ist keiner der beiden Klartexte \(m_1\) und \(m_2\) bekannt, so lassen sich aus der entstehenden Bitfolge \(m_1 \oplus m_2\) dennoch häufig Muster in den Klartexten ableiten. Fangen beide Klartexte beispielsweise mit der Grußformel Sehr geehrte Damen und Herren, so drückt sich dies durch eine statistisch auffällige lange Bitfolge von Nullen am Anfang von \(m_1 \oplus m_2\) aus. Ebenso lassen sich einzelne übereinstimmende Zeichen in beiden Chiffretexten zählen und so eine Häufigkeitsanalyse durchführen, womit Teile des geheimen Schlüsselstroms rekonstruiert werden können.
Ist ein Schlüsselstrom im One-Time-Pad nicht zufällig erzeugt, so kann ein Angreifer unter Umständen einen deterministischen Weg finden den gleichen Schlüsselstrom zu erzeugen und somit einen abgefangenen Chiffretext entschlüsseln.
Noch schlimmer wäre es wenn ein Schlüsselstrom aus einem vorher genutzten Schlüsselstrom erzeugt wurde, z.B. durch Inversion aller Bits oder durch dass Addieren einer festen Binärzahl. In diesem Fall lassen sich mit einer ähnlichen Argumentation wie oben wieder Rückschlüsse auf die zu Grunde liegenden Klartexte ziehen.
Obwohl die Verschlüsselung mittels eines One-Time-Pads unter Einhaltung aller Voraussetzungen theoretisch unknackbar ist, bringt sie dennoch einige Nachteile mit sich. Das größte Problem dieses Kryptosystems ist der sichere Austausch und die sichere Verwahrung des geheimen Schlüsselstroms, da dieser bei jeder verschlüsselten Kommunikation neu und sicher ausgetauscht werden muss. Darüber hinaus ist die Erzeugung von hinreichend großen, echt zufälligen Schlüsselströmen eine technische Herausforderung.