Lineare Kryptoanalyse

Einleitung -- Motivation

Grundlagen

Übersicht zur Vorgehensweise der linearen Approximation

Analyse des DES mit drei Runden

Analyse des DES mit fünf Runden

Analyse des DES mit acht Runden

Analyse des DES mit mehr als acht Runden

Aufwand und Erfolgswahrscheinlichkeit der linearen Analyse

 

 

Die lineare Kryptoanalyse ist heute eine der effektivsten Analysemethoden gegen iterierte Blockchiffren. Grundsätzlich handelt es sich um einen Angriff, der große Mengen Geheimtext mit bekanntem Klartext voraussetzt (Known Plaintext Attack). Unter bestimmten Umständen können aber auch Angriffe durchgeführt werden, bei denen nur Geheimtexte bekannt sind. Alle wichtigen Algorithmen, Methoden und Vorgehensweisen, die zur Durchführung einer linearen Kryptoanalyse mit bekanntem Klartext notwendig sind, werden in diesem Kapitel ausführlich erklärt.

Die Darstellung folgt dabei der ersten Veröffentlichung zur linearen Kryptoanalyse von Mitsuru Matsui, ist jedoch ausführlicher und um einige Beispiel ergänzt. Damit ist es möglich, eigene Implementierungen zu testen und Zwischenergebnisse mit den angegebenen Werten zu vergleichen.

Das Kapitel ist in acht Abschnitte unterteilt. Abschnitt 1 enthält eine kurze Einleitung zur Geschichte und den grundlegenden Möglichkeiten der linearen Kryptoanalyse.

Im darauf folgenden Abschnitt werden einige Grundlagen über lineare boolesche Funktionen und die verwendete Notation präsentiert.

Anschließend --- im dritten Abschnitt --- wird die grundlegende Idee sowie eine Übersicht zur Vorgehensweise der Analyse durch lineare Approximation präsentiert. Dabei wird auch die lineare Kryptoanalyse einer einzelnen DES Runde durchgeführt.

Die lineare Kryptoanalyse des DES mit drei Runden wird in Abschnitt 4 vorgestellt.

Im darauf folgenden Abschnitt wird das Verfahren ein wenig erweitert, so daß es möglich ist, den DES mit fünf Runden zu analysieren. Diese Analyse zielt darauf, jeweils ein Bit des verwendeten Schlüssels zu bestimmen.

In Abschnitt 6 wird vorgeführt, wie es möglich ist, die vorgestellten Methoden derart zu erweitern, daß mehrere Schlüsselbits bestimmt werden. Das Verfahren wird am Beispiel des DES mit acht Runden ausführlich beschrieben und demonstriert.

Eine detaillierte Darstellung dessen, wie man mit Hilfe linearer Approximationen Kryptoanalysen für DES-Varianten mit mehr als acht Runden durchführt, ist in Abschnitt 7 enthalten.

Die Aufwandsabschätzung und die Berechnung der Erfolgswahrscheinlichkeit einer linearen Kryptoanalyse ist Thema des letzten Abschnitts in diesem Kapitel.