From: C445585@mizzou1.missouri.edu (John Kelsey) Subject: Re: Information on FEAL encryption? Organization: University of Missouri Date: Tue, 25 May 93 16:04:21 CDT In article 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 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.