Symmetrische Verschlüsselung [KSR Wiki]

Wir können nun beliebige Zeichenfolgen codieren und mit einer XOR-Operation verschlüsseln. Die Verschlüsselung erfolgt dabei blockweise, wobei jeder Block genau die Länge des Schlüssels hat. Die Verschlüsselung folgt diesem Schema:

Beispielsweise verschlüsseln wir einen Text mit dem Schlüssel ZUSE:

    |EINE| SEH|R KL|EINE| SEN|SATI|ON|
XOR |ZUSE|ZUSE|ZUSE|ZUSE|ZUSE|ZUSE|ZU|

    |@-. |ZFVM|HUXI|@-. |ZFVK|ITGL|U,|

Was fällt dabei auf?

Lösung:

Warum ist das ein Problem?

Lösung:

Moderne Kryptographie-Verfahren funktionieren ganz ähnlich, aber es gibt ein zwei wesentliche Unterschiede:

1. Blockverschlüsselung: Statt einer XOR Operation wird bei der Verschlüsselung jedes Blocks eine kompliziertere Funktion verwendet. Das Ziel dabei ist, dass jeweils nicht nur ein einzelnes Bit des Schlüssels und des Klartexts kombiniert werden, sondern dass möglichst alle Bits miteinander vermischt werden. Ein einziger geänderter Buchstabe bewirkt, dass alle Stellen des Blocks verändert werden. In den Abbildungen steht statt XOR jeweils eine Box block cipher encryption (Blockverschlüsselung), die die kompliziertere Funktion enthält.

Wir haben aber trotzdem noch ein Problem: komplett gleiche Blöcke werden weiterhin gleich verschlüsselt. Wiederholt sich eine Klartext-Sequenz exakt mit der Blockgrösse, wird das Chiffrat ebenfalls an diesen Stellen gleich sein, was einem Angreifer auffallen dürfte. Zudem ist es für einen Angreifer nach wie vor möglich, verschlüsselte Blöcke einzufügen oder Blöcke zu löschen, ohne dass dies detektiert werden kann.

2. Verkettung: Aus diesem Grund werden die Blöcke nochmals miteinander verkettet (en. chaining): das Chiffrat des vorherigen Blocks wird mit dem Klartext des momentanen Blocks mit einer XOR-Operation verbunden. Dadurch ist jeder Block immer auch an den vorherigen Block gebunden, eine Änderung eines Buchstabens zu Beginn der Nachricht ändert auch alle folgenden Blöcke.

Der Ausdruck Block Chain ist auch aus der Welt der Cryptowährungen bekannt, die auf dem exakt gleichen Prinzip aufbauen: Ein neuer Block in der Block Chain basiert auf allen vorhergehenden Transaktionen der Währung.

Der Unterschied zwischen der Verschlüsselung ohne oder mit Chaining kann anhand eines verschlüsselten Bildes illustriert werden: Das zu verschlüsselnde Bild enthält viele weisse Pixel (= gleiche Blöcke). Bei entsprechender Blocklänge erscheinen die gleich verschlüsselten Blöcke immerzu im Ciphertext, und lassen übers ganze das Bild deutlich erscheinen. Im Gegensatz dazu enthält das Bild nur Rauschen, wenn es im Chaining-Modus verschlüsselt wurde (Quelle: Wikipedia: Electronic Code Book Mode):

Nimm den Full-Block-Coder aus der Lösung der Aufgabe 4 und baue die Verkettung ein. Modifiziere sowohl die Verschlüsselung und die Entschlüsselung. Als Zumischung für den ersten Block definierst du einen Initialization Vector (s. Abbildung).

Achtung: Bei der Verschlüsselung wird zu jedem Klartext-Block der letzte chiffrierte Block dazugemischt (mit XOR). Bei der Entschlüsselung muss entsprechend ebenfalls der vorherige chiffrierte Block vor dem Entschlüsseln beigemischt werden:

Lösung:

chaining_block_coder.py

def textToBytes(text):
    """Converts a string into a list of ASCII codes."""
    numbers = []
    for letter in text:
        number = ord(letter)
        numbers.append(number)
    return numbers
 
def bytesToText(numbers):
    """Converts a number list into text using ASCII decoding."""
    text = ""
    for number in numbers:
        letter = chr(number)
        text += letter
    return text
 
