Differenzielle Kryptoanalyse

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

Die Methode der differenziellen Kryptoanalyse wurde im Jahr 1991 von den Kryptologen Eli Biham und Adi Shamir veröffentlicht. 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

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. 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. 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 differenzieller 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.

Prinzip

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

Differenzen

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)

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 $SX_{E}$ vor der XOR-Verknüpfung ($\oplus$) mit dem Rundenschlüssel $K$ berechnen. Aus der Geheimtextdifferenz 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)

Die Menge der Eingangs- und Ausgangsdifferenzen über $n$ Runden bezüglich irgendeines Klartextpaares, sowie der Klartext- und der Geheimtextdifferenz 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 Geheimtextdifferenz 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 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 $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

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. 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 $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 Geheimtextdifferenz der n-Runden-Charakteristik übereinstimmt.

Beispiel (DES)

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

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

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)$.

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

• Kryptoanalyse
• Lineare Kryptoanalyse

Weblinks

• 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.