Feistel-Netzwerke: Bausteine moderner Chiffren

Anfang der 1970er-Jahre arbeitete Horst Feistel bei IBM Research an der Lucifer-Chiffre, als er eine grundlegende Erkenntnis entwickelte: Man kann eine umkehrbare Chiffre mit einer nicht umkehrbaren Rundenfunktion aufbauen.

Das war revolutionär, weil es schwierig ist, Funktionen zu entwerfen, die zugleich umkehrbar und sicher sind. Feistels Konstruktion umgeht diese Anforderung vollständig und ermöglicht den Einsatz beliebig komplexer, einseitiger Rundenfunktionen.

Bei einer Feistel-Chiffre wird der Eingabeblock in zwei gleich große Hälften geteilt: L (links) und R (rechts). In jeder Runde wird die Rundenfunktion F auf R angewendet, das Ergebnis mit L per XOR verknüpft und anschließend werden die Hälften vertauscht.

Nach n Runden werden die beiden Hälften wieder zusammengefügt, um den Geheimtext zu erzeugen. Durch das Vertauschen werden beide Hälften in abwechselnden Runden verarbeitet und gründlich durchmischt.

Die Rundenfunktion F in einem Feistel-Netzwerk nimmt die rechte Hälfte und den Rundenschlüssel als Eingaben und erzeugt eine Ausgabe, die per XOR mit der linken Hälfte verknüpft wird. Entscheidend ist, dass F nicht umkehrbar sein muss.

F kann beliebig komplex sein: Jede Kombination aus Substitutionen, Permutationen, XOR-Operationen und modularer Arithmetik ist möglich. Je komplexer und nichtlinearer F ist, desto stärker ist die Chiffre, da die Entschlüsselung F niemals umkehren muss.

Die Entschlüsselung einer Feistel-Chiffre verwendet exakt dieselbe Struktur wie die Verschlüsselung, wendet die Rundenschlüssel jedoch in umgekehrter Reihenfolge an. Das ist möglich, weil XOR seine eigene Umkehrung ist: Wenn A XOR B = C gilt, dann gilt C XOR B = A.

Da die Entschlüsselung niemals F^-1, also die Umkehrung von F, aufruft, kann die Rundenfunktion ein irreversibler Hash, eine Nachschlagetabelle oder eine beliebig komplexe Operation sein, ohne die Umkehrbarkeit der Chiffre zu beeinträchtigen.

Die mathematische Eleganz von Feistel-Netzwerken besteht darin, dass die XOR-Struktur unabhängig von der Funktionsweise von F die Umkehrbarkeit garantiert. Selbst wenn F eine Einwegfunktion wie SHA-256 ist, bleibt die gesamte Feistel-Chiffre umkehrbar.

Das macht Feistel-Chiffren äußerst flexibel. Kryptografen können sich vollständig darauf konzentrieren, F möglichst verwirrend und diffusiv zu gestalten, da die Umkehrbarkeit bereits durch die Netzwerkstruktur selbst gewährleistet wird.

Der 1977 veröffentlichte Data Encryption Standard (DES) ist eine Feistel-Chiffre mit 16 Runden, die auf 64-Bit-Blöcken mit einem 56-Bit-Schlüssel arbeitet. Jede Runde verwendet einen anderen 48-Bit-Unterschlüssel, der aus dem Hauptschlüssel abgeleitet wird.

Die Rundenfunktion von DES umfasst eine Expansionspermutation, eine XOR-Verknüpfung mit dem Unterschlüssel, acht S-Boxen für die Nichtlinearität und eine P-Box-Permutation. Diese Kombination liefert sowohl Konfusion als auch Diffusion, wie es die Prinzipien von Shannons Chiffrenentwurf verlangen.

Blowfish, 1993 von Bruce Schneier entwickelt, ist eine Feistel-Chiffre mit variabler Schlüssellänge (32–448 Bit) und 16 Runden. Sie verwendet schlüsselabhängige S-Boxen, wodurch vorberechnete Angriffe unpraktikabel werden.

Twofish, ein Finalist im AES-Wettbewerb, erweitert die Ideen von Blowfish um 128-Bit-Blöcke und 16 Runden. Beide gelten weiterhin als ungebrochen und werden in Anwendungen wie dem Passwort-Hashing mit bcrypt verwendet, das eine modifizierte Version von Blowfish nutzt.

Eine ausgeglichene Feistel-Chiffre teilt den Block in zwei gleich große Hälften. Bei einem unausgeglichenen Feistel-Netzwerk sind die Hälften unterschiedlich groß, etwa im Verhältnis 3/4 zu 1/4.

Unausgeglichene Feistel-Netzwerke können in bestimmten Kontexten Sicherheitsvorteile bieten und werden in einigen spezialisierten Chiffren eingesetzt. Die Chiffrenfamilie CAST verwendet eine ausgeglichene 64-Bit-Feistel-Struktur.

Michael Luby und Charles Rackoff bewiesen 1988, dass ein Feistel-Netzwerk mit drei Runden und pseudorandomisierten Rundenfunktionen eine sichere pseudorandomisierte Permutation (PRP) ist und eine Version mit vier Runden eine starke PRP darstellt.

Dieses theoretische Ergebnis gab Feistel-Netzwerken eine solide, beweisbare Sicherheitsgrundlage statt lediglich empirischer Zuverlässigkeit. Es bestätigte, dass die Feistel-Struktur selbst über die Rundenfunktion hinaus zur Sicherheit beiträgt.

Das von AES verwendete Substitutions-Permutations-Netzwerk (SPN) wendet Substitution und Permutation gleichzeitig auf den gesamten Block an, statt in jeder Runde nur auf eine Blockhälfte. Dadurch wird eine schnellere Diffusion erreicht.

AES erreicht bereits nach vier Runden eine vollständige Diffusion, während die Feistel-Struktur von DES für eine vergleichbare Diffusion mehr Runden benötigt. AES' SPN eignet sich außerdem besser für moderne Prozessorarchitekturen mit SIMD-Befehlen.

Der Satz von Luby und Rackoff behandelt die Rundenfunktion F als eine wirklich zufällige Funktion. In der Praxis ist F jedoch eine pseudorandomisierte Funktion, also eine schlüsselabhängige Chiffre oder ein Hash, und kein echtes Random Oracle.

Diese Lücke zwischen theoretischen Beweisen und praktischen Implementierungen ist ein wiederkehrendes Thema in der Kryptografie. Beweise schaffen Vertrauen, beruhen jedoch auf idealisierten Modellen. Die Sicherheit in der Praxis hängt außerdem von sicheren Implementierungen ohne Seitenkanal-Schwachstellen ab.

Testen Sie Ihr Verständnis des Entwurfs von Feistel-Netzwerken.

Feistel-Netzwerke sind Strukturen für Blockchiffren, die eine Rundenfunktion verwenden, die nicht umkehrbar sein muss. Die Entschlüsselung erfolgt, indem dieselbe Struktur mit den Unterschlüsseln in umgekehrter Reihenfolge ausgeführt wird.

DES, Blowfish und Twofish sind allesamt Feistel-Chiffren. Der Satz von Luby und Rackoff liefert theoretische Sicherheitsgarantien. AES verwendet stattdessen eine SPN-Struktur und bietet pro Runde eine bessere Diffusion.