def binaryToBytes(binary):
    """Converts a sequence of binary strings into a list of numbers."""
    numbers = []
    for bin in binary:
        number = int(bin, 2)
        numbers.append(number)
    return numbers
 
def bytesToBinary(numbers):
    """Converts a number list into a space separated binary string."""
    text = ""
    for number in numbers:
        binary = format(number, "b")
        text += binary + " "
    return text
 
def parseWords(binaryText):
    """Splits a string with space-separated words into a list of words."""
    return binaryText.split()
 
def xor(block, key):
    """Computes XOR for a single block of numbers."""
    result = []
    for i in range(len(block)):
        result.append(block[i] ^ key[i])
    return result
 
def decryptBlock(block, key, previous_block):
    return xor(xor(block, key), previous_block)
 
def decrypt(ciphertext, passphrase):
    """Decrypts a sequence of binary text using a passphrase"""
    ciphernumbers = binaryToBytes(parseWords(ciphertext))
    key = textToBytes(passphrase)
    plaintext = []
    # Content does not matter - we'll discard the first block 
    previous_block = textToBytes("1234567890")
    # Split ciphertext into blocks of key length, then decrypt each block. 
    first = True
    for i in range(0, len(ciphernumbers), len(key)):
        cipherblock = ciphernumbers[i:i+len(key)]
        plainblock = decryptBlock(cipherblock, key, previous_block)
        if first:
            # Discard the first block.
            first = False
        else:
            plaintext += plainblock
        previous_block = cipherblock
    return bytesToText(plaintext)
 
def encryptBlock(block, key, previous_block):
    return xor(xor(block, previous_block), key)
 
def encrypt(plaintext, passphrase):
    """Encrypts plaintext as binary string output using passphrase."""
    key = textToBytes(passphrase)
    plaincodes = textToBytes(plaintext)
 
    # First block is random - decrypt will discard it.
    first_block = textToBytes("abcdefghij")
    # Initialization vector - in reality, we'd choose a random value.
    initialization_vector = textToBytes("9876543210")
    # Encrypt the random first block with the init vector - it will be 
    # discarded.
    ciphertext = encryptBlock(first_block, key, initialization_vector)
    previous_block = ciphertext
 
    # Split plaintext into blocks of key length, then encrypt each block. 
    for i in range(0, len(plaincodes), len(key)):
        plainblock = plaincodes[i:i+len(key)]
        cipherblock = encryptBlock(plainblock, key, previous_block)
        ciphertext += cipherblock
        previous_block = cipherblock
    return bytesToBinary(ciphertext)
 
key = "ROMANSHORN"
print(decrypt(encrypt("Das ist alles wirlich sehr, sehr geheim!", key), key))

Wende eine einfache Block-Verschlüsselung im ECB bzw. CBC-Modus an, und dokumentieren den Effekt in einem Dokument (OneNote, Word, Latex…).

Wie sieht das verschlüsselte Bild aus?
Was passiert mit anderen (längeren) Schlüsseln?
Warum ist ein Schlüssel nur aus Grossbuchstaben ungünstig?

Vorgehen

Du benötigst ein Bild, z.B. penguin.png.

Speichere den folgenden Code in VS Code. Der Code verwendet die OpenCV-Bibliothek zur Bildverarbeitung. Sie muss einmalig im Terminal mit python -m pip install opencv-python installiert werden.

Führe den Code aus - was zeigt das Bild?
Ändere den Code, um den Effekt von verschiedenen Schlüssellängen und von Chaining auf das Chiffrat auszuprobieren!
Dokumentiere die Resultate in OneNote / Word / Latex / Jupyter.

block_coder.py

import cv2 as cv
import numpy as np
import math
import random
 
def text_to_bytes(text):
    """Converts a string into a list of ASCII codes."""
    numbers = []
    for letter in text:
        number = ord(letter)
        numbers.append(number)
    return numbers
 
def bytes_to_text(numbers):
    """Converts a number list into text using ASCII decoding."""
    text = ""
    for number in numbers:
        letter = chr(number)
        text += letter
    return text
 
def binary_to_bytes(binstring):
    binstring *= 8  # ensure we are byte-aligned
    result = []
    for eight in range(0, len(binstring), 8):
        result.append(int(binstring[eight:eight+8], 2))
    return result
 
def xor(one, two):
    result = []
    for i in range(len(one)):
        result.append(one[i] ^ two[i])
    return result
 
