Cryptography Reference
In-Depth Information
Als Nächstes betrachten wir das Verschlüsselungsverfahren in Abbildung 7-4.
Dieses verwendet die gleiche S-Box wie das zuvor behandelte, hat aber zwei Run-
den. Pro Runde wird ein Subschlüssel der Länge 3 Bit eingebracht, es gibt also
2
6
=64 Schlüssel. Im Rahmen einer differenziellen Kryptoanalyse verschlüsselt
Mallory zwei Klartexte mit der Differenz 110. Nehmen wir an, er erhält als
Ergebnis die Differenz 111. Mallory weiß, dass die Ausgangsdifferenz der ersten
S-Box 001, 010, 100 oder 111 betragen muss, da die Eingangsdifferenz 110 nur
diese vier Werte erzeugt. Durch Ausprobieren oder Nachschauen in einer vorbe-
rechneten Tabelle findet Mallory außerdem heraus, dass nur die Werte 110, 100,
011 und 001 als Eingangsdifferenzen der zweiten S-Box infrage kommen, da nur
diese die Ausgangsdifferenz 111 erzeugen. Durch einen Abgleich der Ausgangs-
differenzen der ersten und der Eingangsdifferenzen der zweiten S-Box kann Mal-
lory erkennen, dass die Differenz auf dem Weg von der ersten zur zweiten S-Box
001 oder 100 beträgt (die Exklusiv-oder-Verknüpfungen mit dem Schlüssel
ändern wiederum nichts an den Differenzen). Zu jeder der beiden Differenzen
gibt es zwei Paare, die sie erzeugen. Außerdem gibt es jeweils zwei Eingangsdiffe-
renzen der ersten S-Box, die sie erzeugt haben können, und zu diesen wiederum
zwei Paare. Insgesamt haben wir damit acht Kombinationen, die Mallory durch-
probieren muss, um den richtigen Schlüssel zu finden. Gegenüber einer vollstän-
digen Schlüsselsuche bei 64 Schlüsseln ist das schon ein Vorteil.
Die differenzielle Kryptoanalyse lässt sich in ähnlicher Form auch auf ein
Drei-Runden-Verschlüsselungsverfahren übertragen. Die Schlüssellänge beträgt
hier 9 Bit, wodurch es 512 Schlüssel gibt. Durch das Suchen von Differenzkombi-
nationen kann Mallory den Schlüssel in 10-20 Arbeitsschritten ermitteln, was
bei 512 Schlüsseln ein deutlicher Vorteil gegenüber Brute Force ist.
In der Praxis hat es Mallory allerdings mit deutlich komplexeren Verfahren
zu tun. Der DES hat beispielsweise 16 Runden, acht verschiedene 6×4-S-Boxen
und pro Runde einen 48-Bit-Subschlüssel. Die differenzielle Kryptoanalyse ist
dennoch auch hier anwendbar (eine gute Erklärung dazu findet sich in [Heys]).
Dazu muss Mallory zunächst die S-Boxen untersuchen und die Verteilung von
Eingangs- sowie Ausgangsdifferenzen betrachten. Anschließend kann er mithilfe
gewählter Klartexte nach Differenzen suchen, die sich über die Runden hinweg
fortpflanzen. Die Einbringung des Schlüssels per Exklusiv-oder-Verknüpfung
ändert wiederum die Differenzen nicht. Die Permutationen des DES kann Mal-
lory bei der Verfolgung der Differenzen leicht herausrechnen, da diese nur die
Reihenfolge der Bits verändern. aufgrund der vielen Runden kann Mallory nor-
malerweise keine eindeutigen Differenzenpfade ermitteln, die sich vom Klartext
bis zum Geheimtext erstrecken, doch er kann Varianten ermitteln, aus denen er
durch Probieren die richtige findet. In vielen Fällen findet Mallory den Schlüssel
auf diese Weise deutlich schneller als durch eine vollständige Suche.
Die differenzielle Kryptoanalyse wurde in den neunziger Jahren so manchem
neu entwickelten Verschlüsselungsverfahren zum Verhängnis. Als besonders
anfällig erwies sich das DES-ähnliche Verfahren FEAL, dessen ursprüngliche Ver-
