3.3. Betriebsmodi für Blockchiffren#
Wir haben in diesem Kapitel verschiedene symmetrische Blockchiffren eingeführt, die Klartextblöcke entweder durch eine Substitution oder eine Permutation chiffrieren. Hierbei haben wir bisher die gleiche Verschlüsselungsfunktion auf alle Blöcke angewendet unabhängig von deren Position innerhalb des Klartexts. Dies führt leider dazu, dass gleiche Klartextblöcke (bei Verwendung des selben Schlüssels) immer zu gleichen Chiffretextblöcken verschlüsselt werden. Dies erleichtert die Kryptoanalyse solcher Kryptosysteme signifikant und erlaubt es potentiellen Angreifern Rückschlüsse auf den Klartext zu ziehen, z.B. durch die Anwendung von Häufigkeitsanalysen. Auch würden bekannte Teile des Klartexts im Sinne einer Known-plaintext Attacke, wie z.B. eine Grussformel, dazu führen, dass andere Teile des Chiffretexts entschlüsselt werden können oder in zukünftigen Nachrichten lesbar bleiben. Speziell bei Kryptosystemen mit öffentlichen Schlüsseln, wie z.B. das RSA-Kryptosystem, welches wir in dieser Vorlesung diskutieren werden, kann ein Angreifer jederzeit eine Chosen-plaintext Attacke durchführen, was bei fehlender Randomisierung dazu führt, dass durch genügendes Ausprobieren selbst komplexe Blockchiffren geknackt werden können.
Um dieses Problem zu lösen hat man in der Kryptographie sogenannte Betriebsmodi für Blockchiffren (im Englischen: Block cipher mode of operation) eingeführt. Diese Betriebsmodi geben klar an, wie eine Blockchiffre auf einen Klartext anzuwenden ist, der länger als die Blocklänge \(n \in \N\) der Blockchiffre ist und verschleiern potentielle Muster im resultierenden Chiffretext. Moderne Betriebsmodi, wie z.B. der Galois/Counter Mode Betriebsmodus, erlauben zudem eine gleichzeitige Authentifikation von Nutzern neben der Verschlüsselung.
Wie wir bereits wissen operieren Blockchiffren auf festen Blöcken der Länge \(n \in \N\). Ist \(\Sigma\) das zu Grunde liegende Alphabet, so hat man also folgende Verschlüsselungs- und Entschlüsselungsfunktionen \(E_k \in \mathcal{E}\) und \(D_k \in \mathcal{D}\) mit
in Abhängigkeit von einem frei wählbaren Parameter - dem geheimen Schlüssel \(k \in \mathcal{K}\). Man kann nun Blockchiffren in verschiedener Weise zum Verschlüsseln ganzer Texte einsetzen. Die gängigsten Verfahren in der Literatur sind:
Electronic Code Book (ECB) Modus
Cipher Block Chaining (CBC) Modus
Propagating Cipher Block Chaining (PCBC) Modus
Cipher Feedback Modus (CFM)
Output Feedback Modus (OFM)
Counter Modus (CM)
Wir werden uns in dieser Vorlesung nur kurz mit den ersten beiden Varianten beschäftigen, um das grundlegende Prinzip zu verdeutlichen.
ECB-Modus: Dies ist die einfachste Art, eine Blockchiffrierung auf einen Klartext \(m \in \mathcal{P}\) anzuwenden. Wir teilen den Text in Blöcke \(a_i\) der Länge \(n\in\N\) auf:
\[m=a_1|a_2|a_3|a_4|\dots.\]Anschließend verschlüsselt man den \(i\)-ten Block zu \(b_i=E_k(a_i)\) und erhält den verschlüsselten Text \(c = b_1|b_2|b_3|b_4|\dots\). Die Entschlüsselung erfolgt durch \(a_i=D_k(b_i)\). Im Prinzip haben wir in allen bisherigen Beispielen Blockchiffren im ECB-Modus angewendet. Ein Nachteil des ECB-Modus ist, dass Regelmäßigkeiten im Klartext zu Regelmäßigkeiten im verschlüsselten Text führen, was wiederum Rückschlüsse auf den Inhalt erlaubt.
(Modularer) CBC-Modus: Wir setzen als Alphabet \(\Sigma\simeq \{0,1,\dots,N-1\}\) voraus. Wir teilen den Text in Blöcke \(a_i\) der Länge \(n\in\N\) auf:
\[m=a_1|a_2|a_3|a_4|\dots,\]wobei wir uns \(a_i\in\Sigma^n\) als einen Vektor der Länge \(n\) vorstellen. Wir wählen einen sogenannten Initialisierungsvektor \(b_0\in \Sigma^n\) der Länge \(n\) und berechnen anschließend für jeden Block die Verschlüsselung
\[b_i = E_k(b_{i-1}+a_i \bmod N)\quad\text{ für }\quad i\ge 1,\]wobei die Addition der Vektoren komponentenweise gemeint ist. Der verschlüsselte Text wird somit \(c = b_0|b_1|b_2|b_3|b_4|\dots\). Wegen
\[D_k(b_i) = D_k(E_k(b_{i-1}+a_i \bmod N)) = b_{i-1}+a_i \bmod N\]erhält man mit der Formel
\[a_i=D_k(b_i)-b_{i-1} \bmod N\]den ursprünglichen Klartext zurück.
Bemerkung 3.7 (XOR Operation)
Die oben beschriebene Variante des normalen CBC-Modus verwendet modulare Arithmetik, um einen Klartextblock mit dem Chiffrat des letzten Klartextblocks zu verrechnen. Dies macht es für uns möglich diesen Betriebsmodus auch leicht manuell anzuwenden.
Die Standardimplementierung des CBC-Modus funktioniert jedoch anders und operiert direkt auf einer Byterepräsentation von Klar- und Chiffretexten. Hierbei wird ein Klartextblock \(a_i\) mit dem Chiffrat des letzten Klartextblocks \(b_{i-1}\) mittels des bitweisen XOR Operators miteinander verrechnet via:
wobei bitweise eine boolsche exklusive Oder-Operation durchgeführt wird, die durch folgende Tabelle beschrieben wird:
\(a\) |
\(b\) |
\(a \oplus b\) |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
Hierbei ist zu beachten, dass für die XOR-Operation gilt \(a_i \oplus a_i = 0\). Außerdem sieht man aus diesem Grund leicht ein, dass diese Operation zu sich selbst invers ist, d.h. es gilt \((a_i \oplus b_i) \oplus b_i = a_i\) und \((a_i \oplus b_i) \oplus a_i = b_i\), was sie zu einem wichtigen Werkzeug für symmetrische Kryptosysteme macht.
Eine wichtige Beobachtung ist, dass im Fall des CBC-Modus verschiedene Initialisierungsvektoren bei gleichem Schlüssel zu verschiedenen Chiffretexten führen. Dies führt zu einer Randomisierung des verschlüsselten Texts, die die Kryptoanalyse von Blockchiffren signifikant schwieriger macht, da sie wiederkehrende Muster, selbst bei gleichen Klartexten, verhindert.
Bemerkung 3.8 (Übertragung des Initialisierungsvektors)
Um der empfangenden Partei es zu ermöglichen den Chiffretext bei Kenntnis des geheimen Schlüssels zu dechiffrieren, muss natürlich auch der Initialisierungsvektor übermittelt werden. Der Initialisierungsvektor selbst muss dabei nicht geheim gehalten werden, da er alleine nicht ausreicht um den Chiffretext zu entschlüsseln. Er sollte jedoch zufällig (d.h unvorhersehbar) und für jede verschlüsselte Nachricht neu erzeugt werden, um wirklich Sicherheit zu bieten.
Häufig wird der Initialisierungsvektor als erster Block \(b_0\) des Chiffretexts \(c = b_0 b_1 \dots\) übertragen.
3.3.1. Kontextabhängige Verschlüsselung#
Einige der typischen Betriebsmodi für Blockchiffren verschleiern Muster im Chiffretext indem iterative Verkettungsmechanismen oder ein sich nicht wiederholender Schlüsselstrom ausgenutzt wird. Dies führt zu einer kontextabhängigen Verschlüsselung, da das Chiffrat eines Klartextblocks von seinem Kontext abhängt.
Diese verschleiernde Wirkung stimmt mit dem Ziel von polyalphabetischen Substitutionschiffren überein, bei denen mit Hilfe mehrerer Chiffre-Alphabete verhindert wird, dass gleiche Klartextzeichen zu gleichen Chiffretextzeichen verschlüsselt werden und somit die Sicherheit des Kryptosystems erhöht wird.
Betriebsmodi wie der CBC-Modus oder Counter-Modus emulieren in gewisser Weise eine Polyalphabetie. Beim CBC-Modus wird jeder Klartextblock mit dem vorherigen Chiffretextblock XOR-verknüpft, bevor er verschlüsselt wird. Dadurch hängt der resultierende Chiffretext von allen vorhergehenden Blöcken ab. Beim Counter-Modus wird ein eindeutiger Zählerwert verschlüsselt, um einen sicheren Schlüsselstrom (siehe Stromchiffren) zu erzeugen. Dies macht die Verschlüsselung eines Blocks kontextabhängig.
Es ist wichtig zu verstehen, dass diese Betriebsmodi eine kontextabhängige Verschlüsselung nicht durch die Verwendung verschiedener Chiffrealphabete in der Blockchiffre realisiert, sondern durch kryptografische Operationen innerhalb des Betriebsmodus selbst. Auch ist zu beachten, dass nicht alle Betriebsmodi eine kontextabhängige Verschlüsselung gewährleisten. Der ECB-Modus zum Beispiel verhält sich streng monoalphabetisch, d.h., gleiche Klartextblöcke werden immer zu gleichen Chiffretextblöcken verschlüsselt.
3.3.2. Padding#
Die abschließende Frage zur Nutzung von Betriebsmodi für Blockchiffren lautet, was man tun soll wenn die Zeichenzahl des Klartextes nicht durch die Blocklänge \(n\in\N\) teilbar ist, d.h. wenn der letzte Block weniger als \(n\) Zeichen hat. In diesem Fall kann die Verschlüsselungsfunktion \(E_k \in \mathcal{E}\) auf den letzten Block nicht angewendet werden.
Eine gängige Möglichkeit zur Lösung des Problems besteht im sogenannten Auffüllen oder Puffern (im Englischen: padding), was wir im Folgenden für Blocklängen \(n \le 255\) beschreiben wollen.
Wir nehmen an, wir haben eine Datei, die aus \(N\in\N\) Bytes besteht. Wir zerlegen mittels Division mit Rest die Anzahl der Bytes in \(N=\ell n + r\) mit \(0\le r<n\), so dass also \(r\) die Anzahl der Bytes im unvollständigen, letzten Block oder \(0\) ist. Wir ergänzen jetzt den letzten Block durch \(n-r-1\) beliebige Bytes (idealerweise zufällig erzeugt) und hängen dann noch ein Byte an, das die Zahl \(n-r\) (also die Anzahl der aufgefüllten Bytes) codiert. Der vervollständigte Klartext kann jetzt mit einem Betriebsmodus für Blockchiffren verschlüsselt werden. Nach dem Entschlüsseln gibt das letzte Byte bei dieser Konvention an, wie viele Bytes zu streichen sind, damit man den exakten Ausgangstext wieder erhält.