Personal tools

feal-algorithm.txt

In article <C7JMFG.BoG@vcd.hp.com>
egurney@vcd.hp.com (Ed J. Gurney) writes:

>Can anyone recommend any sources on FEAL encryption? Is it a secure
>encryption scheme, or has it been "compromised"? I've checked archie
>for 'FEAL' and didn't find anything useful. I'd appreciate any
>references on how the method works, its overall security, etc.

FEAL is a feistel-type cipher designed in Japan. I don't have the
references in front of me, but I can tell you a bit:

FEAL is a feistel-type cipher, like DES. This means that the input
block is split into a left and right half, then each round of encryption
calculates some nonlinear function of the right half and part of the key,
XORs it into the left half, and swaps the right and left half. The non-
linear function in FEAL depends on addition of 8-bit numbers mod 256, which
isn't all that strong.

One round of a Feistel-type cipher:

L = L XOR F(R,K_i)
SWAP L,R

The original FEAL has a 64-bit key. Biham and Shamir wrote in Crypto 90
that FEAL with less than 32 rounds is breakable by differential cryptanalysis
faster than a brute-force keysearch. They detail an attack on FEAL in
Eurocrypt '91. There is also a statistical attack on FEAL-8 in Crypto 90,
which seemed to be strongly related to differential cryptannalytic techniques,
but I haven't read the article just yet.

