CBC in Python: Cipher Block Chaining Schritt für Schritt

Was du hier lernst

XOR-Verknüpfung
bytes und bytearray
Blöcke mit Slices
Initialisierungsvektor
Zufall: random und secrets
Hexadezimaldarstellung

Die Erklärung stammt – leicht überarbeitet für Python 3 – aus dem Buch „Coding for Fun mit Python“ von Lars Heppert, Kapitel 4, Ende von Abschnitt 4.7 und Abschnitt 4.8.

Blöcke verketten

Die Vigenère-Verschlüsselung hat eine Schwäche: Jeder x-te Buchstabe wird mit demselben Passwortbuchstaben verschlüsselt, und die Häufigkeitsverteilung der Sprache schimmert durch. Eine Möglichkeit, das Verfahren zu stärken, ist das Verknüpfen der einzelnen Datenblöcke. Du könntest zum Beispiel jeden Block per XOR mit dem jeweils vorhergehenden Block verknüpfen, wobei die Länge eines Blocks der Länge des Passwortes entsprechen sollte. Auch diese Art der Verknüpfung verschleiert die Häufigkeiten. Am besten ist natürlich die Kombination aus allen Verfahren, welche die Häufigkeitsverteilung verschleiern.

Zusätzlich ist es sinnvoll, den ersten Block zufällig zu initialisieren, denn so lassen sich keine Annahmen über den Ausgangsblock treffen. Im Fachjargon ist die Verknüpfung der Blöcke als CBC bekannt, was für »Cipher Block Chaining« steht. CBC war jahrzehntelang der beliebteste Modus für Blockchiffren wie DES und AES.

CBC – Cipher Block Chaining

CBC ist also die Verknüpfung aufeinanderfolgender Blöcke mittels XOR. Die Blockgröße kann dabei variieren, in der Regel entspricht sie der Blockgröße der verwendeten Blockchiffre – bei AES sind das 16 Bytes.

Zwei Blöcke per XOR verknüpfen

Zwei Blöcke beliebiger Größe lassen sich mit der folgenden Funktion leicht miteinander verknüpfen:

def blockXOR(a, b):
    result = []
    for x in range(len(a)):
        result.append(a[x] ^ b[x])

    return bytes(result)

Der Operator ^ verknüpft zwei Zahlen Bit für Bit mit »exklusivem Oder«: Ein Ergebnisbit ist genau dann 1, wenn die beiden Eingangsbits verschieden sind. Das Schöne an XOR: Zweimal angewendet hebt es sich wieder auf. Aus a ^ b ^ b wird wieder a. Genau das zeigen die ersten drei Zeilen in der Konsole: Aus c = a XOR b kommt mit c XOR a wieder b heraus und mit c XOR b wieder a. Und wo zwei gleiche Zeichen aufeinandertreffen, etwa zwei Leerzeichen, entsteht eine Null – in der Ausgabe als \x00 zu sehen.

Die Funktion ist so ausgelegt, dass sie zwei gleich große Blöcke erwartet, weshalb auf eine Überprüfung der Größe von b verzichtet wurde. Falls du etwas mehr Sicherheit wünschst, fügst du noch eine Überprüfung ein. Eine andere Möglichkeit wäre, dass bei zwei unterschiedlich großen Blöcken der kleinere die Anzahl der Stellen vorgibt. Alternativ könnte der kleinere Block auch wieder von vorn verwendet werden, so wie du es bei der Vigenère-Chiffre mit dem Passwort schon erlebt hast.

Verschlüsseln mit cbcForward()

Die Blockverknüpfung verwendest du nun in einer Funktion, die eine größere Datenmenge in Blöcke teilt und verkettet:

def cbcForward(blockLength, data, initVector):
    dataLength  = len(data)
    blockCount  = dataLength // blockLength
    vector      = initVector
    index       = 0
    cbcResult   = []

    while index < blockCount:
        start   = index * blockLength
        end     = start + blockLength
        block   = data[start:end]
        vector  = blockXOR(block, vector)
        index  += 1

        cbcResult.append(vector)

    remainder   = dataLength % blockLength
    if remainder > 0:
        block   = data[-remainder:]
        plain   = blockXOR(block, vector[0:remainder])

        cbcResult.append(plain)

    return b"".join(cbcResult)

