Lineare Kryptoanalyse und Approximationstabellen

Lineare Kryptanalyse (Matsui, 1993) ist ein Angriff mit bekanntem Klartext, bei dem lineare Approximationen (XOR bestimmter Bits) einer Chiffre gesucht werden, die mit einer Wahrscheinlichkeit p ≠ 1/2 gelten. Mithilfe vieler Klartext-Chiffretext-Paare legt die statistische Abweichung Schlüsselbits offen.

Eine lineare Approximation für eine S-Box lautet: XOR der ausgewählten Eingabebits XOR XOR der ausgewählten Ausgabebits = 0 (mod 2) mit Wahrscheinlichkeit p. Ausgedrückt als: P[a·x XOR b·y = 0] = 1/2 + ε, wobei a,b Bitmasken und ε die Abweichung sind (|ε| >> 0 ist wünschenswert).

Die LAT zählt für jede Eingabemaske a und Ausgabemaske b die Anzahl der Eingaben x, für die (a·x) XOR (b·S(x)) = 0 gilt. Durch Subtraktion von 2^{n-1} erhält man die Abweichung. Eine gute S-Box hat |max_bias| = 1 (Wahrscheinlichkeit 1/2 ± 1/2^{n/2}) — sie ist damit möglichst gleichmäßig.

Bei unabhängigen linearen Approximationen über mehrere Runden multiplizieren sich die Abweichungen: ε_total = 2^{r-1} * ε_1 * ε_2 * ... * ε_r. Jede Rundenapproximation halbiert die effektive Abweichung. Nach vielen Runden nähert sich die Gesamtabweichung 0, sodass zum Nachweis exponentiell mehr Paare erforderlich sind.

Für einen Angriff auf eine r-Runden-Chiffre wird ein linearer Pfad ε über r-1 Runden gesucht. Anschließend werden N = 1/ε^2 Klartexte mit bekanntem Inhalt gesammelt. Für jedes Byte k' des Kandidatenschlüssels der letzten Runde wird die letzte Runde teilweise per XOR entschlüsselt und geprüft, ob die lineare Approximation mehr als N/2-mal gilt. Der korrekte Schlüssel k' zeigt die erwartete Abweichung.

Matsui griff 1993 das 16-rundige DES mit einer linearen Approximation über 14 Runden und einer Abweichung von 2^{-21.4} an. Dafür waren 2^{43} Klartexte mit bekanntem Inhalt erforderlich. In Phase 1 wurden 26 Schlüsselbits ermittelt, die verbleibenden 30 durch vollständiges Durchprobieren. Dies war der erste praktische Angriff, der schneller als ein Brute-Force-Angriff auf das vollständige DES war.

Die AES-S-Box hat den maximalen LAT-Eintrag |ε| = 4/256 = 1/64 pro S-Box. Die Wide-Trail-Strategie begrenzt die Anzahl aktiver S-Boxen in jedem 4-Runden-Pfad auf mindestens 25. Die Gesamtabweichung beträgt höchstens (1/64)^{25/2} ≈ 2^{-75}. Dafür wären 2^{150} Klartexte mit bekanntem Inhalt erforderlich — undurchführbar.

Differenziell: Paare mit bekanntem oder gewähltem Klartext; nutzt Ausgabedifferenzen. Linear: Klartexte mit bekanntem Inhalt; nutzt statistische lineare Approximationen. Für praktische Angriffe sind beide Varianten Angriffe mit gewähltem Klartext. Beide sind Entwurfskriterien: S-Boxen müssen gegen beide widerstandsfähig sein (niedriger maximaler DDT- und LAT-Wert).

Mehrere lineare Approximationen werden gleichzeitig verwendet, um die Datenkomplexität zu reduzieren. Nyberg und Leander erweiterten Matsuis Methode: Die Kombination von M Approximationen reduziert die benötigte Datenmenge um den Faktor log(M). Diese Methode wird auf PRESENT, SIMON und andere leichtgewichtige Chiffren angewendet.

Bei der Anwendung linearer Approximation auf Stromchiffren wird eine Korrelation zwischen dem Schlüsselstrom und einer linearen Funktion der LFSR-Ausgabe gesucht. Diese Korrelation ermöglicht bei einem Wert ungleich null eine schnellere Schlüsselermittlung als durch vollständiges Durchprobieren. Sie beeinflusste den Entwurf nichtlinearer Kombinationsfunktionen in Stromchiffren.

Bei der integralen Kryptanalyse (Knudsen-Wagner) wird eine Menge von Klartexten gewählt, bei der bestimmte Bytes alle 256 Werte annehmen, während andere fest bleiben. Nach mehreren Runden ist das XOR aller Ausgaben an bestimmten Positionen 0 (ausgeglichen). Diese Methode nutzt die Struktur von AES aus und bricht AES mit reduzierter Rundenzahl effizient.

Was besagt das Piling-Up-Lemma über die Kombination linearer Approximationen?

Lineare Kryptanalyse findet lineare Approximationen von S-Boxen mit statistischer Abweichung. AES widersteht ihr durch seine LAT-optimierte S-Box und den Wide-Trail-Entwurf. Matsui brach DES mit 2^43 Klartexten mit bekanntem Inhalt mithilfe eines 14-Runden-Pfads. Als Nächstes: Geburtstagsangriffe und das Finden von Kollisionen.