Einstieg
Ein Bit Unterschied
Zwei Nachrichten, derselbe AES-128-Schlüssel 2b7e1516 28aed2a6 abf71588 09cf4f3c
| Klartext | Byte 12 binär |
|---|---|
| Treffen um 17:00 | 0011 0111 |
| Treffen um 16:00 | 0011 0110 |
Die beiden Klartexte unterscheiden sich in genau 1 von 128 Bit. Beide werden mit AES verschlüsselt.
Geheimtext 1: ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
Geheimtext 2: ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
Jedes Kästchen ist ein Bit des Geheimtexts, dunkel = verschieden.
Wie viele der 128 Bit im Geheimtext unterscheiden sich?
Hier sind es … von 128 Bit. Im Mittel kippt jedes Bit mit Wahrscheinlichkeit ½, wie bei einem Münzwurf; meist sind es 55 bis 73. Alle 128 wären auch ein Muster: Der Geheimtext wäre nur invertiert.
Bei Cäsar oder Vigenère ändert ein anderer Buchstabe nur einen Buchstaben. Wie baut man eine umkehrbare Rechnung, in der ein Bit am Ende alles beeinflusst?
Station 1 · Bauplan
Was den alten Verfahren fehlt
Auftrag: Vergleicht die drei Verfahren aus der Reihe. Welche Eigenschaft fehlt allen dreien?
| Verfahren | Ein Klartextzeichen ändern … | Häufigkeiten im Geheimtext |
|---|---|---|
| Cäsar | ändert genau 1 Geheimtextzeichen | bleiben erhalten, nur verschoben |
| Vigenère | ändert genau 1 Geheimtextzeichen | verwischt, aber je Spalte wie Cäsar |
| Skytale | ändert genau 1 Zeichen, nur an anderem Ort | bleiben exakt erhalten |
Konfusion
Der Zusammenhang zwischen Schlüssel und Geheimtext ist so verwickelt, dass man ihn nicht zurückrechnen kann. Werkzeug: ersetzen, nichtlinear.
Diffusion
Jedes Klartextbit wirkt auf viele Geheimtextbits. Statistische Muster verteilen sich. Werkzeug: umstellen und mischen.
Begriffe nach Claude E. Shannon, „Communication Theory of Secrecy Systems“, 1949.
Was fehlt allen drei Verfahren?
Keines verteilt eine Änderung. Darum funktionieren Häufigkeitsanalyse und Wortraten. Geheim muss nach Kerckhoffs nur der Schlüssel sein.
Bauplan von AES: eine Runde = ersetzen + umstellen + mischen + Schlüssel. Die Runde wird oft wiederholt (Substitutions-Permutations-Netz).
Station 2 · Block und Zustand
128 Bit als 4 × 4-Tabelle
Auftrag: Sagt voraus, in welcher Zelle das 7. Zeichen landet. Dann tippt die Zelle an und prüft.
Tippt eine Zelle an.
Das 7. Zeichen (Byte 6) landet in … (Zeilen und Spalten ab 0)
AES füllt die Tabelle spaltenweise: Byte k steht in Zeile k mod 4, Spalte ⌊k/4⌋.
| Blocklänge | immer 128 Bit = 16 Byte |
|---|---|
| Schlüssel | 128 / 192 / 256 Bit → 10 / 12 / 14 Runden |
| Längere Texte | in Blöcke teilen, Betriebsart nötig (Station 10) |
Station 3 · Überblick
Der Rundenplan von AES-128
Auftrag: Lest den Plan von oben nach unten. Begründet, warum in der letzten Runde MixColumns fehlt.
Warum fehlt MixColumns in Runde 10?
MC(s) ⊕ K = MC(s ⊕ MC−1(K)): Ein letztes MixColumns wäre nur eine öffentliche Umrechnung des Geheimtexts.
Darum steht auch AddRoundKey am Anfang: Sonst könnte jeder die ersten Schritte ohne Schlüssel nachrechnen.
Station 4 · Werkzeug
Rechnen mit Bytes: der Körper GF(28)
Auftrag: Rechnet {57} · {13} zuerst selbst mit der xtime-Regel. Dann deckt die Rechnung auf.
Ein Byte ist ein Polynom mit Koeffizienten 0 oder 1:
{57} = 0101 0111 = x6 + x4 + x2 + x + 1
Addition = Koeffizienten mod 2 addieren = XOR. Plus und Minus sind dasselbe.
{57} ⊕ {83} = 0101 0111 ⊕ 1000 0011 = 1101 0100 = {D4}
Multiplikation = Polynome multiplizieren und den Rest bei Division durch
m(x) = x8 + x4 + x3 + x + 1 = {11B}
nehmen. Mal x (xtime): Bits eins nach links schieben. Fällt eine 1 links heraus, mit {1B} XOR-verknüpfen.
Weil m(x) irreduzibel ist, hat jedes Byte außer {00} ein Inverses: {53} · {CA} = {01}. Das braucht die S-Box auf der nächsten Station.
| i | a · xi | Bit i von b | Summe |
|---|
Station 5 · SubBytes
Die S-Box: Konfusion in einer Tabelle
Auftrag: Sucht ein Byte, das die S-Box auf sich selbst abbildet. Prüft dann, ob S(a ⊕ b) = S(a) ⊕ S(b) gilt.
Zeile = erste Hex-Ziffer, Spalte = zweite. Tippt eine Zelle an.
Jeder Eintrag: Inverses in GF(28), dann affine Abbildung der Bits:
b′i = bi ⊕ bi+4 ⊕ bi+5 ⊕ bi+6 ⊕ bi+7 ⊕ ci, Indizes mod 8, c = {63}
Linear? a = …, b = …
S(a ⊕ b) = … S(a) ⊕ S(b) = …
Station 6 · ShiftRows MixColumns
Verschieben und mischen: Diffusion
Auftrag: Ändert ein einziges Byte der Spalte. Wie viele Bytes ändern sich nach MixColumns? Erst vermuten, dann tippen.
ShiftRows: Zeile r rückt r Plätze nach links
Jede Spalte enthält noch Bytes aus nur einer Spalte (A, B, C oder D).
MixColumns: jede Spalte mal eine feste Matrix
Tippt ein Byte der Eingabe an, es wird um 1 erhöht.
Eingabe- und Ausgabebytes, die sich ändern, sind zusammen immer mindestens 5 (Verzweigungszahl 5). Nach ShiftRows stammen die vier Bytes einer Spalte aus vier Spalten. Darum hängt nach zwei Runden jedes Byte von jedem ab.
Station 7 · AddRoundKey
Aus 1 Schlüssel werden 11 Rundenschlüssel
Auftrag: Rechnet w4 für den Beispielschlüssel nach. Wozu dient Rcon?
Der Schlüssel liefert die Wörter w0 … w3 (je 4 Byte). Jedes weitere Wort ist
wi = wi−4 ⊕ t, t = wi−1 oder, wenn i durch 4 teilbar ist, t = SubWord(RotWord(wi−1)) ⊕ Rcon
Rcon = xj−1 in GF(28) für j = i/4: 01, 02, 04, …, 80, 1B, 36. Ohne Rcon ergäbe ein Schlüssel aus lauter gleichen Bytes nur Rundenschlüssel aus lauter gleichen Bytes; Rcon bricht solche Symmetrien.
Rundenschlüssel K0 … K10
Schlüssel 2b7e1516 28aed2a6 abf71588 09cf4f3c (FIPS 197, Anhang A.1)
AddRoundKey verknüpft den Zustand Byte für Byte per XOR mit Kr. Zweimal angewendet hebt es sich auf.
Station 8 · Simulation
AES-128 Schritt für Schritt
Auftrag: Vermutet vor jedem Klick, welche Bytes sich ändern. Vergleicht das Ergebnis mit FIPS 197, Anhang B.
Rundenschlüssel
Alle 41 Schritte, antippen zum Springen. Buchstaben: S SubBytes, R ShiftRows, M MixColumns, K AddRoundKey.
Station 9 · Zurück zum Einstieg
Wie schnell breitet sich ein Bit aus?
Auftrag: Schätzt erst, dann auflösen. Wählt danach selbst ein Bit im Klartext oder im Schlüssel.
Ein Klartextbit kippt. Nach welcher Runde unterscheiden sich alle 16 Bytes des Zustands?
Runde 1: Das geänderte Byte geht durch SubBytes, ShiftRows verschiebt es, MixColumns verteilt es auf 4 Bytes. Runde 2: ShiftRows schickt diese 4 Bytes in 4 verschiedene Spalten, MixColumns macht daraus 16. Die übrigen Runden sind Sicherheitsreserve gegen raffiniertere Angriffe.
Byte wählen (0–15), dann Bit (7 = höchstes):
Klartext „Treffen um 17:00“, Schlüssel wie im FIPS-Beispiel.
Unterschied nach jeder Runde: Kästchen = Byte verschieden, Balken und Zahl = verschiedene Bits von 128.
Station 10 · Lange Nachrichten
Ein Bild, Block für Block verschlüsselt
Auftrag: Erklärt, warum man im ECB-Bild den Leuchtturm noch erkennt, obwohl jeder Block mit AES verschlüsselt ist.
1 Byte je Pixel
jeder Block einzeln
Blöcke verkettet
ECB (Electronic Codebook): jeder Block einzeln. Gleiche Klartextblöcke ergeben gleiche Geheimtextblöcke.
Ci = AESK(Pi)
CBC (Cipher Block Chaining): vorher mit dem vorigen Geheimtextblock XOR-verknüpfen, am Anfang mit einem zufälligen IV.
Ci = AESK(Pi ⊕ Ci−1), C0 = IV
CTR (Counter): einen Zähler verschlüsseln und das Ergebnis als Schlüsselstrom per XOR auf die Daten legen. Ähnlich wie beim One-Time-Pad, aber der Strom ist berechnet, nicht zufällig.
Ci = Pi ⊕ AESK(Nonce ‖ i)
Station 11 · Angriff ohne Schlüssel
Geheim heißt nicht unverfälscht
Auftrag: Eve kennt den Schlüssel nicht, aber das Format der Überweisung. Vermutet, dann lasst Eve angreifen.
Alice → Bank, verschlüsselt mit AES-128 im CTR-Modus
Geheimtext, den Eve abfängt (Hex):
Eve weiß: Byte 16 ist die Tausenderstelle, bei Beträgen unter 1000 steht dort „0“. Sie verknüpft das Byte mit „0“ ⊕ „neue Ziffer“:
Die Bank entschlüsselt mit dem richtigen Schlüssel:
Kann Eve den Betrag gezielt ändern?
Bei CTR kippt ein Bit im Geheimtext genau dasselbe Bit im Klartext. AES selbst bleibt ungebrochen, die Bank merkt nichts.
Abhilfe: authentifizierte Verschlüsselung wie AES-GCM. Ein Prüfwert (Tag) verrät jede Änderung. TLS 1.3 erlaubt nur solche Verfahren.
Station 12 · Einordnen
Wie sicher ist AES heute?
Auftrag: Rechnet den Aufwand für das Durchprobieren. Ordnet dann ein: Welcher Angriff ist praktisch am gefährlichsten?
Alle 2128 ≈ 3,4 · 1038 Schlüssel durchprobieren
Mathematisch
Bester bekannter Angriff auf volles AES-128 (Biclique, 2011): 2126,1 statt 2128 Schritte, nur rund 3,7-mal schneller.
Seitenkanal
Angriff auf die Umsetzung, nicht auf die Mathematik: Laufzeit, Cache, Stromverbrauch. Bernstein zeigte 2005, wie Zeitmessungen an einem Server den Schlüssel verraten.
Quantencomputer
Grovers Algorithmus durchsucht N Schlüssel in rund √N Schritten, etwa 264 für AES-128, die sich aber schlecht aufteilen lassen. NIST plant keinen Umstieg weg von AES.
Was ist heute praktisch am gefährlichsten?
Gegen die Mathematik von AES gibt es keinen praktischen Angriff. Gebrochen werden Umsetzungen und Anwendungen: Seitenkanäle, ECB, fehlende Prüfwerte, schwache Passwörter.
Abschluss
Check
Auftrag: Entscheidet euch zu jeder Frage zuerst, dann auflösen und begründen.
1. Welcher Schritt verhindert, dass man AES als lineares Gleichungssystem lösen kann?
Nur die S-Box (Inverses in GF(28)) ist nichtlinear. Die anderen drei sind linear bzw. ein XOR mit dem Schlüssel.
2. Eine Datei mit vielen gleichen 16-Byte-Blöcken wird mit AES-ECB verschlüsselt. Was erfährt ein Angreifer ohne Schlüssel?
ECB ist deterministisch je Block. Muster im Klartext bleiben als Muster im Geheimtext sichtbar (Leuchtturm).
3. Warum nutzt TLS 1.3 AES-GCM und nicht einfach AES-CTR?
GCM ist CTR plus Prüfwert. Ohne Prüfwert kann Eve gezielt Bits kippen (Station 11).