Zunächst ermittelt die Funktion die Gesamtlänge dataLength der Daten und daraus per Ganzzahldivision die Anzahl der ganzen Blöcke. Der dabei möglicherweise anfallende Rest fällt nicht unter den Tisch, sondern wird am Ende separat behandelt. Die Variable vector enthält jeweils den vorherigen Block, der als Nächstes verknüpft werden soll – am Anfang ist das der Initialisierungsvektor.

In der while-Schleife wird zuerst der Start des aktuellen Blocks ermittelt, indem die Blocklänge mit dem aktuellen Index multipliziert wird. Das Ende ergibt sich durch Addition der Blocklänge. Der zu verarbeitende Block wird als Slice in die Variable block kopiert. Dann wird blockXOR() mit dem aktuellen Block und dem Inhalt von vector aufgerufen. Die Rückgabe wird wieder vector zugewiesen, dadurch enthält vector für den nächsten Block das Ergebnis aller vorherigen Verknüpfungen. Zum Schluss wird der Block an cbcResult angehängt und der Index um eins erhöht.

Nach der Schleife bleibt eventuell ein Rest, der keinen ganzen Block mehr füllt. Für diese Daten wird das letzte Verknüpfungsergebnis nur in dem Umfang angewendet, der für den Rest nötig ist. Am Ende fügt b"".join() alle Blöcke zu einer einzigen Bytefolge zusammen.

Schema mit drei Stufen: Klartextblock XOR Initialisierungsvektor beziehungsweise vorheriger Geheimtextblock, dann eine Blockchiffre mit Schlüssel, darunter der Geheimtextblock, der zur nächsten Stufe weitergereicht wird — Abbildung 4.7 aus dem Buch: Cipher Block Chaining

Schau dir die Abbildung genau an: Zwischen dem XOR und dem Geheimtext sitzt dort noch ein Kasten »Block Cipher Encryption« mit einem Schlüssel. Unsere Funktion setzt nur die Verkettung um, also den Betriebsmodus. Warum der Kasten so wichtig ist, zeigt sich gleich.

Entschlüsseln mit cbcBackward()

Die Umkehrung übernimmt die Funktion cbcBackward():

    while index < blockCount:
        start   = index * blockLength
        end     = start + blockLength
        block   = data[start:end]
        plain   = blockXOR(block, vector)
        vector  = block
        index  += 1

        cbcResult.append(plain)

Auf den ersten Blick sieht die Schleife genauso aus wie in cbcForward(), aber es gibt einen Unterschied: Das Ergebnis der Verknüpfung ist nicht der Block für die nächste Operation. Für die nächste Verknüpfung wird der Block so verwendet, wie er in den Daten steht – deshalb bekommt vector hier den Slice block und nicht das Ergebnis plain. Alles andere ist identisch, auch die Behandlung des Restes. Die Daten werden übrigens auch hier von vorn durchlaufen. Insofern ist der Name etwas irreführend, aber er zeigt gut, dass es sich um zwei entgegengesetzte Funktionen handelt.

Der Initialisierungsvektor

Der initVector ist ein zufälliger Block, der als Verknüpfungsblock für den ersten Block dient. Er wird entsprechend der verketteten Verknüpfung über die gesamte Datenmenge »gestempelt« und wird auch zum Entschlüsseln gebraucht. Erzeugt wird er so:

def generateInitVector(blockLength):
    vector = []
    for x in range(blockLength):
        randomByte = random.randint(0, 255) ^ x
        vector.append(randomByte)

    return bytes(vector)

