7. Lineare Kryptanalyse

Die lineare Kryptanalyse wurde von Mitsuru Matsui eingeführt. Sie benutzt lineare Approximationen, um die Funktion einer Blockchiffrierung (beispielsweise DES) zu beschreiben.

Verknüpft man einige Bits des Klartextes mit XOR, dann einige des Chiffretextes und schließlich die beiden Ergebnisse, so erhält man ein einzelnes Bit, das der XOR-Verknüpfung einiger Bits des Schlüssels entspricht. Diese Verknüpfung stellt eine lineare Approximation dar, die mit einer gewissen Wahrscheinlichkeit p stimmt. Falls p ungleich 0.5, läßt sich diese Asymmetrie ausnutzen. Aus Klartext und zugehörigem Chiffretext rät man die Werte der Schlüsselbits. Je mehr Daten man zur Verfügung hat, desto zuverlässiger ist die Schätzung. Je größer die Asymmetrie, um so eher wird man mit der gleichen Datenmenge Erfolg haben.

Man geht dabei folgenderweise vor: Zunächst sucht man gute lineare Approximationen für die einzelnen Runden des DES und verknüpft sie. Jetzt betrachtet man die S-Boxen. Es gibt 6 Eingabe- und 4 Ausgabebits. Die Eingabebits kann man auf 63 sinnvolle Arten (2⁶-1) miteinander kombinieren, die Ausgabebits auf 15 Arten. Für jede S-Box läßt sich also die Wahrscheinlichkeit dafür bestimmen, daß bei beliebig gewählter Eingabe eine XOR-Verknüpfung gewisser Eingabebits einer XOR-Verknüpfung gewisser Ausgabebits entspricht. Falls es eine Kombination gibt, die genügend weit von der Gleichverteilung entfernt ist, könnte die lineare Kryptanalyse funktionieren.

Wendet man dieses Verfahren (natürlich nur durch Einführen einiger weiterer Tricks) gegen vollständigen DES mit 16 Runden an, so benötigt man durchschnittlich 2⁴³ bekannte Klartexte. Eine Software-Implementierung dieses Angriffs bestimmte einen DES-Schlüssel auf 12 Workstations in 50 Tagen. Dies war zu dieser Zeit (1993) der erfolgreichste Angriff gegen DES.