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

• Die S-Boxen sollen so nichtlinear wie möglich sein.

Muss man einen Angriff mit 2⁴³ 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:

• Angriff mit verwandten Schlüsseln ('related keys') (BIHAM 1992, SCHNEIER).
• Differenziale höherer Ordnung (HARPES 1993, BIHAM 1994, LAI 1994).
• Differenziell-lineare Kryptoanalyse (LANGFORD/HELLMAN 1994).
• Partielle Differenziale (KNUDSEN 1995).
• I/O-Summen-Analyse (HARPES/KRAMER/MASSEY 1995).
• S-Box-Paar-Analyse (DAVIES/MURPHY 1995, MIRZA 1996).
• Bumerang-Angriff (WAGNER 1999).
• Slide-Attacken auf (evtl. versteckte) Periodizität in Chiffren oder Schlüsselauswahl-Schemata (BIRYUKOV/WAGNER 1999).
• Unmögliche Differenziale (BIHAM/BIRYUKOV/SHAMIR 1999).

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 F₂-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/2ⁿZ untersucht - oder gar auf »exotische« Strukturen, die extra zur Untersuchung dieser einen Abbildung eingeführt werden. Wir beschränken uns hier exemplarisch auf die F₂-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.

• Diffusion/Lawineneffekt: Bei Änderung eines Klartextbits ändern sich ca. 50% der Geheimtextbits. Hierdurch sollen statistische Unregelmäßigkeiten vermieden werden.
• Balanciertheit: Alle Urbildmengen sind gleich groß, d. h., die Werte der Abbildung sind gleichmäßig verteilt. Unregelmäßigkeiten in der Verteilung würden einen Ansatz zur statistischen Kryptoanalyse bieten.
• Algebraische Komplexität: Die Bestimmung von Urbildern oder Teilen davon soll auf möglichst schwer lösbare Gleichungen führen. Diese Forderung hängt mit dem algebraischen Grad der Abbildung zusammen, aber nicht auf leicht zu beschreibende Weise. In letzter Zeit wird dafür ein neues Maß, die »algebraische Immunität« propagiert.
• Nichtlinearität: Hier gibt es eine Reihe von Kriterien, die auch »versteckte« Nichtlinearität messen und vergleichsweise leicht zu beschreiben und handzuhaben sind; sie zeigen u. a., wie anfällig die Abbildungen für lineare oder differenzielle Kryptoanalyse sind.
  • Das »lineare Potenzial« soll möglichst gering, das »Linearitätsprofil« möglichst ausgeglichen sein.
  • Das »differenzielle Potenzial« soll möglichst gering, das »Differenzenprofil« möglichst ausgeglichen sein.
  • Die »Nichtlinearität«, der Abstand (HAMMING-Distanz) zu affinen Abbildungen, soll möglichst groß sein.
  • Die »Linearitätsdistanz«, der Abstand zu Abbildungen mit »linearer Struktur«, soll möglichst groß sein.

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.