Die XOR-Verknüpfung der Zufallszahl mit x ist dabei nicht von Bedeutung. Mir missfiel einfach, dass Eclipse die nicht verwendete Variable x bemängelte. Natürlich hatte ich vorher überlegt, ob diese Verknüpfung die Zufallszahlen verschlechtern könnte, und beschloss, dass sie das nicht tut. Heute würde man für eine Schleifenvariable, die man nicht braucht, einfach einen Unterstrich schreiben: for _ in range(blockLength).

Wichtiger ist etwas anderes: Diese Art, einen Zufallsvektor zu erzeugen, ist nicht sicher. Computer arbeiten deterministisch, und Zufallszahlengeneratoren in Software folgen einer festen Regel. Man spricht von Pseudozufallszahlen. random ist für Simulationen und Spiele gedacht, nicht für Kryptographie. Für ernsthafte Zwecke gibt es spezielle, kryptografisch sichere Generatoren, die echte Zufallsquellen einbeziehen, zum Beispiel das Rauschen von Hardware. In Python ist das seit Version 3.6 das Modul secrets – die Variante »Echter Zufall für den Vektor« zeigt, wie es geht.

Ausprobieren

Mit den folgenden Aufrufen testest du die Funktionen:

blockLength = 8
initVector  = generateInitVector(blockLength)
message     = a
encrypted   = cbcForward(blockLength, message, initVector)
print("initVector  =", initVector.hex(" "))
print("cbcForward  =", encrypted.hex(" "))

Die verschlüsselten Bytes sind meist keine lesbaren Zeichen, deshalb zeigt .hex(" ") sie als Hexadezimalzahlen. Und jetzt lohnt ein genauer Blick auf die Konsole: Die Bytes 9 bis 16 des Geheimtexts sind exakt der Initialisierungsvektor! Die Animation entdeckt das auch und markiert die Paare in Farbe.

Warum die Verkettung allein nicht reicht

Unser Text »ABC ABC ABC …« besteht aus lauter gleichen Blöcken P. Der erste Geheimtextblock ist P XOR IV, der zweite ist P XOR (P XOR IV) – und weil sich XOR selbst aufhebt, bleibt davon nur der IV übrig. Schlimmer noch: Jeder Geheimtextblock ist der Vorgänger des nächsten. Wer die Daten abfängt, rechnet einfach Geheimtextblock XOR vorheriger Geheimtextblock und liest ab dem zweiten Block alles mit, ganz ohne Schlüssel. Das Geheimnis steckt in Abbildung 4.7 im Kasten »Block Cipher Encryption«: Erst eine Blockchiffre mit Schlüssel macht aus der Verkettung eine Verschlüsselung. CBC selbst ist nur der Betriebsmodus, der festlegt, wie die Blöcke zusammenhängen. Unter »Probier mal« setzt du die Vigenère-Chiffre als Blockchiffre ein.

Was passiert bei Übertragungsfehlern?

In der gedruckten Fassung hatte ich geschrieben, dass bei Übertragungsfehlern alle nach dem Fehler folgenden Daten verloren sind, weil jeder Block von allen Vorgängerblöcken abhängt. Das stimmt nur zur Hälfte. Beim Verschlüsseln gilt es: Ändert sich ein Byte im ersten Klartextblock, ändern sich alle folgenden Geheimtextblöcke. Beim Entschlüsseln braucht jeder Block aber nur seinen direkten Vorgänger, so wie er übertragen wurde. Ein gekipptes Bit verdirbt deshalb genau zwei Blöcke, danach stimmt alles wieder. Die Variante »Ein Übertragungsfehler« zeigt das: Zwei Zeichen werden rot, der Rest ist korrekt.

CBC heute

CBC ist nach wie vor in vielen Protokollen und Dateiformaten zu finden, hat aber an Bedeutung verloren. Gegen CBC in SSL und TLS gab es mehrere Angriffe, etwa »Lucky Thirteen« (2013) und »POODLE« (2014). Das aktuelle TLS 1.3 kennt CBC gar nicht mehr und setzt ausschließlich auf authentifizierte Verfahren wie AES-GCM oder ChaCha20-Poly1305. Die verschlüsseln nicht nur, sondern merken auch, wenn unterwegs jemand ein Bit verändert hat.

