Symmetrische Kryptografie: Data Encryption Standard (DES)

Rückblick und Themen

• Rückblick:
  • Einordnung Kryptografie
  • Modulare Arithmetik
  • Substitutionschiffre
  • Stromchiffren
• Themen heute:
  • Data Encryption Standard (DES)
    • Verschlüsselung
    • Schlüsselfahrplan
    • Entschlüsselung

Blockchiffren Data Encryption Standard (DES)

• Referenz: https://csrc.nist.gov/csrc/media/publications/fips/46/3/archive/1999-10-25/documents/fips46-3.pdf

Historie von DES

• 1972: Ausschreibung des NBS (heute NIST, National Institute of Standards and Technology)
• 1974: NBS erhält vielversprechendsten Vorschlag von IBM
  • Algorithmus basiert auf einer Feistel Chiffre
  • Verschlüsselt Blöcke von 64 Bit mit einem 128 Bit Schlüssel
• Gerüchte:
  • NBS fragt nach Hilfe bei der NSA an
  • Vermutung: NSA nimmt Einfluss auf die Chiffre, insbesondere Reduktion der Schlüssellänge auf 56 Bit (Brute-Force Angriffsmöglichkeit)
  • Verdacht einer absichtlichen Hintertür in den S-Boxen hat sich nicht bestätigt
• 1977: Veröffentlichung der Chiffre als Data Encryption Standard (DES)

Konfusion und Diffusion nach Claude Shannon

• Konfusion:
  • Operation zur Verschleierung der Beziehung zwischen Schlüssel und Chiffrat
  • Beispiel: Substitutionstabellen
• Diffusion:
  • Operation zur Streuung des Einflusses eines Klartextsymbols auf zahlreiche Chiffratsymbole
  • Beispiel: Bitpermutationen

Heutige Blockchiffren

• Nutzen das Hintereinanderschalten von Konfusion und Diffusion in wiederholenden Runden.

Schlüssel- und Blocklänge bei DES

• 64-Bit Blöcke und 56-Bit Schlüssel
• 16 Runden zur Verschlüsselung eines Klartextblocks
• In jeder Runde wird ein Rundenschlüssel k_i vom Hauptschlüssel k abgeleitet.

Feistel-Struktur in DES – Runde 1

• Klartext x
• Eingangspermutation IP(x)
• L0, R0
• f
• L1, R1
• Schlüssel k
• PC-1
• k_1

Feistel-Struktur in DES – Runde 2-16

• L1, R1
• f
• L2, R2
• k_2
• …
• L{16}, R{16}

Feistel-Struktur in DES – Nach Runde 16

• L{16}, R{16}
• Ausgangspermutation IP^{-1}
• Chiffrat y = DES_k(x)

Eingangs- und Ausgangspermutation

• Eine vordefinierte Tabelle gibt an, wie der 64-Bit Block permutiert wird.
• Die Ausgangspermutation ist die inverse Operation der Eingangspermutation;
  • Es gilt also IP^{-1}(IP(x)) = x
