Differenzielle Kryptoanalyse

Verfahren zum Brechen von Verschlüsselung

Differenzielle Kryptoanalyse verfolgt das Ziel, rundenbasierte Blockchiffren und kryptologische Hashfunktionen zu brechen. Zu diesem Zweck untersucht sie die Auswirkungen von Differenzen in Klartextblöcken auf die Differenzen in den durch Verschlüsselung erzeugten Geheimtextblöcken.

Einleitung

Bearbeiten

Die Methode der differenziellen Kryptoanalyse wurde im Jahr 1991 von den Kryptologen Eli Biham und Adi Shamir veröffentlicht.[1] Dabei handelt es sich um einen statistischen Angriff auf beliebige Feistelchiffren. Der Angriff wird als chosen plaintext attack ausgeführt. Das heißt, man nimmt an, dass der Angreifer Zugriff auf beliebige, selbstgewählte Klartext-Geheimtext-Paare hat. Ziel des Angriffs ist es, den geheimen Schlüssel der Chiffre (oder Teile davon) zu ermitteln. Der Angreifer untersucht, welchen Effekt bestimmte Differenzen von Klartextpaaren auf die Differenzen der resultierenden Geheimtextpaare haben. Diese Differenzen können genutzt werden, um die Wahrscheinlichkeiten möglicher Schlüssel zu berechnen und den wahrscheinlichsten Schlüssel zu ermitteln. Der Schlüssel kann dann vom Angreifer verwendet werden, um weitere Geheimtexte des Opfers zu entschlüsseln.

Bezug zum DES

Bearbeiten

Biham und Shamir entwickelten die differenzielle Kryptoanalyse, um die Sicherheit des seit 1976 weit verbreiteten Verschlüsselungsstandards DES zu analysieren. Sie stellten fest, dass DES durch die Konstruktion der nicht-linearen Substitutionsboxen sehr resistent gegen dieses Verfahren ist. Don Coppersmith, einer der DES-Entwickler bei IBM, gab im Jahr 1994 an, dass Sicherheit gegen diesen Angriff eines der Entwicklungsziele war.[2] Folglich wussten die Entwickler schon im Jahr 1974 von dem Angriff. Nach einer Diskussion mit der NSA entschieden sie sich, weder den Angriff selbst noch die Sicherung dagegen zu veröffentlichen.[2] Das Wissen um den Angriff erklärt, warum DES exakt 16 Runden hat: Die Komplexität eines naiven Angriffs mit der Brute-Force-Methode liegt bei   Operationen, da die effektive Länge des Schlüssels 56 Bit beträgt. Hätte DES nur 15 Runden, dann läge die Komplexität eines Angriffs mit differenzieller Kryptoanalyse mit   Operationen darunter. Bei 16 Runden ist der Angriff jedoch mit   Operationen geringfügig komplexer als mit der Brute-Force-Methode.[1]

Kern des Verfahrens ist die Analyse der Auswirkung von Differenzen in Klartextpaaren auf die Differenzen der daraus resultierenden Geheimtextpaare.

Differenzen

Bearbeiten

Die Differenzen werden bitweise gebildet, durch eine XOR-Verknüpfung. Seien   und   zwei Klartexte, so ist ihre Differenz  . Diese Differenz kann man durch die einzelnen Verschlüsselungsschritte hindurch beobachten. Schritte, welche nur XOR-Verknüpfungen enthalten, verändern die Differenz nicht. Auch Permutationen und Expansionen, wie sie in den meisten Feistelchiffren vorkommen, können leicht berechnet werden, indem auch die Bits der Differenzen in der Weise vertauscht oder dupliziert werden, wie dies die Permutationen und Expansionen vorsehen. Nur über die nicht-linearen Substitutionsboxen hinweg ist eine Berechnung der Differenzen nicht möglich.

Um das Verhalten der Differenzen in einer Substitutionsbox (S-Box) genauer zu untersuchen, gibt man unterschiedliche Eingangswerte   und   mit der gleichen Eingangsdifferenz in eine S-Box   ein, also  . Man kann dann feststellen, dass die Differenzen   der Werte   und   am Ausgang ungleich verteilt sind. Das heißt, bei konstanter Eingangsdifferenz treten einige Ausgangsdifferenzen häufiger, andere seltener oder gar nicht auf. Diese Eigenschaft einer S-Box wird in einer Differenzenverteilungstabelle festgehalten:

     
       
       