There is an extended version of FEAL called FEAL-NX (N = # of rounds).
Biham and Shamir wrote that it was no harder to break that FEAL-N.

--John Kelsey, c445585@mizzou1.missouri.edu

From: Mike Barney <mike_barney@email.mot.com>

the "author" of FEAL is Shoji Miyaguchi at NTT in Japan. I don't have an
email for him, but his voice and fax at NTT in Japan are:
Tele 81 468 59 3377
Fax 81 468 59 3858 (Usually prefered to Japan because of time delta)
FEAL started as a SW based algorithm and has been "strengthened" by
adding additional rounds ("FEAL-8, FEAL-16...) At least at Crypto91 they
had a prize (small) out for any successfut attack for (I think) Feal 16,
but I don't think anyone collected, and there wern't any major
announcements at that time that someone was taking them up on their
challenge. There was allegedly a FEAL chip comming out a year ago, but I
don't know the latest. Anybody?
Hope this helps.

egurney@vcd.hp.com (Ed J. Gurney)
Mike Barney
Motorola Secure Telecommunications
Voice: (602) 441-2205
Fax: (602) 441-8377
email: mike_barney@email.mot.com

From: C445585@mizzou1.missouri.edu (John Kelsey)
Subject: Re: Information on FEAL encryption?
Date: Tue, 25 May 93 23:38:34 CDT

I beleive the prize for breaking FEAL was for demonstrating a method for
breaking it given a fairly small number of known plaintexts (in ECB mode)
or chosen plaintexts (in CBC mode). I never heard whether anyone broke it.
The differential method Biham and Shamir worked out requires encryption of
chosen plaintexts (or really, really large numbers of known-plaintexts with
a somewhat random distribution), so I don't know whether this prize was ever
collected.

I'd guess that FEAL has shown a "certificational weakness," in that the
published attacks, while possibly not practical as shown, imply weaknesses
in the algorithm that may make other attacks too easy.

The only nonlinearity in the FEAL-NX algorithms is in the S0 and S1
boxes. Both are 16-bit to 8-bit substitutions based on modulo 256 addition
and bit rotation. This is the weakness that allowed the attacks that have
been published, I think.

I wonder if there's some way of measuring, for a given F function, how
many rounds in a Feistel transformation are necessary to eliminate any
weaknesses. Clearly, IBM, NSA, or someone knew enough about differential
cryptanalysis or some closely-related technique to choose just the right
number of rounds, just the right S-box criteria (?), etc. It seems like
there should be a way of determining that the output block from the nth
round really, really contains no usable patterns, but then, someone can
still sometimes find some special input values (or input value differences)
for which some pattern emerges. Hrmmmmm.....

--John Kelsey, c445585@mizzou1.missouri.edu

From: ahaley@eoe.co.uk (Andrew Haley)
Date: 26 May 93 09:48:24 GMT

John Kelsey (C445585@mizzou1.missouri.edu) wrote:
: FEAL is a feistel-type cipher designed in Japan. I don't have the
: references in front of me, but I can tell you a bit:

FEAL-NX specification:

Function S

Sd(X1,X2) = Rot2(T)
T=X1+X2+d mod 256; d is 0 or 1
Rot2 is a left rotate by two bits

Function fk

fk is passed two four byte blocks, a and b

fk1 = a1 xor a0
fk2 = a2 xor a3
fk1 = S1(fk1,(fk2 xor b0))
fk2 = S0(fk2,(fk1 xor b1))
fk0 = S0(a0,(fk1 xor b2))
fk3 = S1(a3,(fk2 xor b3))

Function f

f is passed two four byte blocks, a and b

f1 = a1 xor b0 xor a0
f2 = a2 xor b1 xor a3
f1 = S1(f1,f2)
f2 = S0(f2,f1)
f0 = S0(a0,f1)
f3 = S1(a3,f2)

Key processing

The 128 bit key is split into two halves K[L] and K[R]. If K[R] is
all zeroes, the encryption is equivalent to the earlier version of
FEAL which had a 64-bit key.

1. Processing of K[R].

KR is divided into the left half K[R1] and the right half K[R2].

Q[r] is defined as

Q[r] = K[R1] xor K[R2] for r = 1,4,7,...,
( r = 3*i + 1; i = 0,1,...)
Q[r] = K[R1] for r = 2,5,8,...,
( r = 3*i + 2; i = 0,1,...)
Q[r] = K[R2] for r = 3,6,9,...,
( r = 3*i + 3; i = 0,1,...)

Where 1 <= r <= (N/2)+4. (N >= 4, N:even)

2. Processing of K[L]

A[0] and B[0] are two four byte blocks. K[L] is the
concatenation of these two blocks. K[n] is an array of N+8 two
byte words.

D0 = 00000000 (four bytes)

for i = 0 to N+7 do begin
D[r] := A[r-1]
A[r] := B[r-1]
B[r] := fk(A[r-1],B[r-1] xor D[r-1] xor Q[r])
K[2*(r-1)] := (B[r[0]], B[r[1]])
K[2*(r-1)+1] := (B[r[2]], B[r[3]])
end

Enciphering procedure

The plaintext (8 bytes) is separated into L[0] and R[0] of four
bytes each.

(R[N],L[N]) := (R[N],L[N]) xor (K[N],K[N+1],K[N+2],K[N+3])
R[0] := R[0] xor L[0]

for r = 1 to N do begin
R[r] := L[r-1] xor f( R[r-1], K[r-1] )
L[r] := R[r-1]
end

(L[N],R[N]) := (R[N],L[N])
L[N] := L[N] xor R[N]

(R[N],L[N]) := (R[N],L[N]) xor (K[N+4],K[N+5],K[N+6],K[N+7])

Ciphertext is (R[N],L[N])

Deciphering procedure

The ciphertext (R[N],L[N]) (8 bytes) is separated into R[8] and
L[8] of four bytes each.

(R[N],L[N]) := (R[N],L[N]) xor (K[N+4],K[N+5],K[N+6],K[N+7])
L[N] := L[N] xor R[N]

for r = N to 1 do begin
L[r-1] := R[r] xor f( L[r], K[r-1] )
R[r-1] := L[r-1]
end

R[0] := R[0] xor L[0]
(R[N],L[N]) := (R[N],L[N]) xor (K[N],K[N+1],K[N+2],K[N+3])

The plaintext is (L[0],R[0]).

:
: FEAL is a feistel-type cipher, like DES. This means that the input
: block is split into a left and right half, then each round of encryption
: calculates some nonlinear function of the right half and part of the key,
: XORs it into the left half, and swaps the right and left half. The non-
: linear function in FEAL depends on addition of 8-bit numbers mod 256, which
: isn't all that strong.
:
: One round of a Feistel-type cipher:
:
: L = L XOR F(R,K_i)
: SWAP L,R
:
: The original FEAL has a 64-bit key. Biham and Shamir wrote in Crypto 90
: that FEAL with less than 32 rounds is breakable by differential cryptanalysis
: faster than a brute-force keysearch. They detail an attack on FEAL in
: Eurocrypt '91. There is also a statistical attack on FEAL-8 in Crypto 90,
: which seemed to be strongly related to differential cryptannalytic techniques,
: but I haven't read the article just yet.
:
: There is an extended version of FEAL called FEAL-NX (N = # of rounds).
: Biham and Shamir wrote that it was no harder to break that FEAL-N.
:
: --John Kelsey, c445585@mizzou1.missouri.edu

From: ahaley@eoe.co.uk (Andrew Haley)
Subject: Re: Information on FEAL encryption?
Date: 28 May 93 09:25:46 GMT
Organization: EO Europe Limited, Cambridge, UK

John Kelsey (C445585@mizzou1.missouri.edu) wrote:

: Reference: "The FEAL Cipher Family," in the Rump Session of the
: procedings of Crypto '90. Written by Shoji Miyaguchi.
:
: The author contends that a chosen plaintext attack can be defeated by
: use of CBC mode. However, I don't see that this is really true. If I
: know the plaintext of one encrypted transmission with a given key, I should
: be able to retrieve known plaintext-ciphertext pairs from the encryption
: function. Then, I should be able to use those to choose a second set of
: chosen plaintexts that will give me the desired input values to the
: encryption function. All I need is the IV, which is (I think) usually
: transmitted with the message in the clear. (What am I missing?)
:
: --John Kelsey, c445585@mizzou1.missouri.edu

As the IV is randomly generated for every message, you can never have
any control on what the encryption function itself sees. In fact,
even if you could control the IV you would only be able to supply a
single block of chosen test.

Andrew.

Archived CPSR Information
Created before October 2004
Announcements

Sign up for CPSR announcements emails

Chapters

International Chapters -

> Canada
> Japan
> Peru
> Spain
          more...

USA Chapters -

> Chicago, IL
> Pittsburgh, PA
> San Francisco Bay Area
> Seattle, WA
more...
Why did you join CPSR?

It is important for knowledgeable professionals to influence technology policy. Legislators and regulators are too often unfamiliar with the fields they control and are insufficiently aware of the consequences of their actions.