Hallo liebe Steemians,

heute geht es weiter mit der Kryptographie Reihe, und der Fortsetzung der symmetrischen Kryptographie
Wer die ersten Teile verpasst hat, kann diese hier nachlesen:

---

Teil 1: Einleitung & klassische Kryptographie
Teil 2: Modulare Arithmetik
Teil 3: Symmetrische Kryptographie #1

---

---

Blockchiffren

Defition 15: Blockchiffren

Eine Blockchiffre verschlüsselt Blöcke fester Länge, zb. 64 Bit. Der Klartext               
wird zerlegt und danach Block für Block verschlüsselt. Wenn der Klartext den 
letzten Block nicht vollständig ausfüllt, wird dieser aufgefüllt. (Padding)

Data Encryption Standard (DES)

Eigenschaften:
- Blocklänge: 64 Bit
- Schlüssellänge: 56 Bit ( + 8Bit Redundanz)
- interne Struktur ist eine Feistelchiffre
- 16 Verschlüsselungsrunden pro Block

Funktionen :

- IP( )     8x8 Matrix  
- IP⁻¹ ( ) 8x8 Matrix
- PC-1 ( )  7x8 Matrix
- E( )  6x8 Matrix
- P( )  4x8 Matrix
- S Boxen 16x4 Matrix

Anmerkung: All die oben genannten Funktionen sind vorhandene, festgelegte Matrizen.
Diese hier alle aufzuführen, würde den Rahmen mehr als nur sprengen :D
Wer Interesse hat, findet die Daten alle im Netz.

Beispiel

101110 -> S-Box ->  1011
    1. und letztes bit gibt die Zeile an : 10 => Zeile 2
    die bits dazwischen geben die spalte an: 0111 => Spalte 7
=> An Position 2/7 steht die 11(dec) 
          -

Definition 16: Feistelnetzwerk

    Das Feistelnetzwerk lässt sich mathematisch beschreiben: 
        Li = R(i-1) 
        Ri = L(i-1) XOR f(R(i-1), ki)
        f Funktion (siehe Bild)

Entschlüsselung von DES

Die Entschlüsselung von DES unterscheidet sich von der Verschlüsselung nur durch eine veränderte
Teilschlüsselberechnung (Schlüsselfahrplan). Anstatt des Linksshifts im Transform-Block wird ein
Rechtsshift verwendet.

Transforms ohne Rechtsshift:        1
Transforms mit Rechtsshift 1Bit:    2, 9, 16
Transforms mit Rechtsshift 2Bit:    3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15

Dadurch werden die Teilschlüssel in der Reihenfolge K16, K15, K14, ..., K1 gebildet.

Warum funktioniert das?

1. Die initiale Permutation IP wird durch die finale Permutation IP⁻¹ aufgehoben.
2. Das Feistel-Netzwerk ist invertierbar

Beweis:

Wir wissen von der Verschlüsselung, dass:
    L16 = R15
    R16 = L15 XOR f(R15,K16)
    
Und R16 steht auf der linken Seite, L16 steht rechts (Vertauschung)
Die Entschlüsselung beginnt mit K16 und  L0(=R16), R0(=L16=R15)
Die Invertiertung funktioniert , wenn L1=R15 und R1=L15 

L1 = R0 = R15
R1 = L0 XOR f(R0, K16) = R16 XOR f(R15, K16) = L15

Die Sicherheit von DES

• Differentielle Kryptoanalyse benötigt 2⁴⁷ Klartext-Chiffretext-Paare, um Schlüssel K zu finden.
• Lineare Kryptoanalyse benötigt 2⁴³ Klartext-Chiffretext-Paare, um Schlüssel K zu finden.
• Bruteforce-Angriff auf Schlüssel K(56Bit) benötigt mit Spezialhardware z.B.:
  Riviera S6LX150 (64 Cores) im Durchschnitt etwa einen Tag

=> DES gilt somit als gebrochen

3DES

Implementierung

c = DESK2(DesK1(m))                 2DES
c = DESk2(m XOR K1) XOR K3          DESX    
c = DESk3( DESk2 ( DESk1(m)))       3DES
c = DESk3( DES⁻¹k2( DESk1(m)))      3DES-EDE (Encryption-Decryption-Encryption)

