[JoGu]

Kryptologie

Kryptoanalyse von Bitblock-Chiffren

a7Hzq .#5r<
kÜ\as TâÆK$
ûj(Ö2 ñw%h:
Úk{4R f~`z8
¤˜Æ+Ô „&¢Dø

  1. Die Idee der linearen Kryptoanalyse [PDF].
  2. Beispiel: Eine Einrunden-Chiffre [PDF].
  3. Die hypergeometrische Verteilung [PDF].
  4. Die Erfolgswahrscheinlichkeit [PDF].
  5. Beispiel: Eine Zweirunden-Chiffre [PDF].
  6. Binäre Summen binärer Zufallsvariablen [PDF].
  7. Lineare Pfade und lineare Hüllen [PDF].
  8. Beispiel: Ein einfaches SP-Netz
  9. Die Idee der differenziellen Kryptoanalyse [PDF].
  10. Charakteristiken und Differentiale (differenzielle Pfade und differenzielle Hüllen)

Den ganzen Abschnitt gibt's auch am Stück (mit kleinen Lücken) als PDF-Datei.


Übersicht

Für die Kryptoanalyse von Bitblock-Chiffren sind folgende allgemeine Ansätze bekannt:

  1. Exhaustion = vollständige Schlüsselsuche. Sie wird durch Wahl einer genügend großen Schlüssellänge unmöglich gemacht. - Viele der weiteren bekannten Angriffe zielen darauf ab, den Suchraum für die Exhaustion spürbar zu verkleinern.
  2. Algebraischer Angriff. Er wird durch die Nichtlinearität der Chiffre erschwert oder verhindert.
  3. Statistische Angriffe auf versteckte Linearität:
    1. Lineare Kryptoanalyse (MATSUI/YAMAGISHI EUROCRYPT 92). Sie ist das Hauptthema dieses Abschnitts.
    2. Differenzielle Kryptoanalyse (MURPHY, SHAMIR, BIHAM 1990 - bei IBM/NSA schon 1974 bekannt). Sie wird im Anschluss daran kurz erläutert.
    3. Verallgemeinerungen und Mischformen, s. u.

Im Gegensatz zur differenziellen Kryptoanalyse war die lineare Kryptoanalyse den DES-Entwicklern wahrscheinlich nicht bekannt; demgemäß ist DES gegen sie nicht optimal resistent. Es gab nur das Design-Kriterium

Aber SHAMIR bemerkte schon früh (CRYPTO 85), dass es »lineare Approximationen« für die S-Boxen gibt, deren Übereinstimmung besser als zufällig ist. Es dauerte allerdings weitere 8 Jahre, bis es MATSUI gelang, diese Beobachtung systematisch auszunutzen, siehe hier (externer Link).

Muss man einen Angriff mit 243 bekannten Klartextblöcken ernst nehmen? [FAQ]

Darüber hinaus sind in den letzten Jahren verschiedene Verallgemeinerungen und Kombinationen von linearer und differenzieller Kryptoanalyse entwickelt worden:

Alle diese Verfahren einschließlich der linearen und der differenziellen Kryptoanalyse sind allerdings kaum konkret zum Brechen einer Chiffre im Sinne der klassischen Kryptoanalyse anwendbar. Sie setzen so viele bekannte Klartexte voraus, wie man in realistischen Situationen kaum je erhalten kann. Ihr Sinn liegt aber vor allem darin, sinnvolle Maße für die Sicherheit von Bitblock-Chiffren zu gewinnen. Ein solches Sicherheitsmaß ist z. B. die Anzahl bekannter Klartextblöcke, die man für einen Angriff benötigt. Chiffren, die selbst unter unrealistischen Annahmen über die Kenntnisse des Angreifers sicher sind, können als in der Praxis besonders sicher gelten.

Hier zeigt sich die Kryptoanalyse in ihrem »legalen« Aspekt - sie dient nicht zu kriminellen Ausspähaktionen, sondern ist ein wichtiges Werkzeug für die Konstruktion starker Chiffren.

Bei FEISTEL- oder ähnlichen iterierten Chiffren startet man die Angriffe bei den nichtlineraen Bestandteilen der einzelnen Runden - die wie bei LUCIFER und DES meist S-Boxen genannt werden - und versucht, den Angriff über mehrere Runden auszudehnen. Dabei sieht man oft, wie die Schwierigkeit des Angriffs mit der Rundenzahl zunimmt. So erhält man Kriterien, ab wievielen Runden eine Chiffre »sicher« ist.

Man darf dabei nicht vergessen, dass sich der Angriff immer auf eine bestimmte algebraische Struktur bezieht; hier auf die F2-Vektorraumstruktur des Klartextblock-Raums. Selbstverständlich kann man ähnliche Angriffsversuche auch auf andere Strukturen ansetzen; eine Abbildung, die komplex aussieht, könnte z. B. plötzlich einfach aussehen, wenn man ihre Wirkung auf die Struktur als zyklische Gruppe Z/2nZ untersucht - oder gar auf »exotische« Strukturen, die extra zur Untersuchung dieser einen Abbildung eingeführt werden. Wir beschränken uns hier exemplarisch auf die F2-Vektorraumstruktur, über die man am meisten weiß.


Kriterien für Bitblock-Chiffren

... bzw. deren Runden-Abbildungen oder deren nichtlineare Bausteine, die S-Boxen.

Sie werden zum großen Teil im mathematischen Einschub behandelt.

Einige dieser Kriterien lassen sich gleichzeitig erfüllen, andere widersprechen sich teilweise, so dass das Design einer Bitblock-Chiffre insbesondere eine Abwägung der verschiedenen Kriterien erfordert; statt der Optimierung nach einem Kriterium ist ein möglichst gleichmäßig hohes Niveau bezüglich aller Kriterien anzustreben.

Zur Zeit wird grundsätzlich der Konflikt zwischen Balanciertheit und Nichtlinearität zu Gunsten der Balanciertheit entschieden. Dafür gibt es aber keinen wirklich stichhaltigen Grund; statistische Angriffe, die die Ungleichverteilung der Bilder bei nicht balancierten Abbildungen ausnutzen, sind einfach leichter zu begreifen und werden daher höher gewichtet. Die Abstriche bei der Nhtlinearität bekommt man durch Erhöhung der Rundenzahl in den Griff.

Die Bezeichnungen und Ergebnisse des Abschnitts »Linearitätsmaße für BOOLEsche Abbildungen« werden in diesem Abschnitt - oft ohne expliziten Hinweis - verwendet.


Autor: Klaus Pommerening, 11. April 2000; letzte Änderung: 5. Juni 2008.