Cryptography Reference
In-Depth Information
che der 343 Gleichungen besonders viele Belegungen hat, bei denen die Glei-
chung stimmt. Wenn beispielsweise herauskommt, dass die Gleichung
m
1
⊕
c
1
=
k
1
in 448 von 512 Belegungen (also in 87,5 Prozent der Fälle) korrekt ist,
dann bedeutet das für Mallory: Mit dem ersten und dem dritten Bit des Klartexts
(der Klartext ist ihm bekannt, da wir von einer Known-Plaintext-Attacke ausge-
hen) sowie mit dem ersten Geheimtext-Bit kann er mit 87,5 Prozent Erfolgswahr-
scheinlichkeit das erste Schlüsselbit berechnen. Der Aufwand dafür ist minimal,
da Mallory nur eine Berechnung durchführen muss.
Wenn Mallory geeignete Gleichungen findet (man spricht auch von einer line-
aren Approximierung), dann kann er auch die beiden anderen Schlüsselbits
ermitteln. Eventuell lohnt es sich für ihn, für ein Schlüsselbit mehrere Gleichun-
gen anzuwenden, um die Wahrscheinlichkeit für ein korrektes Ergebnis zu erhö-
hen. Wenn auf der rechten Seite einer Gleichung kein einzelnes Bit steht, sondern
beispielsweise
k
1
⊕
m
3
k
2
, dann muss Mallory möglicherweise ein kleines Glei-
chungssystem lösen. Fehlende Schlüsselbits kann er bei Bedarf auch per Brute
Force ermitteln.
Mit diesem Wissen kann Mallory auch komplexere Verschlüsselungsverfah-
ren lösen. Hierzu muss er für jede Runde möglichst gute lineare Approximierun-
gen finden und diese anschließend zu möglichst guten linearen Approximierun-
gen des gesamten Algorithmus zusammensetzen. Dabei helfen ihm auch
Gleichungen, die nicht besonders häufig, sondern besonders selten korrekt sind.
In der Praxis muss sich Mallory am Ende oft mit linearen Approximierungen
zufriedengeben, die nur in knapp über (bzw. knapp unter) 50 Prozent der Bele-
gungen korrekt sind. Dementsprechend kann eine lineare Kryptoanalyse recht
aufwendig sein.
Mallory kann die lineare Kryptoanalyse auch auf den DES anwenden - sogar
deutlich effektiver als die differenzielle Kryptoanalyse. Dem Erfinder der
Methode, Mitsuru Matsui, gelang 1994 ein erfolgreicher Angriff gegen den DES,
für den er zwölf Workstations 50 Tage lang beschäftigte. Er benötigte dazu
jedoch 2
43
(also über 1.000.000.000.000) Klartextblöcke - das entspricht etwa
der Anzahl der Buchstaben in 150 Millionen Exemplaren dieses Buches. Das ist
zwar deutlich besser als eine vollständige Schlüsselsuche, in der Praxis jedoch
nicht anwendbar.
Gute Chiffren-Designer haben sich bereits seit den neunziger Jahren auf die
lineare Kryptoanalyse eingestellt, weshalb moderne Verfahren stets mit entspre-
chenden Gegenmaßnahmen ausgestattet sind. Dazu muss der Chiffren-Designer
die S-Boxen so gestalten, dass sie möglichst wenig lineare Bestandteile enthalten.
Wie das geht, ist in der Literatur gut dokumentiert. Es ist durchaus möglich,
S-Boxen zu konstruieren, die sowohl gegen die differenzielle als auch gegen die
lineare Kryptoanalyse sicher sind.
⊕
