Lineare Kryptoanalyse

Die lineare Kryptoanalyse ist eine Methode, blockbasierte, symmetrische Verfahren zu knacken. Es werden Chosen-Plaintext-Angriffe auf die nicht-lineare Bestandteile des Algorithmus (also meist die Substitutionsboxen) benutzt, um die dort integrierten linearen Bestandteile (etwa XOR-Verknüpfungen) zu isolieren. So können einzelne Schlüsselbits ausfindig gemacht werden und die Brute-Force-Attacke muss nur noch über einen verminderten Schlüsselraum ausgeführt werden. Die lineare Kryptoanalyse wurde 1992 vom japanischen Kryptologen Mitsuru Matsui erfunden.

Der Angriff wird als chosen plaintext attack (Attacke bei frei wählbarem Klartext) ausgeführt. Voraussetzung ist, dass der Angreifer Zugriff auf beliebige, selbstgewählte Klartext-Chiffretext-Paare hat. Die Attacken sind so gestaltet, dass die lineare Bestandteile des Algorithmus offenkundig werden. Etwa, weil herausgefunden wird, das ein Bestandteil immer den gleichen Wert (also konstant) ist. Nachdem die lineare Bestandteile und deren Funktionsweise isoliert ist, können diese geschickt so kombiniert werden, dass ggf. einzelne Schlüsselbits ermittelt werden können. Aber auch wenn Schlüsselbits nicht mit 100%iger Sicherheit bestimmt werden können, so hilft auch schon eine von der Normalverteilung abweichende Wahrscheinlichkeit weiter, die man durch Gleichungen (Stichwort lineare Approximation) beschreiben kann. Gegenbenenfalls lassen sich Gleichungsbestandteile durch andere gefunden Gleichungen ersetzen und so das Gleichungssystem vereinfachen oder Variablen auflösen.

Zum Schluss bleibt eine Berechnungsformel, deren Berechnung nur den Bruchteil der Zeit eines Brute-Force-Angriffes ausmacht. Mtsuri Matsui gelang so 1994 einen Angriff gegen DES, bei dem 12 Computer 50 Tage lang rechneten und 243 (8.8 * 1012) Klartextblöcke ausprobierten. Das ist zwar rund 10.000 mal schneller als ein Brute-Force-Attack über den kompletten Schlüsselraum (256 = 7.2 * 1016, aber dennoch nicht praxistauglich.

Heute designed man die Algorithmen natürlich so, dass sie gegen Angriffe der lineare Kryptoanalyse gehärtet sind, z. B. indem man die S-Boxen so entwirft, dass sie möglichst wenig lineare Bestandteile beinhalten.

Quellen, Literaturverweise und weiterführende Links

Schmeh, Klaus: Kryptografie: Verfahren - Protokolle - Infrastrukturen, dpunkt Verlag, 5. Auflage 2013, iX-Edition, S. 110
Matsui und Yamagishi: A new method for known plaintext attack of FEAL cipher, EUROCRYPT 1992
Matsui, Mitsuru: Linear cryptanalysis method for DES cipher, EUROCRYPT 1993
Matsui, Mitsuru: The first experimental cryptanalysis of the data encryption standard, CRYPT 1994