Differenzielle Kryptoanalyse

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 Chiffretextblö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-Chiffretext-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 Chiffretextpaare 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 Chiffretexte 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 2^{56} 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 differentieller Kryptoanalyse mit 2^{52} Operationen darunter. Bei 16 Runden ist der Angriff jedoch mit 2^{58} Operationen geringfügig komplexer als mit der Brute-Force-Methode.[1]

Prinzip[Bearbeiten]

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

Differenzen[Bearbeiten]

Die Differenzen werden bitweise gebildet, durch eine XOR-Verknüpfung. Seien P und P^\ast zwei Klartexte, so ist ihre Differenz P^\prime = P \oplus P^\ast. 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 SX_I und SX_I^\ast mit der gleichen Eingangsdifferenz in eine S-Box X ein, also SX_I^\prime = const. Man kann dann feststellen, dass die Differenzen SX_O^\prime der Werte SX_O und SX_O^\ast 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:

SX_{O0}^\prime SX_{O1}^\prime SX_{O2}^\prime
SX_{I0}^\prime x_{0,0} x_{1,0} x_{2,0}
SX_{I1}^\prime x_{0,1} x_{1,1} x_{2,1}

Der Wert x_{i,j} gibt dabei an, wie oft bei Eingangsdifferenz SX_{Ij}^\prime die Ausgangsdifferenz SX_{Oi}^\prime auftritt, wenn man alle möglichen Paare von Eingabewerten mit der S-Box X untersucht. Die Eingangsdifferenz SX_{Ij}^\prime verursacht dann die Ausgangsdifferenz SX_{Oi}^\prime mit einer Wahrscheinlichkeit

p_D = \frac{ x_{i,j} }{ 2^l }

durch die untersuchte S-Box X mit einem l 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 Chiffretexte oder zumindest deren Differenz. Er kann aus der Kenntnis der Klartexte den Status der Verschlüsselung SX_E vor der XOR-Verknüpfung (\oplus) mit dem Rundenschlüssel K berechnen. Aus der Chiffretextdifferenz kann er die Ausgangsdifferenz SX_O^\prime der S-Box X berechnen. Anhand der Differenzenverteilungstabelle ist aus der Eingangsdifferenz SX_I^\prime und der Ausgangsdifferenz SX_O^\prime die Anzahl der in Betracht kommenden Eingangswerte der S-Box ersichtlich. Die Paare von Eingangswerten SX_I und SX_I^\ast, mit Differenz SX_I^\prime, welche die Ausgangsdifferenz SX_O^\prime 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 SX_E, sowie die möglichen Werte von SX_I bekannt. Damit kann er Kandidaten für den Rundenschlüssel berechnen:

K = SX_E \oplus SX_I

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 n Runden bezüglich irgendeines Klartextpaares, sowie der Klartext- und der Chiffretextdifferenz nennt man n-Runden-Charakteristik \Omega. Wenn die vertauschten Hälften der Klartextdifferenz einer n-Runden-Charakteristik \Omega_{1P} = (L_0^\prime, R_0^\prime) der Chiffretextdifferenz einer m-Runden-Charakteristik \Omega_{2T} = (L_m^\prime, R_m^\prime) gleich sind, also

L_m^\prime = R_0^\prime und R_m^\prime = L_0^\prime,

dann können diese zu einer (m + n)-Runden-Charakteristik aneinander gehängt werden.

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

p^\Omega = \prod_{i=1}^n p_i^\Omega

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

Ein Sonderfall sind sogenannte iterative Charakteristiken, mit \Omega_1 = \Omega_2, welche immer wieder an sich selbst angehängt werden können. Die vertauschten Hälften der Klartextdifferenz sind also gleich der Chiffretextdifferenz 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 n, 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 p^\Omega, 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.

Angriff[Bearbeiten]

Um nun die Rundenschlüssel der n Runden zu ermitteln, benötigt man zunächst mehrere n-Runden-Charakteristiken (mit möglichst hoher Wahrscheinlichkeit p^\Omega). Der Angreifer wählt dann eine genügend große Menge an Klartextpaaren mit Differenzen, welche denen der n-Runden-Charakteristiken entsprechen. Er lässt sich (auf unbestimmte Art und Weise) die dazugehörigen Chiffretextpaare 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 Chiffretexte bekannt sind, kann der Angriff auch als known plaintext attack durchgeführt werden.

Entspricht auch die Differenz der Chiffretexte der von der n-Runden-Charakteristik vorgegebenen Chiffretextdifferenz, so ist das korrespondierende Klartextpaar mit Wahrscheinlichkeit p^\Omega ein richtiges Paar. Die zu den einzelnen Runden der Charakteristik gehörenden Mengen mit Schlüsselkandidaten enthalten also mit Wahrscheinlichkeit p^\Omega 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 n 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 Chiffretextdifferenz 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 S1:

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 S1_I. Der Eingang einer S-Box ist 6 Bit breit. Es sind also insgesamt 2^6 \cdot 2^6 = 2^{12} = 4096 Wertepaare möglich. Diese können 2^6 = 64 verschiedene Differenzen haben und zwar 0h … 3Fh.

Die Titelzeile zeigt die möglichen Ausgangsdifferenzen S1_O. Der Ausgang einer S-Box ist 4 Bit breit. Es sind also insgesamt 2^4 \cdot 2^4 = 2^{8} = 256 Wertepaare möglich. Diese können 2^4 = 16 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 S1_I = 0h) der gleiche Ausgangswert (Ausgangsdifferenz S1_O = 0h) auftreten sollte. Wie in Zelle (0h, 0h) der Tabelle zu sehen ist, gilt dies für alle 64 möglichen Wertepaare mit S1_I = 0h. Also ist die Wahrscheinlichkeit, dass S1_I = 0h S1_O = 0h verursacht, 1.

Die Wahrscheinlichkeit, dass S1_I = 34h S1_O = 4h verursacht, ist \frac{2}{64} = 0{,}03125.

Schlüsselkandidaten finden[Bearbeiten]

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

P = (L_0, R_0) mit R_0 = A800.0001h und
P^\ast = (L_0^\ast, R_0^\ast) mit R_0^\ast = 0800.0000h

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

E(A800.0001h) = 3510.0000.0003h und
E(0800.0000h) = 0110.0000.0000h

Es ist also

S1_E = 35h und
S1_E^\ast = 1h.

Dann ist S1_E^\prime = S1_E \oplus S1_E^\ast = 34h die Differenz der Werte vor der Verknüpfung mit dem Rundenschlüssel. Da beide Werte mit dem gleichen Rundenschlüssel K XOR-verknüpft werden, bleibt die Differenz unverändert:

S1_I^\prime = S1_I \oplus S1_I^\ast = (S1_E \oplus K) \oplus (S1_E^\ast \oplus K) = S1_E \oplus S1_E^\ast = S1_E^\prime = 34h

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

S1_O^\prime = 4h

Die Differenzenverteilungstabelle für die S-Box S1 zeigt, dass es 2 mögliche Belegungen der Eingangswerte gibt, bei denen S1_I^\prime = 34h und S1_O^\prime = 4h 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

(S1_I, S1_I^\ast) = (13h, 27h) oder
(S1_I, S1_I^\ast) = (27h, 13h).[1]

Die Schlüsselkandidaten ergeben sich aus K = S1_I \oplus S1_E. Damit ist der korrekte Rundenschlüssel entweder

13h \oplus 35h = 26h oder
27h \oplus 35h = 12h.

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

Siehe auch[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

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