Der Wert   gibt dabei an, wie oft bei Eingangsdifferenz   die Ausgangsdifferenz   auftritt, wenn man alle möglichen Paare von Eingabewerten mit der S-Box   untersucht. Die Eingangsdifferenz   verursacht dann die Ausgangsdifferenz   mit einer Wahrscheinlichkeit

 

durch die untersuchte S-Box   mit einem   Bit breiten Eingang.

Schlüsselkandidaten (eine Runde)

Bearbeiten
 
Ausschnitt aus einer Rundenfunktion des Data Encryption Standard: Die Unterteilung des Eingangswertes und des Rundenschlüssels in 8 Blöcke zu je 6 Bit soll die Zuordnung der Bits zu den 8 S-Boxen symbolisieren.

Für eine Feistelchiffre mit nur einer Runde, kann man mit diesem Wissen bestimmte Schlüssel ausschließen. Die verbleibenden Schlüssel sind die Schlüsselkandidaten. Die Abbildung rechts macht die im Folgenden verwendeten Bezeichnungen am Beispiel des DES etwas klarer.

Der Angreifer lässt zwei Klartexte mit einer selbst gewählten Differenz verschlüsseln. Er erfährt die Geheimtexte oder zumindest deren Differenz. Er kann aus der Kenntnis der Klartexte den Status der Verschlüsselung   vor der XOR-Verknüpfung ( ) mit dem Rundenschlüssel   berechnen. Aus der Geheimtextdifferenz kann er die Ausgangsdifferenz   der S-Box   berechnen. Anhand der Differenzenverteilungstabelle ist aus der Eingangsdifferenz   und der Ausgangsdifferenz   die Anzahl der in Betracht kommenden Eingangswerte der S-Box ersichtlich. Die Paare von Eingangswerten   und  , mit Differenz  , welche die Ausgangsdifferenz   erzeugen, müssen vom Angreifer berechnet oder aus einer Tabelle abgelesen werden. Man geht davon aus, dass dem Angreifer die Berechnungsvorschrift für die S-Boxen bekannt ist (Kerckhoffs’ Prinzip).

Dem Angreifer sind nun die Werte von  , sowie die möglichen Werte von   bekannt. Damit kann er Kandidaten für den Rundenschlüssel berechnen:

 

Dies kann mit verschiedenen Klartextpaaren wiederholt werden. Der korrekte Rundenschlüssel befindet sich immer unter den Schlüsselkandidaten eines Durchlaufs. Schlüssel, die nicht in den Schlüsselkandidaten aller Durchläufe enthalten sind, scheiden damit als Rundenschlüssel aus.

Charakteristiken (mehrere Runden)

Bearbeiten

Die Menge der Eingangs- und Ausgangsdifferenzen über   Runden bezüglich irgendeines Klartextpaares, sowie der Klartext- und der Geheimtextdifferenz nennt man n-Runden-Charakteristik  . Wenn die vertauschten Hälften der Klartextdifferenz einer n-Runden-Charakteristik   der Geheimtextdifferenz einer m-Runden-Charakteristik   gleich sind, also

  und  ,

dann können diese zu einer  -Runden-Charakteristik aneinander gehängt werden.

Jeder Charakteristik   kann man eine Wahrscheinlichkeit   zuordnen, dass ein zufälliges Klartextpaar mit der gegebenen Differenz   genau die in der Charakteristik angenommenen Differenzen in den einzelnen Runden aufweist. Die Wahrscheinlichkeit einer n-Runden-Charakteristik   ist dabei das Produkt der Wahrscheinlichkeiten aller 1-Runden-Charakteristiken   aus denen sich die n-Runden-Charakteristik   zusammensetzt.

 

Die Wahrscheinlichkeit einer 1-Runden-Charakteristik ist   (siehe oben), also die Wahrscheinlichkeit, dass die Eingangsdifferenz dieser Charakteristik die Ausgangsdifferenz dieser Charakteristik verursacht.

