Editing FEAL

{{Short description|Block cipher}}
{{More footnotes|date=September 2015}}
{{Infobox block cipher
| name          = FEAL
| image         = [[Image:FEAL InfoBox Diagram.png|300px|center]]
| caption       = The FEAL Feistel function
| designers     = Akihiro Shimizu and Shoji Miyaguchi (NTT)
| publish date  = FEAL-4 in 1987; FEAL-N/NX in 1990
| derived from  = 
| derived to    = 
| key size      = 64 bits (FEAL), 128 bits (FEAL-NX)
| block size    = 64 bits
| structure     = [[Feistel network]]
| rounds        = Originally 4, then 8, then variable (recommended 32)
| cryptanalysis = [[Linear cryptanalysis]] can break FEAL-4 with 5 [[known plaintext]]s (Matsui and Yamagishi, 1992). A [[differential attack]] breaks FEAL-N/NX with fewer than 31 rounds (Biham and Shamir, 1991).
}}

In [[cryptography]], '''FEAL''' (the '''Fast data Encipherment Algorithm''') is a [[block cipher]] proposed as an alternative to the [[Data Encryption Standard]] (DES), and designed to be much faster in software. The [[Feistel cipher|Feistel]] based algorithm was first published in 1987 by [[Akihiro Shimizu]] and [[Shoji Miyaguchi]] from [[Nippon Telegraph and Telephone|NTT]]. The cipher is susceptible to various forms of [[cryptanalysis]], and has acted as a catalyst in the discovery of [[differential cryptanalysis|differential]] and [[linear cryptanalysis]].

There have been several different revisions of FEAL, though all are [[Feistel cipher]]s, and make use of the same basic round function and operate on a [[block size (cryptography)|64-bit block]]. One of the earliest designs is now termed '''FEAL-4''', which has four rounds and a [[key (cryptography)|64-bit key]]. 
<!-- den Boer refers to an earlier FEAL-1 and FEAL-2, and Gutmann also mentions pre-FEAL-4 versions, but info on these is hard to find, and they aren't significant, really -->

Problems were found with FEAL-4 from the start: Bert den Boer related a weakness in an unpublished rump session at the same conference where the cipher was first presented. A later paper (den Boer, 1988) describes an attack requiring 100&ndash;10000 [[chosen plaintext]]s, and Sean Murphy (1990) found an improvement that needs only 20 chosen plaintexts. Murphy and den Boer's methods contain elements similar to those used in [[differential cryptanalysis]].

The designers countered by doubling the number of rounds, '''FEAL-8''' (Shimizu and Miyaguchi, 1988). However, eight rounds also proved to be insufficient &mdash; in 1989, at the Securicom conference, [[Eli Biham]] and [[Adi Shamir]] described a differential attack on the cipher, mentioned in (Miyaguchi, 1989). Gilbert and Chassé (1990) subsequently published a statistical attack similar to differential cryptanalysis which requires 10000 pairs of chosen plaintexts.

In response, the designers introduced a variable-round cipher, '''FEAL-N''' (Miyaguchi, 1990), where "N" was chosen by the user, together with '''FEAL-NX''', which had a larger 128-bit key. Biham and Shamir's differential cryptanalysis (1991) showed that both FEAL-N and FEAL-NX could be broken faster than exhaustive search for N ≤ 31. Later attacks, precursors to linear cryptanalysis, could break versions under the [[known plaintext]] assumption, first (Tardy-Corfdir and Gilbert, 1991) and then (Matsui and Yamagishi, 1992), the latter breaking FEAL-4 with 5 known plaintexts, FEAL-6 with 100, and FEAL-8 with 2<sup>15</sup>.

In 1994, Ohta and Aoki presented a linear cryptanalytic attack against FEAL-8 that required 2<sup>12</sup> known plaintexts.<ref>{{cite web|url=http://x5.net/faqs/crypto/q79.html |title=Q79: What is FEAL? |publisher=X5.net |access-date=2013-02-19}}</ref>

==See also==
* [[N-Hash]]

==Notes==
{{reflist}}

==References==
* Eli Biham, Adi Shamir: Differential Cryptanalysis of Feal and N-Hash. EUROCRYPT 1991: 1&ndash;16
* Bert den Boer, Cryptanalysis of F.E.A.L., EUROCRYPT 1988: 293&ndash;299
* Henri Gilbert, Guy Chassé: A Statistical Attack of the FEAL-8 Cryptosystem. CRYPTO 1990: 22&ndash;33.
* Shoji Miyaguchi: The FEAL Cipher Family. CRYPTO 1990: 627&ndash;638
* Shoji Miyaguchi: The FEAL-8 Cryptosystem and a Call for Attack. CRYPTO 1989: 624&ndash;627
* Mitsuru Matsui, Atsuhiro Yamagishi: A New Method for Known Plaintext Attack of FEAL Cipher. EUROCRYPT 1992: 81&ndash;91
* Sean Murphy, The Cryptanalysis of FEAL-4 with 20 Chosen Plaintexts. ''J. Cryptology'' '''2'''(3): 145&ndash;154 (1990)
* A. Shimizu and S. Miyaguchi, Fast data encipherment algorithm FEAL, Advances in Cryptology &mdash; Eurocrypt '87, Springer-Verlag (1988), 267&ndash;280.
* Anne Tardy-Corfdir, Henri Gilbert: A Known Plaintext Attack of FEAL-4 and FEAL-6. CRYPTO 1991: 172&ndash;181

==External links==
* [http://info.isl.ntt.co.jp/crypt/eng/archive/index.html#feal The FEAL home page]
* [https://groups.google.com/groups?selm=54gq4q%242d7%40scream.auckland.ac.nz A sci.crypt article by Peter Gutmann describing FEAL]
*[http://patft.uspto.gov/netacgi/nph-Parser?TERM1=4850019&u=/netahtml/srchnum.htm&Sect1=PTO1&Sect2=HITOFF&p=1&r=0&l=50&f=S&d=PALL US patent 4850019] {{Webarchive|url=https://web.archive.org/web/20160409112249/http://patft.uspto.gov/netacgi/nph-Parser?TERM1=4850019&u=/netahtml/srchnum.htm&Sect1=PTO1&Sect2=HITOFF&p=1&r=0&l=50&f=S&d=PALL |date=2016-04-09 }}

{{Cryptography navbox | block}}

[[Category:Broken block ciphers]]
[[Category:Feistel ciphers]]