Grundlagen der differentiellen Kryptoanalyse

Differenzielle Kryptanalyse (Biham und Shamir, 1990) ist ein Angriff mit gewähltem Klartext, bei dem untersucht wird, wie sich Unterschiede in Klartextpaaren durch eine Chiffre fortpflanzen. Indem Eingabedifferenzen gefunden werden, die mit hoher Wahrscheinlichkeit vorhersehbare Ausgabedifferenzen erzeugen, kann ein Angreifer statistisch Schlüsselbits ermitteln.

Für XOR-basierte Chiffren gilt: Differenz ΔX = X XOR X'. Für additionsbasierte Chiffren gilt: Differenz ΔX = X - X' mod 2^n. XOR-Differenzen sind am weitesten verbreitet, da XOR mit der XOR-Schlüsselverknüpfung kommutiert (Effekte des Schlüsselplans heben sich in differentiellen Paaren auf).

Ein differentielles Paar (P, P') hat die Eingabedifferenz ΔP = P XOR P'. Nach der Verschlüsselung entsteht (C, C') mit der Ausgabedifferenz ΔC = C XOR C'. Eine nützliche Differenz ist ΔP → ΔC mit hoher Wahrscheinlichkeit p — das bedeutet, dass viele Paare (P, P') mit der Differenz ΔP die Ausgabedifferenz ΔC erzeugen.

Die DDT (Differential Distribution Table) zählt für jede Eingabedifferenz Δx und Ausgabedifferenz Δy, wie viele Eingaben x die Bedingung S(x) XOR S(x XOR Δx) = Δy erfüllen. Durch Division durch 2^n erhält man die Wahrscheinlichkeit. Eine gute S-Box hat den maximalen DDT-Wert 2 (Wahrscheinlichkeit 1/2^{n-1}) — also keine starken Differenzen.

Für eine Blockchiffre mit r Runden wird eine Folge ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1} gesucht, bei der die Wahrscheinlichkeit jedes Rundenübergangs bekannt ist. Die Wahrscheinlichkeiten werden über die Runden multipliziert: Gesamtwahrscheinlichkeit p = p1 * p2 * ... * p_{r-1}. Der Angriff verwendet 2/p Paare, um den Schlüssel der letzten Runde zu ermitteln.

Bei einer differentiellen Charakteristik über r-1 Runden mit hoher Wahrscheinlichkeit werden N = 2/p Klartextpaare gesammelt. Für jeden Kandidaten des Rundenschlüssels K' werden beide Chiffretexte eine Runde entschlüsselt, die Ergebnisse per XOR verknüpft und darauf geprüft, ob die Differenz ΔU_{r-1} entspricht. Der korrekte Schlüssel K' stimmt ungefähr N/2-mal überein; falsche Schlüssel stimmen ungefähr N/2^{bit_size}-mal überein.

Die AES-S-Box ist die multiplikative Inverse über GF(2^8), gefolgt von einer affinen Transformation. Ihr maximaler DDT-Wert beträgt 4 (von 256), was eine differentielle Wahrscheinlichkeit von höchstens 4/256 = 1/64 pro S-Box ergibt. AES hat 4 S-Boxen pro Runde, aber der Wide-Trail-Entwurf stellt sicher, dass vollständige differentielle Pfade unter 2^{-100} liegen.

Joan Daemens Wide-Trail-Entwurf (verwendet in AES/Rijndael): Die Verzweigungszahl B von MixColumns wird festgelegt. Jeder nichttriviale differentielle Pfad durch eine Runde aktiviert mindestens B aktive S-Boxen. 4 Runden × 4 S-Boxen pro Runde garantieren mindestens 25 aktive S-Boxen → Wahrscheinlichkeit < 2^{-100}.

Abgeschnittene Differenzen geben nur einen Teil der Differenz an (z. B. nur, welche Spalten aktiv sind, nicht die exakten Differenzwerte). Dadurch werden Angriffe auf mehr Runden ermöglicht, wenn vollständige Differenzen zu schwach sind. Sie werden gegen AES mit reduzierter Rundenzahl, SERPENT und andere SPN-Chiffren eingesetzt.

Eine unmögliche Differenz ist ein Paar (ΔP, ΔC), das für keinen Schlüssel auftreten kann. Jeder Schlüssel, der ein beobachtetes Paar (P, P') mit dieser Differenz abbildet, wird ausgeschlossen. Durch das Sammeln ausreichender Paare werden alle falschen Schlüssel ausgeschlossen, sodass der korrekte Schlüssel übrig bleibt.

Der Boomerang-Angriff (Wagner, 1999) kombiniert zwei kurze Differenzen zu einem adaptiven Angriff mit gewähltem Klartext und Chiffretext. Dabei wird die Chiffre in zwei Hälften zerlegt, die jeweils eine kurze differentielle Charakteristik mit hoher Wahrscheinlichkeit besitzen. So wird ein Angriff über mehr Runden ermöglicht, als eine einzelne Differenz erlauben würde.

Welchen Zweck hat die Differential Distribution Table (DDT) in der Kryptanalyse?

Differenzielle Kryptanalyse nutzt die Fortpflanzung von Eingabe- zu Ausgabedifferenzen mit hoher Wahrscheinlichkeit. AES widersteht ihr durch seine DDT-optimierte S-Box und den Wide-Trail-Entwurf. Als Nächstes: lineare Kryptanalyse und Approximationstabellen.