Ein kleiner Wettkampf

Jetzt hast du genug Informationen, um ein bisschen zu basteln und weiterzuentwickeln. Interessant ist sicherlich ein kleiner Wettkampf unter Kollegen oder Freunden, bei dem jeder ein einfaches Verfahren entwickelt, das die anderen knacken müssen. Legt dafür ein paar Einschränkungen bei den erlaubten Operationen fest – am spannendsten sind sehr einfache Verfahren, deren Funktionsweise klar nachvollziehbar ist, die aber trotzdem nicht leicht zu knacken sind.

Das Bild zum Programm

Die Animation ist neu auf dieser Website. chainRows() teilt Klartext und Geheimtext in Zeilen auf: links der Klartextblock, in der Mitte sein Vorgänger – zuerst der IV, danach jeweils der vorige Geheimtextblock –, rechts das Ergebnis. Der orangefarbene Pfeil zeigt, wie jeder fertige Geheimtextblock zum Vorgänger der nächsten Zeile wird.

Jedes Byte bekommt eine eigene Farbe. byteColor() multipliziert den Bytewert mit dem Goldenen Schnitt und nimmt davon die Nachkommastellen als Farbton. So bekommen gleiche Bytes immer dieselbe Farbe, benachbarte Werte wie »A« und »B« aber deutlich verschiedene. Am Ende sucht repeats() nach Geheimtextblöcken, die dem IV oder einem früheren Block gleichen, und rahmt jedes Paar in einer eigenen Farbe ein.

Bis hierher haben alle Verfahren denselben Haken: Sender und Empfänger müssen vorher einen Schlüssel austauschen. Wie man ohne Schlüsselaustausch auskommt, zeigt die RSA-Verschlüsselung.

Probier mal

Jede Variante ändert den Code oben. Ein Klick auf »Ausprobieren« übernimmt die Änderung in den Editor und startet das Programm. »Zurücksetzen« holt das Original zurück.

01Mitlesen ohne Schlüssel

Ohne Blockchiffre ist die Kette keine echte Verschlüsselung: Jeder Geheimtextblock ist ja der Vorgänger des nächsten. Ein Angreifer ruft deshalb einfach cbcBackward() auf und nimmt den ersten Geheimtextblock als Initialisierungsvektor. Die neue Zeile in der Konsole zeigt: Ab dem zweiten Block liest er alles mit.
```
- print("cbcBackward =", decrypted)
+ print("cbcBackward =", decrypted)
+ 
+ # Ein Angreifer kennt den IV nicht – und liest trotzdem fast alles mit
+ guessed = cbcBackward(blockLength, received[blockLength:], received[:blockLength])
+ print("Angreifer   =", guessed)
```

02Mit Blockchiffre wie in Abbildung 4.7

In Abbildung 4.7 steckt zwischen XOR und Geheimtext eine »Block Cipher Encryption« mit Schlüssel. Hier übernimmt die Vigenère-Verschlüsselung aus Abschnitt 4.7 diese Rolle, mit einem Passwort so lang wie ein Block. Jetzt wiederholt sich kein Block mehr, und der Angriff aus der ersten Variante liefert nur noch Zeichensalat.

- def cbcForward(blockLength, data, initVector):
+ password = b"Coding4F"  # der Schlüssel der Blockchiffre: so lang wie ein Block
+ 
+ 
+ def encryptBlock(block):
+     # die Vigenère-Chiffre aus Abschnitt 4.7 als (sehr einfache) Blockchiffre
+     return bytes((block[i] + password[i]) % 256 for i in range(len(block)))
+ 
+ 
+ def decryptBlock(block):
+     return bytes((block[i] - password[i] + 256) % 256 for i in range(len(block)))
+ 
+ 
+ def cbcForward(blockLength, data, initVector):
-         vector  = blockXOR(block, vector)
+         vector  = encryptBlock(blockXOR(block, vector))
-         plain   = blockXOR(block, vector)
+         plain   = blockXOR(decryptBlock(block), vector)
- operation      = "XOR"
+ operation      = "XOR, dann Vigenère"