• Beispiel für Eingangspermutation für Bit 1 und Bit 50
• Vollständige Tabelle für Eingangs- und Ausgangspermutation auf Seite 10 des DES NIST Standards (https://csrc.nist.gov/csrc/media/publications/fips/46/3/archive/1999-10-25/documents/fips46-3.pdf) oder auf Wikipedia (https://en.wikipedia.org/wiki/DESsupplementarymaterial#Initialpermutation(IP))

Interna der Feistel-Struktur

• 64-Bit Klartext wird in 2 Hälften aufgeteilt: L0, R0
• Die rechte Seite wird als linke Seite für die nächste Runde verwendet: Li = R{i-1}
• Die rechte Seite ist das Ergebnis der f-Funktion und einer XOR-Verknüpfung: Ri = L{i-1} \oplus f(R{i-1}, ki)
• Beachte:
  • Es wird in jeder Runde nur eine Hälfte verschlüsselt; wesentliche Eigenschaft der Feistel-Struktur
  • Konfusion und Diffusion geschehen innerhalb der f-Funktion

Die f-Funktion

• R_{i-1}
• Expansion E(R_{i-1})
• S1, S2, S3, S4, S5, S6, S7, S8
• Permutation P()
• k_i

Expansion und XOR-Verknüpfung

• Expansion
  • 32 Eingangsbits werden auf 48 Bits Ausgangsbits erweitert
  • Expansion geschieht in der sogenannten E-Box, welche jeweils 4 Bits auf 6 Bits erweitert
  • Die Expansion erhöht die Diffusionseigenschaft von DES
• XOR-Verknüpfung
  • Nach der Expansion wird der Rundenschlüssel k_i mit dem Ergebnis der Expansion XOR verknüpft

Expansionstabelle

• Bildquelle: https://en.wikipedia.org/wiki/DESsupplementarymaterial#/media/File:DES-ee.svg

Substitutionsboxen (S-Boxen)

• Referenz: https://csrc.nist.gov/csrc/media/publications/fips/46/3/archive/1999-10-25/documents/fips46-3.pdf Seite 17
• Der 48-Bit Block wird in 6-Bit Blöcke aufgeteilt
• Die 6-Bit Blöcke durchlaufen verschiedene Substitutionsboxen (S-Boxen)
• Jede S-Box (S1 … S8) beinhaltet 64 Einträge und erwartet einen 6-Bit Eingang und produziert einen 4-Bit Ausgang
• Höchst- und Niedrigwerteste Bit bestimmen die Reihe; die vier inneren Bits die Spalte

Wichtigkeit der S-Boxen

• DES NIST Standards
• S-Boxen sind der kryptografische Kern von DES
• Sie erzeugen Konfusion aufgrund einer nicht-linearen Abbildung, d.h.:
  • S(a) \oplus S(b) \neq S(a \oplus b)
• Es gibt verschiedene Kriterien die eine S-Box erfüllen muss, um als sicher zu gelten
• Diese Kriterien betreffen größtenteils Regeln für das Abbilden von Eingangs- zu Ausgangsbits
• Alle S-Boxen einsehbar auf Seite 17 des DES NIST Standards

Permutation in der f-Funktion

• Führt ebenfalls Diffusion ein, da die 4 Ausgangsbits der S-Boxen jeweils mehrere S-Boxen in der nächsten Runde beeinflussen
• Durch die Diffusion der E-Box, S-Boxen, und Permutation ist garantiert, dass jedes Bit am Ende der 5. Runde eine Funktion von jedem Bit des Klartextes und des Schlüssels ist; der sogenannte Avalanche-Effekt

DES Schlüsselfahrplan

• Permutated Choice 1
  • Ignoriert jedes 8. Bit; das 8. Bit wurde als ungerades Paritätsbit verwendet
  • Es wird ebenfalls gemäß vorgegebener Tabelle (s. PC-1 auf Seite 19 DES NIST Standard) permutiert
  • Der 56-Bit Block wird in 2 Teile aufgeteilt
• Left Shift
  • LS1 … LS{16} verschieben um 1 oder 2 Bits:
    • 1 Bit in Runde 1, 2, 9, 16
    • 2 Bits in allen anderen Runden
  • Left shift ist etwas irreführend; tatsächlich ein left rotate
  • Left shift findet getrennt in Ci und Di statt
• C0 = C{16} und D0 = D{16}
  • Wichtig für Entschlüsselung
• Permutated Choice 2
  • Erzeugt den 48-Bit Rundenschlüssel
  • Es wird ebenfalls gemäß vorgegebener Tabelle (s. PC-2 auf Seite 21 DES NIST Standard) permutiert

Prinzip der DES Entschlüsselung

• Im umgekehrten Schlüsselfahrplan wird rechts rotiert (statt links)
• Im Wesentlichen dieselbe Operation wie die Verschlüsselung aufgrund der Feistel-Struktur:
  1. Mittels IP wird die Ausgangspermutation rückgängig gemacht
  2. Die 1. Runde der Entschlüsselung ist die inverse Operation der 16. Runde der Verschlüsselung
  3. Die 2. Runde der Entschlüsselung ist die inverse Operation der 15. Runde der Verschlüsselung
  4. …
  5. Die 16. Runde der Entschlüsselung ist die inverse Operation der 1. Runde der Verschlüsselung

Diskussion (Entschlüsselung)

• Transformation 16
• L{16}, R{16}
• Ausgangspermutation IP^{-1}
• Chiffrat y = DES_k(x)
• L{15}, R{15}
• f
• k_{16}

Abschließende Bemerkungen zu DES

• Mathematische Schwachstellen wurden nicht gefunden, insb. die S-Boxen sind sicher und robust gewählt worden
• Brute-Force-Angriff ist aber aus heutiger Sicht und mit heutiger Hardware relativ leicht (in Stunden) durchführbar
• Der Schlüssel in DES ist zu kurz
• Triple-DES (112 Bit effektiver Schlüssellänge) erschwert Brute-Force
  • 3 aufeinanderfolgenden DES-Operationen (Encrypt-Decrypt-Encrypt)
  • DES wird deswegen heute immer noch eingesetzt (EC Karte oder Digitaler Ausweis)
• Probleme
  • DES ist in Software nicht effizient und Triple-DES dreimal langsamer als DES
  • Kleine Blockgröße von nur 64-Bit
  • Nicht sicher gegen Quantencomputer aufgrund der Schlüssellänge von maximal 168 Bit (in Triple-DES)