Block Chiffre und der Data Encryption Standard (DES)

Dozent:

Prof. Dr. Michael Eichberg

Version:

2024-05-09

Basierend auf:

Cryptography and Network Security - Principles and Practice, 8th Edition, William Stallings

Stromchiffre

• Verschlüsselt einen digitalen Datenstrom ein Bit oder ein Byte nach dem anderen.

  Beispiele: Autokeyed Vigenère-Chiffre und Vernam-Chiffre.

• Im Idealfall wird (würde) ein One-Time-Pad verwendet werden. Der Schlüsselstrom wäre genauso lang wie der Bitstrom des Klartextes.

  • Wenn der kryptografische Schlüsselstrom zufällig ist, kann diese Chiffre auf keine andere Weise als durch die Beschaffung des Schlüsselstroms geknackt werden.

  • Der Schlüsselstrom muss beiden Nutzern im Voraus über einen unabhängigen und sicheren Kanal zur Verfügung gestellt werden.

  • Dies führt zu unüberwindbaren logistischen Problemen, wenn der vorgesehene Datenverkehr sehr groß ist.

  Beispielimplementierung in Python

  def vernam(plaintext: bytes, key: bytes) -> bytes:
      return bytes([p ^ k for p, k in zip(plaintext, key)])

Stromchiffre

• Aus praktischen Gründen muss der Bitstromgenerator als algorithmisches Verfahren implementiert werden, damit der kryptografische Bitstrom von beiden Benutzern erzeugt werden kann.

  • Es muss rechnerisch praktisch unmöglich sein, zukünftige Teile des Bitstroms auf der Grundlage früherer Teile des Bitstroms vorherzusagen.

  • Die beiden Benutzer müssen nur den erzeugenden Schlüssel sicher miteinander teilen, damit jeder den Schlüsselstrom erzeugen kann.

Blockchiffre

• Ein Klartextblock wird als Ganzes behandelt und verwendet, um einen gleich langen Chiffretextblock zu erzeugen.

• In der Regel wird eine Blockgröße von 64 oder 128 Bit verwendet.

• Wie bei einer Stromchiffre teilen sich die beiden Benutzer einen symmetrischen Chiffrierschlüssel.

• Die meisten netzbasierten Anwendungen, die auf symmetrische Verschlüsselung setzen, verwenden Blockchiffren.

Stromchiffre vs. Blockchiffre

Allgemeine n-Bit-n-Bit-Blocksubstitution (n = 4)

Verschlüsselungs- und Entschlüsselungstabelle für eine Substitutions-Chiffre

Verschlüsselungstabelle

Entschlüsselungstabelle

Feistel-Chiffre

Feistel schlug die Verwendung einer Chiffre vor, bei der sich Substitutionen und Permutationen abwechseln.

Feistel-Chiffre - Hintergrund

• Hierbei handelt es sich um eine praktische Anwendung eines Vorschlags von Claude Shannon zur Entwicklung einer Chiffre, bei der sich Konfusions- und Diffusionsfunktionen abwechseln.

• Dieser Aufbau wird von vielen bedeutenden (Twofish, Blowfish, Serpent, Mars) - im Einsatz befindlichen - symmetrischen Blockchiffren verwendet.

Diffusion

• Die statistische Struktur des Klartextes wird in weitreichende Statistiken des Chiffretextes überführt, d. h. die statistische Beziehung zwischen Klartext und Chiffretext wird so komplex wie möglich.

• Dies wird dadurch erreicht, dass jede Klartextziffer den Wert vieler Chiffretextziffern beeinflusst.

  (Lawineneffekt)

• Die Diffusion kann z. B. durch Permutationen erreicht werden.

Konfusion

• Versucht, die Beziehung zwischen den Statistiken des Chiffriertextes und dem Wert des Chiffrierschlüssels so komplex wie möglich zu gestalten, d. h. eine einzige Änderung des Chiffrierschlüssels sollte viele Bits des Chiffriertextes beeinflussen.

• Selbst wenn der Angreifer die Statistik des Chiffretextes einigermaßen in den Griff bekommt, ist die Art und Weise, wie der Schlüssel verwendet wurde, um diesen Chiffretext zu erzeugen, so komplex, dass es schwierig ist, den Schlüssel abzuleiten.

• Die Verwirrung kann z. B. durch Substitutionen realisiert werden.

Feistel Chiffre - Beispiel

Feistel Chiffre - Eigenschaften

Data Encryption Standard (DES)

• Wurde 1977 vom National Bureau of Standards (heute NIST) als Federal Information Processing Standard 46 herausgegeben.

• War das am häufigsten verwendete Verschlüsselungsverfahren bis zur Einführung des Advanced Encryption Standard (AES) im Jahr 2001