03Ein Übertragungsfehler

Unterwegs kippt ein einziges Bit im ersten Geheimtextblock. Beim Entschlüsseln trifft der Fehler genau zwei Stellen: das Zeichen im selben Block und das an derselben Position im nächsten Block. Danach stimmt alles wieder, denn jeder Block braucht zum Entschlüsseln nur seinen direkten Vorgänger.
```
- received    = encrypted  # so kommt der Geheimtext beim Empfänger an
+ received    = bytearray(encrypted)  # so kommt der Geheimtext beim Empfänger an …
+ received[3] ^= 1                    # … nur ein einziges Bit ist unterwegs gekippt
+ received    = bytes(received)
```
04Kürzere Blöcke

Mit vier Bytes pro Block passt »ABC␣« genau in einen Block. Jetzt wiederholt sich das Muster Schlag auf Schlag: Initialisierungsvektor, Block 1, Initialisierungsvektor, Block 1 … Gleiche Klartextblöcke heben sich beim zweiten XOR einfach wieder auf.
```
- blockLength = 8
+ blockLength = 4
```
05Echter Zufall für den Vektor

Das Modul random ist für Simulationen und Spiele gedacht: Wer genug Ausgaben kennt, kann die folgenden Zahlen vorhersagen. Für Kryptographie gibt es seit Python 3.6 das Modul secrets. Es holt die Zufallsbytes aus einer kryptografisch sicheren Quelle, im Browser aus crypto.getRandomValues().
```
- import random
+ import random
+ import secrets
- initVector  = generateInitVector(blockLength)
+ initVector  = secrets.token_bytes(blockLength)  # kryptografisch sicherer Zufall
```

Vom Buch in den Browser

Die vier Funktionen und die Testaufrufe stammen aus den Listings 4.27 bis 4.31, auf der CD als Kapitel04/cbc.py. Neu für die Website sind die Variablen message und received sowie die Animation mit chainRows(), repeats(), drawBlock() und drawScene().

Im Buch	Hier
Strings mit `chr()` und `ord()`	`bytes`, Einzelwerte sind schon Zahlen
`a = "ABC ABC …"`	`a = b"ABC ABC …"`
`blockCount = dataLength / blockLength`	`blockCount = dataLength // blockLength`
`xrange(…)`	`range(…)`
`"".join(cbcResult)`	`b"".join(cbcResult)`
`random.randint(0, 256)`	`random.randint(0, 255)`
`cbcForward = cbcForward(…)`	`encrypted = cbcForward(…)`
Geheimtext als Zeichensalat ausgegeben	als Hexadezimalzahlen mit `.hex(" ")`

Bytes statt Strings. In Python 2 war ein String eine Folge von Bytes, deshalb rechnete blockXOR() mit ord() und chr(). In Python 3 ist ein String eine Folge von Unicode-Zeichen, und für rohe Daten gibt es den Typ bytes. Das macht den Code sogar kürzer: a[x] liefert bei bytes direkt eine Zahl zwischen 0 und 255, ^ verknüpft zwei solche Zahlen, und bytes(result) baut aus der Liste wieder eine Bytefolge. Deshalb beginnen die Ausgaben in der Konsole mit b'…': Das ist die Schreibweise für bytes.

Ein Fehler weniger im Initialisierungsvektor. Im Buch steht random.randint(0, 256). Anders als range() schließt randint() die obere Grenze ein und liefert also auch 256 – ein Wert, der in kein Byte passt. In Python 2 brach chr(256) dann mit einem ValueError ab, bei acht Bytes in etwa drei von hundert Läufen. Die Portierung nimmt randint(0, 255). Das ^ x aus dem Buch bleibt erhalten: Es kann den Wertebereich 0 bis 255 nicht verlassen.

