Benutzer:Bananenfalter/Differenzielle Kryptoanalyse

Der Artikel ist jetzt hier verfügbar: Differenzielle Kryptoanalyse (Änderungen bitte direkt dort einarbeiten!)

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

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

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 differentieller Kryptoanalyse mit $2^{52}$ Operationen darunter. Bei 16 Runden ist der Angriff jedoch mit $2^{58}$ Operationen geringfügig komplexer als mit der Brut-Force-Methode.

Prinzip

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

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 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle SX_I} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle SX_I^\ast} , mit Differenz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle SX_I^\prime} , welche die Ausgangsdifferenz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle SX_E} , sowie die möglichen Werte von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle SX_I} bekannt. Damit kann er Kandidaten für den Rundenschlüssel berechnen:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Runden bezüglich irgend eines Klartextpaares, sowie der Klartext- und der Chiffretextdifferenz nennt man n-Runden-Charakteristik Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Omega} . Wenn die vertauschten Hälften der Klartextdifferenz einer n-Runden-Charakteristik Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Omega_{1P} = (L_0^\prime, R_0^\prime)} der Chiffretextdifferenz einer m-Runden-Charakteristik Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Omega_{2T} = (L_m^\prime, R_m^\prime)} gleich sind, also

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L_m^\prime = R_0^\prime} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R_m^\prime = L_0^\prime} ,

dann können diese zu einer Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (m + n)} -Runden-Charakteristik aneinander gehängt werden.

Jeder Charakteristik Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Omega} kann man eine Wahrscheinlichkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p^\Omega} zuordnen, dass ein zufälliges Klartextpaar mit der gegebenen Differenz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Omega_P} genau die in der Charakteristik angenommenen Differenzen in den einzelnen Runden aufweist. Die Wahrscheinlichkeit einer n-Runden-Charakteristik Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p^\Omega} ist dabei das Produkt der Wahrscheinlichkeiten aller 1-Runden-Charakteristiken Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_i^\Omega} aus denen sich die n-Runden-Charakteristik Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Omega} zusammensetzt.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p^\Omega = \prod_{i=1}^n p_i^\Omega}

Die Wahrscheinlichkeit einer 1-Runden-Charakteristik ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_D} (siehe oben), also die Wahrscheinlichkeit, dass die Eingangsdifferenz dieser Charakteristik die Ausgangsdifferenz dieser Charakteristik verursacht.

Ein Sonderfall sind sogenannte iterative Charakteristiken, mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 der selben 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Runden zu ermitteln, benötigt man zunächst mehrere n-Runden-Charakteristiken (mit möglichst hoher Wahrscheinlichkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p^\Omega} ein richtiges Paar. Die zu den einzelnen Runden der Charakteristik gehörenden Mengen mit Schlüsselkandidaten enthalten also mit Wahrscheinlichkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Runden, so kann eine kleine Anzahl verbleibender Runden auch überbrückt werden, indem man für diese alle möglichen Rundenschlüssel probiert (Brut-Force-Methode) und jeweils überprüft, ob die Differenz des so gewonnenen Wertepaars mit der Chiffretextdifferenz 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 Postfix h sind hexadezimal.

Differenzenverteilungstabelle

Die folgende Tabelle zeigt einen Ausschnitt aus der Differenzenverteilungstabelle für die S-Box Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S1_I} . Der Eingang einer S-Box ist 6 Bit breit. Es sind also insgesamt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^6 \cdot 2^6 = 2^{12} = 4096} Wertepaare möglich. Diese können Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^6 = 64} verschiedene Differenzen haben und zwar 0h … 3Fh.

Die Titelzeile zeigt die möglichen Ausgangsdifferenzen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S1_O} . Der Ausgang einer S-Box ist 4 Bit breit. Es sind also insgesamt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 2^4 \cdot 2^4 = 2^{16} = 256} Wertepaare möglich. Diese können Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S1_I = 0h} ) der gleiche Ausgangswert (Ausgangsdifferenz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S1_I = 0h} . Also ist die Wahrscheinlichkeit, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S1_I = 0h} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S1_O = 0h} verursacht 1.

Die Wahrscheinlichkeit, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S1_I = 34h} Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S1_O = 4h} verursacht ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{2}{64} = 0{,}03125} .

Schlüsselkandidaten finden

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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P = (L_0, R_0)} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R_0 = A800.0001h} und

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P^\ast = (L_0^\ast, R_0^\ast)} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle E(A800.0001h) = 3510.0000.0003h} und

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle E(0800.0000h) = 0110.0000.0000h}

Es ist also

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S1_E = 35h} und

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S1_E^\ast = 1h} .

Dann ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K} XOR-verknüpft werden, bleibt die Differenz unverändert:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S1_O^\prime = 4h}

Die Differenzenverteilungstabelle für die S-Box Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S1} zeigt, dass es 2 mögliche Belegungen der Eingangswerte gibt, bei denen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S1_I^\prime = 34h} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (S1_I, S1_I^\ast) = (13h, 27h)} oder

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (S1_I, S1_I^\ast) = (27h, 13h)} .

Die Schlüsselkandidaten ergeben sich aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K = S1_I \oplus S1_E} . Damit ist der korrekte Rundenschlüssel entweder

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 13h \oplus 35h = 26h} oder

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 27h \oplus 35h = 12h} .

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

Weblinks

• Ausführliches Paper (englisch): Eli Biham, Adi Shamir: Differential cryptanalysis of DES-like cryptosystems. (PDF) In: Journal of Cryptology. 4, Nr. 1, Januar 1991, S. 3-72. .
• Vereinfachtes Beispiel (deutsch): Praktikumsversuch. (PDF), S. 42 ff

Siehe auch

• Kryptoanalyse
• Lineare Kryptoanalyse