• Der Algorithmus selbst wird als Data Encryption Algorithm (DEA) bezeichnet.

  Eigenschaften

  • Die Daten werden in 64-Bit-Blöcken mit einem 56-Bit-Schlüssel verschlüsselt.

  • Der Algorithmus wandelt die 64-Bit-Eingabe in einer Reihe von Schritten in eine 64-Bit-Ausgabe um.

  • Dieselben Schritte werden mit demselben Schlüssel verwendet, um die Verschlüsselung rückgängig zu machen.

DES - Design

DES Rundenfunktion (F)

Stärke von DES - Timing-Angriffe

• Ein Verfahren, bei dem Informationen über den Schlüssel oder den Klartext gewonnen werden, indem beobachtet wird, wie lange eine bestimmte Implementierung für die Entschlüsselung verschiedener Chiffretexte benötigt.

• Dabei wird die Tatsache ausgenutzt, dass ein Verschlüsselungs- oder Entschlüsselungsalgorithmus für verschiedene Eingaben oft leicht unterschiedliche Zeit benötigt.

• Bislang scheint es unwahrscheinlich, dass diese Technik jemals gegen DES oder leistungsfähigere symmetrische Chiffren wie Triple DES und AES erfolgreich sein wird.

Entwurfsprinzipien für Blockchiffre - Anzahl der Runden

• Je größer die Anzahl der Runden ist, desto schwieriger ist es, eine Kryptoanalyse durchzuführen.

• Im Allgemeinen sollte das Kriterium sein, dass die Anzahl der Runden so gewählt wird, dass bekannte kryptoanalytische Bemühungen mehr Aufwand erfordern als ein einfacher Brute-Force-Schlüsselsuchangriff.

• Hätte DES 15 oder weniger Runden, würde die differentielle Kryptoanalyse weniger Aufwand erfordern als eine Brute-Force-Schlüsselsuche.

Entwurfsprinzipien für Blockchiffre - Funktion F

• Das Herzstück einer Feistel-Blockchiffre ist die Funktion F.

• Je nichtlinearer F ist, desto schwieriger wird jede Art von Kryptoanalyse sein.

• Der Algorithmus sollte einen großen Lawineneffekt (Avalanche-Property) haben.

• Das Einhalten der SAC- und BIC-Kriterien scheint die Wirksamkeit der Verwirrungsfunktion zu stärken.

Entwurfsprinzipien für Blockchiffre - Schlüsselableitung

• Bei jeder Feistel-Blockchiffre wird der Hauptschlüssel verwendet, um einen Unterschlüssel für jede Runde zu erzeugen.

• Im Allgemeinen möchten wir die Unterschlüssel so wählen, dass die Schwierigkeit, einzelne Unterschlüssel abzuleiten, und die Schwierigkeit, den Hauptschlüssel wieder zurückzuerhalten, maximiert werden.

• Es wird vorgeschlagen, dass die Schlüsselableitungsfunktion für die Unterschlüssel (Key Schedule) zumindest das Strenge Lawinenkriterium und das Bit-Unabhängigkeitskriterium für Schlüssel/Ciphertext garantieren sollte.

Doppelte Verschlüsselung

Meet-in-the-Middle-Angriff

Dreifache Verschlüsselung

(Z. B. Triple-DES (3DES) mit drei Schlüsseln)

Triple-DES mit zwei Schlüsseln

Die offensichtliche Antwort auf den Meet-in-the-middle-Angriff ist die dreifache Verschlüsselung mit drei verschiedenen Schlüsseln.

• Dies erhöht die Kosten des Meet-in-the-Middle-Angriffs auf \(2^{112}\), was jenseits dessen liegt, was praktikabel ist.

• Das hat den Nachteil, dass eine Schlüssellänge von \(56\,bits \times 3 = 168\,bits\) erforderlich ist, was etwas unhandlich sein kann.

• Als Alternative schlug Tuchman eine dreifache Verschlüsselungsmethode vor, die nur zwei Schlüssel verwendet.

• 3DES mit zwei Schlüsseln war eine Alternative zu DES und wurde in die Schlüsselverwaltungsstandards ANSI X9.17 und ISO 8732 aufgenommen.

Triple-DES mit drei Schlüsseln

• Es wurden mehrere Angriffe gegen 3DES mit 2 Schlüsseln entwickelt, die jedoch (noch) nicht praktikabel sind.

• Viele Forscher sind inzwischen der Meinung, dass 3DES mit drei Schlüsseln die bevorzugte Alternative ist.

• 3DES mit drei Schlüsseln hat eine effektive Schlüssellänge von 168 Bit und ist definiert als:

  \begin{equation*} C=E(K_3,D(K_2,E(K_1, P))) \end{equation*}

• Rückwärtskompatibilität mit DES ist gegeben, wenn man \(K_3 = K_2\) oder \(K_1 = K_2\) einsetzt.