Ein Name, zwei Bedeutungen. Im Buch überschreibt die Zeile cbcForward = cbcForward(blockLength, a, initVector) die Funktion mit ihrem eigenen Ergebnis. Das funktioniert genau einmal – ein zweiter Aufruf wäre danach nicht mehr möglich. Hier heißt das Ergebnis encrypted.

Ganzzahldivision. dataLength / blockLength liefert in Python 3 eine Kommazahl: 23 / 8 ergibt 2.875. Die Bedingung while index < blockCount gilt dann auch noch für den Index 2, die Schleife behandelt den Rest wie einen ganzen Block – und danach noch einmal als Rest. Der Geheimtext wäre 30 statt 23 Bytes lang. Die Ganzzahldivision // liefert, was gemeint ist: die Anzahl der ganzen Blöcke.

message und received. Im Buch wird direkt a verschlüsselt und der Geheimtext direkt entschlüsselt. Die beiden zusätzlichen Variablen machen es leicht, unter »Probier mal« eine andere Nachricht einzusetzen oder einen Übertragungsfehler einzubauen.

Original aus dem Buch ansehen cbc.py · Python 2

'''
Created on 08.12.2009

@author: GWV7FD3
'''

def blockXOR(a, b):
    result = []
    for x in xrange(len(a)):
        result.append(chr(ord(a[x]) ^ ord(b[x])))
        
    return "".join(result)

import random
def generateInitVector(blockLength):
    vector = []
    for x in xrange(blockLength):
        randomByte = chr(random.randint(0, 256) ^ x)
        vector.append(randomByte)
    
    return "".join(vector)

def cbcForward(blockLength, data, initVector):
    dataLength  = len(data)
    blockCount  = dataLength / blockLength
    vector      = initVector
    index       = 0
    cbcResult   = []
    
    while index < blockCount:
        start   = index * blockLength
        end     = start + blockLength
        block   = data[start:end]
        vector  = blockXOR(block, vector)
        index  += 1
    
        cbcResult.append(vector)
        
    remainder   = dataLength % blockLength
    if remainder > 0:
        block   = data[-remainder:]
        plain   = blockXOR(block, vector[0:remainder])
        
        cbcResult.append(plain)
        
    return "".join(cbcResult)
    
def cbcBackward(blockLength, data, initVector):
    dataLength  = len(data)
    blockCount  = dataLength / blockLength
    vector      = initVector
    index       = 0
    cbcResult   = []
    
    while index < blockCount:
        start   = index * blockLength
        end     = start + blockLength
        block   = data[start:end]
        plain   = blockXOR(block, vector)
        vector  = block
        index  += 1
    
        cbcResult.append(plain)
        
    remainder   = dataLength % blockLength
    if remainder > 0:
        block   = data[-remainder:]
        plain   = blockXOR(block, vector[0:remainder])
        
        cbcResult.append(plain)
        
    return "".join(cbcResult)

a = "ABC ABC ABC ABC ABC ABC"
b = "123 456 789 123 456 789"
c = blockXOR(a, b)
print "a XOR b = c =", c
print "c XOR a = b =", blockXOR(c, a)
print "c XOR b = a =", blockXOR(c, b)

blockLength = 8
initVector  = generateInitVector(blockLength)
cbcForward  = cbcForward(blockLength, a, initVector)
print "cbcForward  =", cbcForward
print "cbcBackward =", cbcBackward(blockLength, cbcForward, initVector)

Was du hier lernst

Blöcke verketten

CBC – Cipher Block Chaining

Zwei Blöcke per XOR verknüpfen

Verschlüsseln mit cbcForward()

Entschlüsseln mit cbcBackward()

Der Initialisierungsvektor

Ausprobieren

Was passiert bei Übertragungsfehlern?

CBC heute

Das Bild zum Programm

Probier mal

01Mitlesen ohne Schlüssel

02Mit Blockchiffre wie in Abbildung 4.7

03Ein Übertragungsfehler

04Kürzere Blöcke

05Echter Zufall für den Vektor

Vom Buch in den Browser

Passt dazu

Vigenère-Verschlüsselung

RSA-Verschlüsselung

Skytale von Sparta