Ein Sonderfall sind sogenannte iterative Charakteristiken, mit  , welche immer wieder an sich selbst angehängt werden können. Die vertauschten Hälften der Klartextdifferenz sind also gleich der Geheimtextdifferenz derselben Charakteristik. Diese lassen sich also leicht zu beliebig großen n-Runden-Charakteristiken zusammenhängen. Während bei nicht-iterativen Charakteristiken die Wahrscheinlichkeit mit größerem  , bedingt durch den Avalanche-Effekt, immer schneller abnimmt, bleiben die Wahrscheinlichkeiten der Teilcharakteristiken, aus denen iterative Charakteristiken zusammengesetzt sind, gleich. Iterative Charakteristiken werden deshalb bei einem Angriff bevorzugt eingesetzt.

Ein Klartextpaar, dessen Klartextdifferenz und dessen korrespondierende Ein- und Ausgangsdifferenzen der einzelnen Runden mit einer bestimmten n-Runden-Charakteristik übereinstimmen nennt man richtiges Paar. Klartextpaare, die nicht diese Differenzen erzeugen sind falsche Paare. Die Wahrscheinlichkeit, dass ein Klartextpaar mit der durch eine n-Runden-Charakteristik gegebenen Klartextdifferenz ein richtiges Paar ist, ist gleich der Wahrscheinlichkeit der n-Runden-Charakteristik  , falls zufällige unabhängige Rundenschlüssel benutzt werden. Die Verallgemeinerung, dass die Rundenschlüssel unabhängig sind, vereinfacht die Analyse und stellt sicher, dass die differenzielle Kryptoanalyse auf verschiedene Verschlüsselungsverfahren anwendbar ist.

Um nun die Rundenschlüssel der   Runden zu ermitteln, benötigt man zunächst mehrere n-Runden-Charakteristiken (mit möglichst hoher Wahrscheinlichkeit  ). Der Angreifer wählt dann eine genügend große Menge an Klartextpaaren mit Differenzen, welche denen der n-Runden-Charakteristiken entsprechen. Es lassen sich (auf unbestimmte Art und Weise) die dazugehörigen Geheimtextpaare oder deren Differenzen berechnen. Dies entspricht der Vorgehensweise einer chosen plaintext attack. Wenn dem Angreifer bereits ausreichend Klartextpaare mit den passenden Differenzen und die dazugehörigen Geheimtexte bekannt sind, kann der Angriff auch als known plaintext attack durchgeführt werden.

Entspricht auch die Differenz der Geheimtexte der von der n-Runden-Charakteristik vorgegebenen Geheimtextdifferenz, so ist das korrespondierende Klartextpaar mit Wahrscheinlichkeit   ein richtiges Paar. Die zu den einzelnen Runden der Charakteristik gehörenden Mengen mit Schlüsselkandidaten enthalten also mit Wahrscheinlichkeit   den korrekten Rundenschlüssel für die jeweilige Runde.

Dieses Vorgehen wiederholt man mit verschiedenen n-Runden-Charakteristiken. Die Rundenschlüssel, welche am häufigsten unter den Kandidaten einer Runde auftreten sind mit entsprechend hoher Wahrscheinlichkeit die gesuchten Rundenschlüssel. Abhängig vom Berechnungsverfahren der Rundenschlüssel im jeweiligen Verschlüsselungsalgorithmus kann daraus der geheime Schlüssel (oder Teile davon) berechnet werden.

Hat das Verschlüsselungsverfahren mehr als   Runden, so kann eine kleine Anzahl verbleibender Runden auch überbrückt werden, indem man für diese alle möglichen Rundenschlüssel probiert (Brute-Force-Methode) und jeweils überprüft, ob die Differenz des so gewonnenen Wertepaars mit der Geheimtextdifferenz der n-Runden-Charakteristik übereinstimmt.

Beispiel (DES)

Bearbeiten

Das folgende Beispiel bezieht sich auf den Data Encryption Standard (DES). Es soll zum Verständnis der grundlegenden Prinzipien beitragen. Zahlenwerte mit Suffix h sind hexadezimal.

Differenzenverteilungstabelle

Bearbeiten

Die folgende Tabelle zeigt einen Ausschnitt aus der Differenzenverteilungstabelle für die S-Box  :

