FEAL

FEAL
Die Rundenfunktion F von FEAL
Entwickler	Akihiro Shimizu und Shoji Miyaguchi, beide von NTT
Veröffentlicht	FEAL-4 1987; FEAL-N/NX 1990
Schlüssellänge	64 Bit (FEAL), 128 Bits (FEAL-NX)
Blockgröße	64 Bit
Struktur	Feistelchiffre
Runden	Ursprünglich 4 bei FEAL-4, dann erweitert auf 8 Runden; FEAL-N/NX mit variabler Rundenanzahl, wobei minimal 32 empfohlen sind.
Beste bekannte Kryptoanalyse
FEAL-4 ist sehr anfällig für die lineare Kryptoanalyse mit nur fünf bekannten Klartextblöcken. (Matsui und Yamagishi, 1992). FEAL-N/NX ist für die differentielle Kryptoanalyse mit weniger als 31 Runden anfällig. (Biham und Shamir, 1991).

FEAL (Fast Data Encipherment Algorithm) ist eine Blockchiffre und zählt zu den symmetrischen Feistelchiffren. Das Ziel bei der Entwicklung, die von dem japanischen Telefonkonzern Nippon Telegraph and Telephone (NTT) ausging, war, eine effiziente Implementierung eines Verschlüsselungsalgorithmus in Software auch für kleine Mikrocontroller zu erreichen und damit eine Alternative zu dem von amerikanischen Behörden entwickelten Data Encryption Standard (DES) zu schaffen. DES ist in Software nur vergleichsweise ineffizient zu implementieren.

FEAL diente in den Jahren nach seiner Entwicklung 1987 vor allem als Testobjekt für verschiedenartige Angriffszenarien auf Verschlüsselungsalgorithmen. Insbesondere diente er dazu, die heute wesentlichen Analyseverfahren, die differentielle Kryptoanalyse und die lineare Kryptoanalyse, in ihrer Entwicklung voranzubringen. FEAL selber gilt, in den ursprünglichen Versionen wie FEAL-4 und FEAL-8, als gebrochen und sollte daher nicht eingesetzt werden.

Funktionsweise

Der Datenblock von 64 Bit besteht aus zwei Wörtern L_i und R_i zu je 32 Bit. Eine Feistelrunde besteht in der Auswertung der Rundenfunktion F (Bild) auf einem Wort und XOR-Verknüpfung des Ergebnisses mit dem anderen Wort und anschließender Vertauschung der Wörter:

$L_{i+1} \!\, = R_i$

$R_{i+1} \!\, = L_i \oplus F(R_i, K_i)$

Die Funktion F zerlegt das Wort R_i in vier Byte, die im Bild jeweils durch eine Linie symbolisiert werden, und erhält als Eingabe außerdem einen Rundenschlüssel K_i (2 Byte). Damit wird vier mal eine bitweise XOR-Verknüpfung von zwei Bytes angewandt, und je zweimal eine der Funktionen S₀ und S₁ ausgewertet, die zwei Eingabebytes auf ein Ausgabebyte abbilden. Sie addieren zunächst die beiden Eingabebytes modulo 256, und im Fall von S₁ wird dazu noch 1 addiert, wodurch das Zwischenergebnis h entsteht. Dieses wird um zwei Bitpositionen nach links rotiert:

$S_i(x,y) = (h \, \bmod \, 64) \cdot 4 + \lfloor h / 64 \rfloor ; \; h = (x+y+i) \, \bmod \, 256$

Die Chiffre verwendet außerdem Key Whitening vor der ersten und nach der letzten Runde.

Versionen

Ursprünglich wurde 1988 von dem Entwicklerteam um Akihiro Shimizu und Shoji Miyaguchi bei NTT FEAL-4 entwickelt. Dieser Algorithmus und seine Entstehungsgeschichte dokumentiert auch sehr anschaulich und mit teilweise amüsanten Abläufen die Problematik, die mit der Entwicklung sicherer Blockverschlüsselungsalgorithmen verbunden sein kann.

Damit der Algorithmus in Software einen möglichst hohen Durchsatz erzielt, war die Anzahl der Runden nur auf vier festgelegt. FEAL-4 wurde noch im gleichen Jahr 1988 auf der Eurocrypt '88 von B. den Boer gebrochen.^[1] Nur zwei Jahre später wurde von Sean Murphy die von ihm neu entwickelte differentielle Kryptoanalyse erfolgreich gegen FEAL-4 eingesetzt, wobei er nur 20 gewählte Klartextblöcke benötigte.^[2]

Die Entwickler verbesserten daraufhin im Jahr 1989 ihren Algorithmus, indem sie die Zahl der Runden auf acht erhöhten (FEAL-8). Dieser Algorithmus wurde ebenfalls im gleichen Jahr von Biham und Shamir auf der Konferenz SECURICOM '89 erfolgreich kryptoanalysiert.

Die Entwickler sahen sich daraufhin gezwungen, ihr Ziel, mit wenigen Runden eine effiziente Softwareimplementierung zu erreichen, endgültig aufzugeben, und veröffentlichten FEAL-N mit einer variablen Anzahl von Runden. Auf der SECURICOM '91 konnte wieder von Biham und Shamir gezeigt werden, das FEAL-N für weniger als 32 Runden effizienter als mit Brute-Force geknackt werden kann.

Die Entwickler von FEAL entwarfen parallel im Jahr 1990 auch FEAL-NX, eine Variante, die mit 128 Bit langen Schlüsseln statt der ursprünglich gewählten 64 Bit langen Schlüsseln arbeitete. Sehr zum Leidwesen der Entwickler wurde auf der SECURICOM '91 von Biham und Shamir gezeigt, dass FEAL-NX mit 128 Bit langen Schlüssel genauso leicht zu brechen ist wie FEAL-N mit 64 Bit langen Schlüsseln.^[3]

Darüber hinaus wurden von verschiedenen Entwicklungsteams Modifikationen zur Stärkung vorgeschlagen, wie FEAL-N(X)S, welche FEAL durch eine dynamische Vertauschungsfunktion stärken soll. Allerdings gehen alle diese Erweiterungen sehr zu Lasten des Datendurchsatzes.

FEAL wird vor allem zum Testen neuer und Verfeinern von kryptoanalytischen Angriffsmethoden verwendet. FEAL, egal in welcher Version, sollte wegen seiner bekannten Schwächen nicht in sicherheitskritischen Bereichen eingesetzt werden. FEAL war weiters in den USA patentiert, das Patent lief 2009 aus.

Referenzen

1. ↑ Bert den Boer: Cryptanalysis of F.E.A.L.. In: Lecture Notes in Computer Science. 330, 1988, S. 293-299. doi:10.1007/3-540-45961-8_27.
2. ↑ Sean Murphy: The cryptanalysis of FEAL-4 with 20 chosen plaintexts. (PDF) In: Journal of Cryptology. 2, Nr. 3, Januar 1990, S. 145-155. doi:10.1007/BF00190801.
3. ↑ Eli Biham, Adi Shamir: Differential cryptanalysis of DES-like cryptosystems. (PDF) In: Journal of Cryptology. 4, Nr. 1, Januar 1991, S. 3-72. doi:10.1.1.31.2000.