A number of European encryption programs are based on the Japanese FEAL
algorithm.  FEAL is a 64-bit block cipher with a 64-bit key, with later
modifications increasing the key size.  Different versions of FEAL have been
broken almost every year since its introduction.  The original version of FEAL
was quickly broken.  A modified version, FEAL-4, was broken by Bert den Boer
in "Cryptanalysis of FEAL", Advances in Cryptology - Eurocrypt'88 Proceedings,
and completely demolished by Sean Murphy in "The Cryptanalysis of FEAL-4 with
20 Chosen Plaintexts", Journal of Cryptology Vol.2, No.3, 1990.

The designers response was FEAL-8.  The first successful attack was announced
by Biham and Shamir at Securicom '89, with another attack using 10,000 chosen
plaintexts being announced by Gilbert and Chasse, "A statistical attack on the
FEAL-8 cryptosystem", Advances in Cryptology - Crypto '90 Proceedings.

The designers responded with another modification, FEAL-N and FEAL-NX, with
the 'N' being a placeholder for a variable number of rounds, and the 'X'
denoting the use of a longer key.  Biham and Shamir showed in "Differential
cryptanalysis of FEAL and N-Hash", Advances in Cryptology - Eurocrypt'91
Proceedings, Springer-Verlag, 1991, that they could break FEAL-N with up to 32
rounds more quickly than by using a brute-force search. FEAL-16 required 2^28
chosen plaintexts, FEAL-8 required 2000 chosen plaintexts, and FEAL-4 required
a mere 5 chosen plaintexts.  They also showed that FEAL-NX with its extended
128-bit key was just as easy to break as FEAL-N with its 64-bit key.  In
"Differential Cryptanalysis of Hash Functions Based on Block Ciphers", ACM
Conference on Computer and Communications Security, 1993, Bart Preneel, Rene'
Govaerts, and Joos Vandewalle demonstrate a differential attack which leads to
collisions in FEAL-N with N up to 16.

The succession of attacks on FEAL continued.  At Crypto'91, Tardy-Corfdir and
Gilbert had another go at FEAL with "A known-plaintext attack of FEAL-4 and
FEAL-6", breaking FEAL-4 with 1000 known plaintexts and FEAL-6 with 20,000
known plaintexts.  Another attack, by Mitsuru Matsui and Yamagishi, "A New
Method for Known Plaintext Attack of FEAL cipher", Advances in Cryptology -
Eurocrypt'92, Springer-Verlag, 1993, breaks FEAL-4 with 5 known plaintexts,
FEAL-6 with 100 known plaintexts, and FEAL-8 with 2^15 known plaintexts.  This
was later improved upon by Eli Biham in "On Matsui's Linear Cryptanalysis",
Proceedings of Eurocrypt'94, Springer-Verlag, 1994 with a known-plaintext
attack on FEAL-8.  Yet another attack, by Toshinobu Kaneko, "A Known-Paintext
Attack of FEAL-4 based on the System of Linear Equations on Difference",
Proceedings of Asiacrypt'91, Springer-Verlag, 1992, breaks FEAL-4 with 24
known plaintexts in a few seconds on a low-end PC.  A discussion on the cost
of Matsui's vs Kaneko's attack on FEAL is given in Kaneko and Masuda's "On the
Relation of Matsuis Method and Differential Equation Method for FEAL",
Symposium on Cryptography and Information Security, 1994.  Biham and Shamir,
in "Differential Cryptanalysis of the Data Encryption Standard",
Springer-Verlag, 1993, report that it takes only 128 chosen plaintexts to
break FEAL-8, and that the designers latest versions, FEAL-N and FEAL-NX, can
be broken using differential cryptanalysis with up to 31 rounds. In
"Differential Attack on Message Authentication Codes", Kazuo Ohta and Mitsuru
Matsui, Advances in Cryptology - Crypto'93, Springer-Verlag, 1994, both 8 and
12-round FEAL MAC's are shown to be insecure.  Yukiyasu Tsunoo, Eiji Okamoto,
and Tomohiko Uyematsu, in "Ciphertext-Only Attack for One-way Function of the
MAP by Using One Ciphertext", Symposium on Cryptography and Information
Security, 1994, demonstrate an attack on MAP, a supposedly one-way function
based on FEAL-4, which takes 15.7 hours on a SparcStation 2.  In "Linear
Cryptanalysis of the Fast Data Encipherment Algorithm", Kazuo Ohta and
Kazumaro Aoki, Advances in Cryptology - Crypto'94, Springer-Verlag, 1994, an
attack on FEAL-8 requiring 2^25 known plaintexts and taking about an hour on
an inexpensive workstation is described.

In any case the most commonly-used 8-round version of FEAL is not secure, with
even a singly moderately-sized file containing enough information to allow it
to be broken.  FEAL's main claim to fame is that it provided a very fertile
testing ground for attacks on block ciphers.

[If I've missed any attacks or papers, please let me know]

Peter.