def block_encrypt(one, two):
    # In reality, this would be a more complex operation, such as a sequence of
    # [s-boxes](https://de.wikipedia.org/wiki/S-Box).
    return xor(one, two)
 
def block_decrypt(one, two):
    # In reality, this would be the inverse of block_encrypt.
    return xor(two, one)
 
def encrypt(plain_bytes, key_bytes, chaining=True, block_size=8):
    # random initialization vector
    iv = random.randbytes(block_size)
 
    # ensure our key material is divisible by block_size
    key_bytes = key_bytes * block_size
 
    first_block = text_to_bytes('a'*block_size)
    cipher_bytes = block_encrypt(xor(first_block, iv), key_bytes[0:block_size])
    previous_block = cipher_bytes
 
    for i in range(0, len(plain_bytes), block_size):
        plain_block = plain_bytes[i:i+block_size]
        key_index = (i+block_size) % len(key_bytes)
        key_block = key_bytes[key_index:key_index+block_size]
        if chaining:
            plain_block = xor(plain_block, previous_block)
        cipher_block = block_encrypt(plain_block, key_block)
        cipher_bytes += cipher_block
        previous_block = cipher_block
 
    return cipher_bytes
 
def decrypt(cipher_bytes, key_bytes, chaining=True, block_size = 8):
    # ensure our key material is divisible by block_size
    key_bytes = key_bytes * block_size
 
    # the first block is thrown away
    previous_block = cipher_bytes[0:block_size]
    plain_bytes = []
 
    # The decrypted first block is ignored...
    for i in range(block_size, len(cipher_bytes), block_size):
        cipher_block = cipher_bytes[i:i+block_size]
        key_index = i % len(key_bytes)
        key_block = key_bytes[key_index:key_index+block_size]
        plain_block = block_decrypt(cipher_block, key_block)
        if chaining:
            plain_block = xor(plain_block, previous_block)
        plain_bytes += plain_block
        previous_block = cipher_block
    return plain_bytes
 
 
def bytes_to_image(img_bytes, shape):
    as_np = np.asarray(img_bytes, order='C', dtype="uint8")
    as_np = as_np.reshape(shape)
    return as_np
 
# Play with different keys:
#key = "11110000011001101100010000110101110010111001100100010110000111110001100101000101101110111111000000000011000000111110010111101010111110001110101010101000001111001010110110100111000000000011111111010001111100110111101001111010000001011101010000101111110101001100010101001011011101110101011001110100100001101110110011000110100100111100010011001100100111000000000011011110000100010010001110101100111101010100111100010001010100101100111101101011100110110000000000101000000010100111110010000011101000111001100000101011110000000100110011000001000101001000011101000100100100100010100111110011101011010101010110001011010001001010000111000100100010111001111100011100001000011001100011100110101101111001000110001001111010111111100001111111111111011101100101111100000101000101100101011111111110001010111000101010110011011010111111101111110100000100100101001000100101100111100010101011111111001001101000011001101111000111111110101100001100110110000101100000000010111110001011011010010010000111010010011001101010010100000011101111110100101001111110011010000101001111001111000000010101111001000101100110010111101111001000010110111101000110110101000101110001001011100111110010111001011111111010000010011000011101100110111001001000110001110110011011000011001010001111000101100100001010110011000001011100001011010011010001110101010001111000000111111101110011000010010000111010111000111000110"
key = "1111000001100110110001000011010111001011100110010001011000011111000110010100010110"
key_bytes = binary_to_bytes(key)
#key_bytes = text_to_bytes("rõménshÖRÑ")
key_bytes = text_to_bytes("ROMANSHORN")
 
# Change between ECB and CBC modes:
chaining = False  # False: ECB, True: CBC
 
img = cv.imread('penguin.png')
img_bytes = img.tobytes()
 
img_encrypted = encrypt(img_bytes, key_bytes, chaining=chaining)
 
# We drop the first block as it's only used as initialization vector.
cv.imshow("image", bytes_to_image(img_encrypted[8:], img.shape))
cv.waitKey()
 
# Test if decryption works
# img_decrypted = decrypt(img_encrypted, key_bytes, chaining=chaining)
# cv.imshow("image", bytes_to_image(img_decrypted, img.shape))
# cv.waitKey()

Symmetrische Verschlüsselung

Moderne Block-Ciphers

Herausforderung: Verkettung

Verkettung ausprobieren

Vorgehen