Die differentielle Kryptanalyse

Diese Analyse bzw. Angriffsform ist theoretisch schneller als der Angriff mit roher Gewalt (Brute-Force). Zum ersten Mal öffentlich entwickelt wurde das Verfahren von Shamir 1990. Vermutlich wurde dieses Verfahren allerdings schon beim Designen der S-Boxen Anfang der Siebziger zumindest berücksichtigt.

DES ohne S-Boxen

Angenommen, DES wäre ohne die S-Boxen konstruiert. An Stelle dieser wäre einfach irgendeine feste Kompressionspermutation, die 48 Bit auf 32 Bit transformiert.

Angenommen, wir ändern im Klartext ein beliebiges Bit. Durch Permutationen wird nur die Position des geänderten Bits geändert, nicht aber das Bit. Durch XOR-Verknüpfungen wird die Position nicht verändert. Es wird höchstens der Wert des Bits verändert.

Spannend wird es vor allem, wenn das Feistelnetzwerk ins Spiel kommt. Annahme, wir befänden uns vor Runde i. Wir machen eine Fallunterscheidung:

• Relevantes Bit ist in L(i):
  Die Änderung bewirkt nur eine Änderung eines Bits in R(i+1)
• Relevantes Bit ist in R(i+1):
  Jetzt werden im Ergebnis der Runde zwei Bits geändert. Allerdings befinden sich diese beiden Bits in L(i+1) und R(i+1) an derselben Position. D.h. es findet keine weitere Ausbreitung statt.

Nun kann sich die Änderung aber noch durch die Expansionspermutation aufspalten. Es hängt dann noch von unserer fiktiven Kompressionspermutation ab, ob sich diese Änderung nach 16 Runden auf alle Bits auswirkt oder nicht.

Wir halten fest: Der Schlüssel hat auf die Position der geänderten Bits gar keinen Einfluß. Der Schlüssel wird ja nur mittels XOR eingebunden. Diese Tatsache bietet z.B. bei einem Klartextangriff wohl eine gute Ansatzmöglichkeit.

DES mit S-Boxen

Erst durch die S-Boxen wird die Wechselwirkung des Schlüssels mit dem Algorithmus komplex. Sie sind das nichtlineare Element, wie wir später noch sehen werden, und verstärken den Lawineneffekt.

Man macht allerdings eine Beobachtung, die die Sicherheit der DES-Verschlüsselung einschränkt. Für bestimmte, festgehaltene Mengen geänderter Bits im Block R(i) beobachtet man eine statistische Abhängigkeit der S-Box Ausgabe vom Schlüssel.

Statt geänderter Bits redet man in der Kryptanalyse von Differenzen:

ΔA:= A XOR A’

In ΔA sind nur die Bits gesetzt, an dessen Position sich A und A’ unterscheiden.

Sei SB die S-Box Transformation, S ein Rundenschlüssel.

C := SB(A XOR S), C’:=SB(A’ XOR S), ΔC:= C XOR C’

Man kann statistisch nachweisen, daß für bestimmte Werte von ΔA die Werte von ΔC vom Schlüssel abhängig sind.

Sei nun ΔP die Differenz eines Klartextpaares (P,P’), für das eine bestimmte Differenz ΔC eine höhere Wahrscheinlichkeit hat als erwartet. Dann nennen wir solche Paare von Differenzen Charakteristiken, Klartextpaare mit den ausgezeichneten Werten für ΔP heißen gute Paare. Die "höhere Wahrscheinlichkeit" wird allerdings mit wachsender Rundenzahl wieder abnehmen.

Man nutzt das praktisch aus, indem man Charakteristiken für ein 15 Runden DES ermittelt und dann mit hinreichend vielen guten Paaren wahrscheinliche Werte für den letzten Rundenschlüssel ermittelt. Da dieser letzte Rundenschlüssel 48 Bit groß ist, müssen die letzten acht Bit durch einen Brute-Force-Angriff ermittelt werden.

Das Problem dabei ist, daß man die Wahrscheinlichkeiten sozusagen auf 2 hoch 48 Schlüssel aufaddieren muß und zudem noch genügend gute Paare im Klartext finden muß. Um 2 hoch 48 Zahlen zu vergleichen bräuchte man lediglich 1000 TByte viel Platz. So viel zur praktischen Umsetzbarkeit.

Biham und Shamir haben bei ihrem Verfahren diese Probleme umgangen. Allerdings zeigt die nachfolgende Aufwandstabelle, daß für die praktische Umsetzung nicht viel gewonnen wurde:

Allein die Frage, wie man einem Chiffrierer beim normalen DES die Datenmenge von 2 hoch 55 Klartexten unterschieben soll, lehrt einem das Gruseln.