FEAL-8 algorithm

430 views
Skip to first unread message

Frank Tuuksam

unread,
Oct 18, 1996, 3:00:00 AM10/18/96
to

I saw an ad in our computer press here, in Estonia praising the FEAL-8
algorithm, supposedly Japanese.

It's supposedly a public algorithm and very fast.

Could someone please comment on its strengths and weaknesses.

Yours,
Frank

Vaughn Herbert Seward

unread,
Oct 18, 1996, 3:00:00 AM10/18/96
to

In <3266C1...@bpro.estnet.ee> Frank Tuuksam <fr...@bpro.estnet.ee>
writes:

The FEAL-8 algorithm was developed in Japan.

It's public, in the sense of not being secret, but it _is_ patented. As
for its strength, I don't have my copy of Schneier at my elbow, but I
believe it is adequately strong, although it had some weakness, in
reduced-round versions, against differential and linear cryptanalysis.
These attacks are mostly relevant if you're encrypting text for other
people, from whom you still wish to keep the key secret.

John Savard


Bryan Olson

unread,
Oct 18, 1996, 3:00:00 AM10/18/96
to

Vaughn Herbert Seward wrote:
>
> In <3266C1...@bpro.estnet.ee> Frank Tuuksam <fr...@bpro.estnet.ee>
> writes:
> >I saw an ad in our computer press here, in Estonia praising the FEAL-8
> >algorithm,

[...]


> for its strength, I don't have my copy of Schneier at my elbow, but I
> believe it is adequately strong, although it had some weakness, in

[...]

First there was just FEAL, (now known as FEAL-4) which was
presented at Eurocrypt 87 (I think). The designers had some
statistic that they claimed came out better than DES, and
they reasoned FEAL was secure.

It was quickly broken (Boer, Eurocrypt 88), and the designers
came back with FEAL-8. FEAL-8 fell to Biam & Shamir. The
designers offered FEAL N, against which there are various
cryptanalytic results.

The main importance of the FEAL algorithms is that they
provid some good targets to hone attacks against block
ciphers. I'd recommend against using them for anything else.

--Bryan

Brollo

unread,
Oct 18, 1996, 3:00:00 AM10/18/96
to

In <3266C1...@bpro.estnet.ee> Frank Tuuksam <fr...@bpro.estnet.ee>
writes:
>
>I saw an ad in our computer press here, in Estonia praising the FEAL-8
>algorithm, supposedly Japanese.
>It's supposedly a public algorithm and very fast.
>Could someone please comment on its strengths and weaknesses.

I do have Bruce Schneier at my hand, and the verdict on Feal is not
good. Feal-4 was successfully cryptanalyzed iwth chosen plaintext attack
(Eurocrypt '88) and then demolished in '90. Similar comment for Feal-8
then Feal-N (above 8) broken by Biham and Shamir (again with chosen
plaintext) finally Feal-N(X)S was proposed. Though the cryptanalysis
requires either chosen plaintext or known plaintext, the results are not
encouraging. Bruce goes on to say that "Whenever anyone discovers a new
cryptanalytic attack, he always seems to try it out on Feal first", with
apparent good success as far as these results show.

Peter Gutmann

unread,
Oct 21, 1996, 3:00:00 AM10/21/96
to

Frank Tuuksam <fr...@bpro.estnet.ee> writes:

>I saw an ad in our computer press here, in Estonia praising the FEAL-8
>algorithm, supposedly Japanese.

>It's supposedly a public algorithm and very fast.

>Could someone please comment on its strengths and weaknesses.

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.

Reply all
Reply to author
Forward
0 new messages