FEAL

FEAL
	The round function F from FEAL
developer	Akihiro Shimizu and Shoji Miyaguchi, both from NTT
Released	FEAL-4 1987; FEAL-N / NX 1990
Key length	64 bits (FEAL), 128 bits (FEAL-NX)
Block size	64 bit
structure	Feistel cipher
Round	Originally 4 at FEAL-4, then expanded to 8 rounds; FEAL-N / NX with variable number of laps, with a minimum of 32 recommended.
Best known cryptanalysis
	FEAL-4 is very susceptible to linear cryptanalysis with only five known plaintext blocks . (Matsui and Yamagishi, 1992). ; FEAL-N / NX is susceptible to differential cryptanalysis with less than 31 rounds. (Biham and Shamir, 1991).

FEAL ( F ast Data E ncipherment Al gorithm ) is a block cipher and one of the symmetrical Feistelchiffren . The aim of the development, which originated from the Japanese telephone company Nippon Telegraph and Telephone (NTT), was to achieve an efficient implementation of an encryption algorithm in software, even for small microcontrollers , and thus an alternative to the Data Encryption Standard (DES ) to accomplish. DES can only be implemented comparatively inefficiently in software.

In the years after its development in 1987, FEAL was primarily used as a test object for various attack scenarios on encryption algorithms. In particular, it served to advance the development of today's essential analysis methods, differential cryptanalysis and linear cryptanalysis . FEAL itself, in the original versions such as FEAL-4 and FEAL-8, is considered broken and should therefore not be used.

functionality

The data block of 64 bits is composed of two words and each 32 bits. A Feistel round consists of evaluating the round function F (image) on one word and XORing the result with the other word and then swapping the words: ${\ displaystyle L_ {i}}$ ${\ displaystyle R_ {i}}$

{\ displaystyle L_ {i + 1} \! \, = R_ {i}}

{\ displaystyle R_ {i + 1} \! \, = L_ {i} \ oplus F (R_ {i}, K_ {i})}

The function F divides the word into four bytes , each symbolized by a line in the picture, and also receives a round key (2 bytes) as input . This means that four times a bit-wise XOR operation of two bytes is used, and one of the functions and is evaluated twice , which map two input bytes to one output byte. You first add the two input bytes modulo , and in the case of 1 is added to this, resulting in the intermediate result h . This is rotated to the left by two bit positions: ${\ displaystyle R_ {i}}$ ${\ displaystyle K_ {i}}$ ${\ displaystyle S_ {0}}$ ${\ displaystyle S_ {1}}$ ${\ displaystyle 256}$ ${\ displaystyle S_ {1}}$

{\ displaystyle S_ {i} (x, y) = (h \, {\ bmod {\,}} 64) \ cdot 4+ \ lfloor h / 64 \ rfloor; \; h = (x + y + i) \, {\ bmod {\,}} 256}

The cipher also uses key whitening before the first and after the last round.

Versions

FEAL-4 was originally developed in 1988 by Akihiro Shimizu and Shoji Miyaguchi's development team at NTT. This algorithm and the history of its origins also document very clearly and with sometimes amusing processes the problems that can be associated with the development of secure block encryption algorithms.

In order for the algorithm to achieve the highest possible throughput in software, the number of rounds was only set to four. FEAL-4 was broken in the same year 1988 on the Eurocrypt '88 by B. den Boer. Just two years later, Sean Murphy successfully used his newly developed differential cryptanalysis against FEAL-4, requiring only 20 selected plaintext blocks.

The developers then improved their algorithm in 1989 by increasing the number of rounds to eight (FEAL-8). This algorithm was also successfully crypto-analyzed by Biham and Shamir at the SECURICOM '89 conference in the same year .

The developers were then forced to finally give up their goal of achieving an efficient software implementation with just a few rounds, and published FEAL-N with a variable number of rounds. At SECURICOM '91 , Biham and Shamir again showed that FEAL-N can be cracked more efficiently for less than 32 rounds than with brute force.

The FEAL developers also designed FEAL-NX in 1990, a variant that worked with 128-bit keys instead of the 64-bit keys originally selected. Much to the chagrin of the developers, Biham and Shamir showed at SECURICOM '91 that FEAL-NX with a 128-bit key is just as easy to break as FEAL-N with a 64-bit key.

In addition, various development teams suggested modifications for strengthening, such as FEAL-N (X) S, which should strengthen FEAL through a dynamic interchangeability function. However, all of these extensions are at the expense of data throughput.

FEAL is mainly used to test new and refine cryptanalytic attack methods. FEAL, regardless of the version, should not be used in security-critical areas because of its known weaknesses. FEAL was patented in the USA, the patent expired in 2009.

credentials

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

[boer-1] Bert den Boer: Cryptanalysis of FEAL . In: Lecture Notes in Computer Science . 330, 1988, pp. 293-299. doi : 10.1007 / 3-540-45961-8_27 .

[murphy-2] Sean Murphy: The cryptanalysis of FEAL-4 with 20 chosen plaintexts . (PDF) In: Journal of Cryptology . 2, No. 3, January 1990, pp. 145-155. doi : 10.1007 / BF00190801 .

[biham-3] Eli Biham, Adi Shamir: Differential cryptanalysis of DES-like cryptosystems . (PDF) In: Journal of Cryptology . 4, No. 1, January 1991, pp. 3-72. doi : 10.1007 / BF00630563 .