Kryptografische Primitiven

Shownotes

Rückblick zu STP041
- Kryptografische Systeme dienen dem Erreichen der vier Schutzziele (Vertraulichkeit, Integrität, Authentizität, Verbindlichkeit)
- Implementierung vollständiger Kryptosysteme braucht Primitiven (Grundbausteine)
- heute: Vorstellung grundlegender Klassen von Primitiven
Symmetrische Verschlüsselung
- Schritt 1: Klartext (Plaintext) + Schlüssel (Key) -> Geheimtext (Ciphertext)
- Schritt 2: Geheimtext + selber Schlüssel -> Klartext
- üblicherweise als Blockchiffre mit Beschränkung des Klartexts auf eine Blockgröße von z.B. 128 oder 256 Bits, übliche Schlüsselgrößen ähnlich groß
- zwei Probleme:
  1. Wie verschlüsselt man mehr als einen Block?
  2. Wie einigt man sich auf einen gemeinsamen Schlüssel, ohne dass Beobachter den Schlüssel abgreifen können?
zu Problem 1: Erweiterung der Blockchiffre zu einem Stromchiffre mittels eines geeigneten Betriebsmodus
- Datenstrom wird in einzelne Blöcke der gewünschten Größe zerteilt; Betriebsmodus beschreibt dann die Anwendung des Blockchiffre auf die Folge von Blöcken
- einfachster Betriebsmodus ist ECB (Electronic Codebook): der Blockchiffre wird auf jeden Block komplett separat angewendet -> offensichtliche Probleme (siehe Bild im verlinkten Abschnitt)
- bei den meisten modernen Betriebsmodi werden meist Daten aus dem aktuellen Blockchiffre in den nächsten Block übertragen, um die Analyse des Geheimtextes zu erschweren -> Problem: schwer parallelisierbar, Lesezugriff nur sequentiell
- CTR-Betriebsmodus (Counter): jeder Block wird beim Verschlüsseln mit einem Zähler kombiniert, damit sich keine wiederkehrenden Muster wie bei ECB ergeben -> Vorteil: wahlfreier Schreib- und Lesezugriff möglich (interessant für Festplattenverschlüsselung)
- siehe unten: Beispiel für die Geschwindigkeit moderner Stromchiffern insb. mit Hardwareunterstützung

$ cryptsetup benchmark
...
#     Algorithm |       Key |      Encryption |      Decryption
...
        aes-xts        512b      3547,4 MiB/s      3540,4 MiB/s
    serpent-xts        512b       742,7 MiB/s       729,4 MiB/s
    twofish-xts        512b       398,9 MiB/s       404,8 MiB/s

zu Problem 2 (Einigung auf einen gemeinsamen Schlüssel) zwei Ansätze:
1. Schlüsselaustausch-Protokolle wie Diffie-Hellman
2. asymmetrische Verschlüsselung
Asymmetrische Verschlüsselung
- statt einem einzelnen Schlüssel ein Schlüsselpaar
  - wir haben keine gute Bildmetapher dazu; Xyrills Vorschlag: zwei Ratschen; eine dreht nur nach rechts und eine nur nach links
- Schritt 1: Klartext + öffentlicher Schlüssel -> Geheimtext
- Schritt 2: Geheimtext + privater Schlüssel -> Klartext
- Beispiel RSA:
  - Grundgeheimnis sind zwei sehr große Primzahlen (p und q, jeweils z.B. 500 Dezimalstellen)
  - aus dem Produkt dieser Primzahlen (N = p * q) werden zwei weitere Zahlen (d und e) mittels günstiger Rechenoperationen abgeleitet
  - dann ist der öffentliche Schlüssel das Zahlenpaar d,N und der private Schlüssel das Zahlenpaar e,N
  - Ableitung des privaten aus dem öffentlichen Schlüssel erfordert Primzahlfaktorisierung von N, was extrem teuer ist (siehe Beispiel unten)
- Problem 1 teilweise gelöst: Empfänger muss nur seinen öffentlichen Schlüssel offenbaren, der kein Geheimnis enthält
- Problem 2 ungelöst: auch asymmetrische Verschlüsselung arbeitet nur pro Block

$ time factor 1350918345091284620469824069824602946802496824562049682046982406982406980
1350918345091284620469824069824602946802496824562049682046982406982406980: 2 2 3 5 7 193 941 5077 3488395463852632669275489205712092360621005476304268749586169
factor   1,92s user 0,00s system 99% cpu 1,926 total
$ time factor 1350918345091284620469824069824602946802496824562049682046982406982406981
1350918345091284620469824069824602946802496824562049682046982406982406981: 11 3931 5242879872157046321 5958863859256362497309559371496021100634736129421
factor   462,19s user 0,01s system 99% cpu 7:43,24 total

neues Problem: asymmetrische Verfahren sind sehr viel rechenaufwändiger als symmetrische Verfahren -> hybrides Kryptosystem
- asymmetrische Verschlüsselung wird nur zum Austausch eines symmetrischen Schlüssels verwendet
- Beispiel "verschlüsselte E-Mail": Alice hat den öffentlichen Schlüssel O, Bob hat den privaten Schlüssel P dazu
  - Alice erstellt die Nachricht N im Klartext
  - Alice erzeugt einen zufälligen symmetrischen Schlüssel S
  - Alice verschlüsselt N mit S und einem Stromchiffre zu N'
  - Alice verschlüsselt S mit O zu S'
  - Alice schickt N' und S' an Bob
  - Bob entschlüsselt S' mit P zu S
  - Bob entschlüsselt N' mit S zu N
zweite Anwendung von asymmetrischer Kryptografie: Signaturen
- Verschlüsselung: vorwärts mit dem öffentlichen Schlüssel, rückwärts mit dem privaten Schlüssel
- bei Signierung umgekehrt: vorwärts mit dem privaten Schlüssel (Erzeugung), rückwärts mit dem öffentlichen Schlüssel (Überprüfung)
- im Detail: erst Komprimierung der zu signierenden Daten auf eine feste Größe mittels einer Hashfunktion (siehe STP004), dann Verschlüsselung dieses Hash-Wertes mit dem privaten Schlüssel
- Überprüfung: Berechnung des Hashes auf dieselbe Weise, Vergleich mit entschlüsselter Signatur
noch eine Primitive zum Schluss: Geheimnisteilung
- Problem: Ein Geheimnis soll in N Teile so aufgeteilt werden, dass M beliebige Teile zum Entschlüsseln genutzt werden können.
- Beispiel: Backup des Passwortspeichers in 5 Fragmente aufteilen und bei 5 Freunden so einlagern, dass man später nur 3 beliebige Fragmente zum Wiederherstellen braucht
- Illustrationen: Visuelle Kryptografie, Blakley-Schema
im Gespräch erwähnt
- Anerzählt Podcast zu AES
- Whitfield Diffie und Moxie Marlinspike und eine Flasche Whiskey auf der Bühne

Schlüsseltechnologie #43 vom 7. September 2023

Download

Shownotes

Audioquellen in Abspielreihenfolge (soweit nicht gemeinfrei)