Sicherheitsgewinn von mehrfache verschlüselung

2DES: c = DESk2( DESk1(m))

Meet-in-the-Middle Angriff:

1. Bruteforce (Aufwand: 2⁵⁶): c' = DESk1(m) und speichern Paare (c',k1) für alle k1
2. Bruteforce (Aufwand: 2⁵⁶): c' ? DES⁻¹k2(c) und vergleichen mit (c',k1) Paaren
Wenn Treffer, dann haben wir K1 & K2 gefunden. Der Aufwand ist 2⁵⁶ + 2⁵⁶ = 2⁵⁷ allerdings plus ein
Speicheraufwand von 2⁵⁶ * Blocklänge (64 Bit)

=> Die Sicherheit von 2DES mit 2 mal 56Bit Schlüsseln entspricht lediglich 57 Bit.

3DES-EDE:

Meet-in-the-Middle Angriff

1. Bruteforce (Aufwand: 2⁵⁶): c'=DESk1(m) und speichern Paare (c',k1) für alle k1
2. Bruteforce (Aufwand: 2¹¹²): c' ? DESk2( DES⁻¹k3(c)) und vergleiche mit allen (c',k1) Paaren
Wenn Treffer, dann haben wir K1, K2 & K3 gefunden. Der Aufwand ist 2⁵⁶ + 2¹¹² = 2¹¹² plus ein
Speicheraufwand von 2⁵⁶ * Blocklänge (64Bit)

Zusammenfassung: Die Sicherheit von 3DES-EDE mit einem 56 Bit-Schlüssel entspricht maximal 2¹¹² Bit

AES - Advanced Encryption Standard

AES wurde im Jahr 2000 als Nachfolger von DES veröffentlicht und hat folgende Eigenschaften:
Blocklänge: 128 Bit
Schlüssellänge: |k| = 128, 192, 256 Bit
in 32 Bit Words: L = |k|/32
Interne Struktur: Substitutions-Permutations-Netzwerk
Runden R = 10, 12, 14 angelehnt an die Schlüssellänge ( auch R = L+6)

Verschlüsselung (schematischer Überblick über den Rijndael-Algorithmus)

Bild

AES verwendet 2 konstante 2D-Byte-Arrays:
- S-Box 16 x 16 (SubstitutionBox): enthält Iversen in GF(2⁸)
- rCon 4x11 (Round Constant): erste Spalte = 2^(r-1) in GF(2⁸)

Defintion 17: KeyExpansion für 128 / 192 / 256 Bit

Folgende Schritte werden durchgeführt:
    1. Erzeuge eine Byte-Matrix W mit 4 Zeilen und 4(R+1) Spalten (=Wi)
    2. Trage Schlüssel k spaltenweise(!) ein
    3. Setze i auf erste freie Spalte Wi nach dem Schlüssel
        Bei 128 Bit Schlüssellänge: i=4
    4. Wiederhole Schritte solange, i<4*(R+1)
        a) tmp = W(i-1)
        b) Wenn i≡0 mod Li dann:
            + (1) rotiere tmp, (2) substituiere mit S-Box(SubBytes), 
              (3) XOR-verknüpfe das oberste Elemente der Spalte mit der Rundenkonstante rCon[i/L]
        c) Falls 256 BIt Schlüssel (L=8) & i≡4 mod L, dann:
            Substituiere tmp mit S-Box (SubBytes)
        d) Befülle neue Spalte Wi = W(i-L) XOR tmp 
        e) Inkrementiere i

Definition 18: SubBytes

Die Bytes eines Blocks(4x4) werden durch Werte aus der S-Box(16x16) ersetzt.
Das erste Nibbe des Bytes (0xab) ist die Zeile; a-> Zeile
Das zweite Nibbe des Bytes ergibt die Spalte;  b -> Spalte

Definition 19: ShiftRows

Zeilen eines Blocks werden byteweise nach links rotiert.
    Zeile 1: Keine Rotation
    Zeile 2: Rotation um 1 Byte
    Zeile 3: Rotation um 2 Bytes
    Zeile 4: Rotation um 3 Bytes

Definition 20: MixColumns

Ersetze jede Spalte Wi des Blocks durch das Produkt mit der folgenden Matrix im Rijndaal-Galois-Feld GF(2⁸) unter 
Verwendung des Polynoms: x⁸+x⁴+x³+x+1 (0x11b)

