Kryptologie Kryptoanalyse von Bitblock-Chiffren

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

• Die Idee der linearen Kryptoanalyse
• Die hypergeometrische Verteilung
• Beispiel: Eine Einrunden-Chiffre
• Die Erfolgswahrscheinlichkeit
• Beispiel: Eine Zweirunden-Chiffre
• Binäre Summen binärer Zufallsvariablen
• Lineare Pfade und lineare Hüllen
• Beispiel: Ein einfaches SP-Netz
• Die Idee der differenziellen Kryptoanalyse
• Charakteristiken und Differentiale (differenzielle Pfade und differenzielle Hüllen)

Ü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.
2. Algebraischer Angriff. Er wird durch die Nichtlinearität der Chiffre verhindert.
3. Statistische Angriffe auf versteckte Linearität:
   1. Lineare Kryptoanalyse (MATSUI/YAMAGISHI EUROCRYPT 92). Sie ist das Hauptthema dieses Abschnitts.
   2. Differenzielle Kryptoanalyse (IBM/NSA 1974 - MURPHY, SHAMIR, BIHAM 1990). 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.

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

• Angriff mit verwandten Schlüsseln (BIHAM 1992, SCHNEIER).
• Differentiale höherer Ordnung (HARPES 1993, BIHAM 1994, LAI 1994).
• Differenziell-lineare Kryptoanalyse (LANGFORD/HELLMAN 1994).
• Partielle Differentiale (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 Differentiale (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 zeigt sich oft, wie die Schwierigkeit des Angriffs über die 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. Auch hierdurch sollen statistische Unregelmäßigkeiten verhindert 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.
• 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.

E-Mail an Pommerening@imsd.uni-mainz.de.