0h 1h 2h 3h 4h 5h 6h 7h 8h 9h Ah Bh Ch Dh Eh Fh
0h 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1h 0 0 0 6 0 2 4 4 0 10 12 4 10 6 2 4
2h 0 0 0 8 0 4 4 4 0 6 8 6 12 6 4 2
34h 0 8 16 6 2 0 0 12 6 0 0 0 0 8 0 6
3Fh 4 8 4 2 4 0 2 4 4 2 4 8 8 6 2 2

Die erste Spalte zeigt die Eingangsdifferenzen  . Der Eingang einer S-Box ist 6 Bit breit. Es sind also insgesamt   Wertepaare möglich. Diese können   verschiedene Differenzen haben und zwar 0h … 3Fh.

Die Titelzeile zeigt die möglichen Ausgangsdifferenzen  . Der Ausgang einer S-Box ist 4 Bit breit. Es sind also insgesamt   Wertepaare möglich. Diese können   verschiedene Differenzen haben und zwar 0h … Fh.

Es gibt jeweils 64 Kombinationen von Eingangswerten, welche eine Eingangsdifferenz erzeugen. Die Zeilensumme muss also immer 64 sein. Intuitiv ist auch, dass bei zwei gleichen Eingangswerten (Eingangsdifferenz  ) der gleiche Ausgangswert (Ausgangsdifferenz  ) auftreten sollte. Wie in Zelle (0h, 0h) der Tabelle zu sehen ist, gilt dies für alle 64 möglichen Wertepaare mit  . Also ist die Wahrscheinlichkeit, dass     verursacht, 1.

Die Wahrscheinlichkeit, dass     verursacht, ist  .

Schlüsselkandidaten finden

Bearbeiten

Man geht davon aus, dass ein Angreifer ein Klartextpaar kennt:

  mit   und
  mit  

Dann kann er auf die rechte Hälfte der beiden Klartexte (der Teil, der in die Rundenfunktion eingeht) die Expansion anwenden:

  und
 

Es ist also

  und
 .

Dann ist   die Differenz der Werte vor der Verknüpfung mit dem Rundenschlüssel. Da beide Werte mit dem gleichen Rundenschlüssel   XOR-verknüpft werden, bleibt die Differenz unverändert:

 

Man geht weiter davon aus, dass dem Angreifer die Ausgangsdifferenz bekannt ist:

 

Die Differenzenverteilungstabelle für die S-Box   zeigt, dass es 2 mögliche Belegungen der Eingangswerte gibt, bei denen   und   ist.

Mit Kenntnis der S-Box (diese ist öffentlich bekannt) ist es möglich zu berechnen, welche 2 Belegungen für die Eingangswerte, mit der gegebenen Eingangsdifferenz, die gegebene Ausgangsdifferenz erzeugen. Zu diesem Zweck kann der Angreifer bereits im Vorhinein eine Tabelle angelegt haben, aus welcher er die Werte abliest. In diesem Fall sind die möglichen Eingangswertepaare

  oder
 .[1]

Die Schlüsselkandidaten ergeben sich aus  . Damit ist der korrekte Rundenschlüssel entweder

  oder
 .

Der Rundenschlüssel kann entweder durch Probieren oder durch Wiederholung mit einem anderen Klartextpaar gefunden werden.

Siehe auch

Bearbeiten
Bearbeiten
  • Ausführliches Paper (englisch): Eli Biham, Adi Shamir: Differential cryptanalysis of DES-like cryptosystems. In: Journal of Cryptology. 4. Jahrgang, Nr. 1, Januar 1991, S. 3–72, doi:10.1007/BF00630563 (psu.edu [PDF]).
  • Vereinfachtes Beispiel (deutsch): Praktikumsversuch. (PDF; 965 kB), S. 42 ff.

Einzelnachweise

Bearbeiten
  1. a b c Eli Biham, Adi Shamir: Differential cryptanalysis of DES-like cryptosystems. In: Journal of Cryptology. 4. Jahrgang, Nr. 1, Januar 1991, S. 3–72, doi:10.1007/3-540-38424-3_1 (psu.edu [PDF]).
  2. a b Don Coppersmith: The Data Encryption Standard (DES) and its strength against attacks. In: IBM Journal of Research and Development. 38. Jahrgang, Nr. 3, Mai 1994, S. 243 (ibm.com [PDF]).