Differentielle Kryptoanalyse

Einleitung -- Motivation

Übersicht zur Vorgehensweise der differentiellen Kryptoanalyse

Grundlagen

Analyse einer DES-Rundenfunktion

Analyse des DES mit drei Runden

Analyse des DES mit mehreren Runden

Schlüsselbestimmung mit Hilfe der Charakteristik

Differentielle Kryptoanalyse des DES mit sechs Runden

Aufwandsanalyse und Aufwandsreduzierung

Resultate der differentiellen Kryptoanalyse

 

 

Die differentielle Kryptoanalyse ist heute eine der bekanntesten Analysemethoden für iterierte Blockchiffren. Obwohl es mit der differentiellen Kryptoanalyse nicht gelingt, einen praktikablen Angriff gegen den DES durchzuführen, ermöglicht diese Methode einen tiefen Einblick in die inneren Strukturen des DES. Zahlreiche andere Verschlüsselungsverfahren sowie DES Varianten mit weniger als 16 Runden können leicht analysiert werden. Zum Beispiel ist es möglich, mit einem einfachen PC, DES Varianten mit acht Runden zu brechen. Die Analyse dauert nur wenige Minuten. Alle wichtigen Algorithmen, Methoden und Vorgehensweisen, die zur Durchführung einer differentiellen Kryptoanalyse notwendig sind, werden auf den folgenden Seiten ausführlich erklärt. Die Darstellung folgt dabei den ersten Veröffentlichungen zur differentiellen Kryptoanalyse von Biham und Shamir. Die vorliegende Darstellung ist jedoch wesentlich ausführlicher und um zahlreiche Beispiel ergänzt, so daß es möglich ist, eigene Implementierungen zu den einzelnen Algorithmen schrittweise zu testen und Resultate und Zwischenergebnisse mit den angegebenen Werten zu vergleichen.

Das Kapitel ist in zehn Abschnitte unterteilt. Abschnitt 1 enthält eine kurze Einleitung zur Geschichte der differentiellen Kryptoanalyse.

Im darauf folgenden Abschnitt wird die grundlegende Idee der Analysemethode und eine Übersicht zur Methode vorgestellt, jedoch ohne auf Details einzugehen.

Im dritten Abschnitt wird die Präsentation der differentiellen Kryptoanalyse vorbereitet, indem die verwendeten Bezeichnungen erklärt und einige Grundlagen vorgestellt werden.

Die detaillierte Erklärung spezieller Methoden der differentiellen Kryptoanalyse beginnt in Abschnitt 4. Dabei wird die Analyse einer einzelnen DES-Rundenfunktion durchgeführt.

Im folgenden Abschnitt wird das Verfahren ein wenig erweitert, so daß es möglich ist, den DES mit drei Runden zu analysieren.

In Abschnitt 6 wird vorgeführt, daß es möglich ist, die vorgestellten Methoden derart zu verallgemeinern, daß prinzipiell die Analyse des DES mit beliebig vielen Runden möglich ist. Dabei wird der Begriff "`Charakteristik"' eingeführt.

Eine detaillierte Darstellung dessen, wie man mit Hilfe einer Charakteristik Kryptoanalysen für DES-Varianten durchführt, ist in Abschnitt 7 enthalten.

Um die entscheidenden Algorithmen und Vorgehensweisen, die in den ersten sieben Abschnitten des Kapitels vorgestellt werden, zu vertiefen, werden im achten Abschnitt die Analyseresultate für den DES mit sechs Runden vorgestellt. Dabei wird deutlich, mit welchem Aufwand eine differentielle Kryptoanalyse verbunden ist.

Für die Aufwandsabschätzung einer differentiellen Kryptoanalyse wird in Abschnitt 9 eine entsprechende Formel vorgestellt. Außerdem werden Ideen zur Reduzierung des Aufwands genannt.

Im letzten Abschnitt werden einige Resultate der differentiellen Kryptoanalyse bezüglich der inneren Strukturen des DES vorgestellt. Das geschieht in der Form, daß Änderungen am DES Algorithmus vorgenommen werden und anschließend Charakteristiken vorgestellt werden, die zeigen, daß durch die vorgenommenen Änderungen wesentlich effektiver Analysen möglich sind. Es zeigt sich, daß fast jede Veränderung des DES-Algorithmus eine erfolgreiche differentielle Kryptoanalyse ermöglicht.