2   3   1   1   
1   2   3   1
1   1   2   3
3   1   1   2

Beispiel MixColumns

2   3   1   1   *   a1  = [2*a1 XOR 3*a2 XOR 1*a3 XOR 1*a4]
1   2   3   1   *   a2  = [1*a1 XOR 2*a2 XOR 3*a3 XOR 1*a4]
1   1   2   3   *   a3  = [1*a1 XOR 1*a2 XOR 2*a3 XOR 3*a4]
3   1   1   2   *   a4  = [3*a1 XOR 1*a2 XOR 1*a3 XOR 2*a4]

Definition 21: AddRoundKey

Block wird mit Rundenschlüssel(W(4r), W(4r+1), ...) der Runde r mit XOR verknüpft

Entschlüsselung von AES

Alle Schritte der Verschlüsselung werden in umgekehrter Reihenfolge angewendet.
Notwendig ist eine invertierte S-Box so wie die Umkehr von ShiftRows & MixColumns.

Multiplikation mit inverser MixColumn Matrix:
12 11 13 9
9 14 11 13
13 9 11 11
11 13 9 14

Die KeyExpansion läuft identisch, nur werden die Rundenschlüssel in umgekehrter Reihenfolge verwendet.

Die Sicherheit von AES

Die stärksten Angriffe (Biclique) ohne Vorraussetzung benötigen 2¹²⁶(128Bit), 2¹⁸⁹(192 Bit)
Der Angriff mit verwandten Schlüsseln benötigt 2¹⁷⁶ Schritte für 192 Bit, bzw 2⁹⁹ für 256Bit

Betriebsmodi von Blockchiffren (Operation Modes)

Definition 22: Electronic Codebook Mode (ECB)

Jeder Block wird unabhängig voneinander verschlüsselt:
Verschlüsselung eines Blocks mi für alle i>=0, ci=enck(mi)

Eigenschaften

• Die Verschlüsselung eines Blocks führt immer zum gleichen Chiffrat

Beispiel: Angriff auf ECB

Fremde Überweisung: 500.000 € von Edith an Christian
                    0x1111 | 0x2222 | 0x3333
Ihre Überweisung 1: 3,50 € an Tante Emma
                    0x1337 | 0x082A | 0xCAFE 
Ihre Überweisung 2: 3,50 € an Onkel Gerd 
                    0x1337 | 0x987 | 0xCAFE
Angriff:            500.000€ von Christian an mich
Neue Transaktion:   0x2222 | 0x1337 | 0x3333

Definition 23: Cipher Block Chaining Mode (CBC)

Verknüpfung des Klartextblocks mit vorherigem Chiffreblock, dann Verschlüsselung

Funktionen

Verschlüsselung

c0 = enck(m0 XOR IV)
ci = enck(ni XOR ci-1)) 

Entschlüsselung

m0 = deck(c0) XOR IV
mi = deck(ci) XOR ci-1

Eigenschaften
Spezielle Fehlerfortpflanzung ^ = EinBitFehler ~ = MehrbitFehler
- 1 Bit Fehler : ^c0
~m0 = deck(c0) XOR IV Ändert sich ein Bit wird nach dem enc/dec der ganze Block anders
^m1 = deck(c1) XOR c0
m2 = deck(c2) XOR c1

Bei diesem Fehler wird der erste Block komplett zerstört, der zweite Block hat ein gekipptes Bit,
und ab dem dritten ist die Verschlüsselung wieder korrekt.

Definition 24: Cipher Feedback Mode (CFB)

        Verknüpfung des Klartextblocks mit mit Verschlüsselung des letzten Chiffreblocks.
        Der CFB Modus erzeugt eine Stromchiffre aus einer Blockchiffre.

Definition 25: Counter Mode (CTR)

Verknüpfung des Klartextblocks mit Verschlüsselung eines Counters.
Initial besteht der Counter oft aus einem bekannten Zufallswert, der für jede Operation 
inkrementiert wird.
Der Counter Modus erzeugt ebenfalls eine Stromchiffre.

---

Vielen Dank für eure Aufmerksamkeit!
Wenn es euch gefallen hat, lasst mir gerne ein Upvote da und natürlich gerne auch Feedback :)

---