From: ralf+@cs.cmu.edu (Ralf Brown)
Subject: Generalized Feistel Networks
Date: 2 Apr 1995 23:59:33 GMT

[I posted the original version of the following to sci.crypt at the
beginning of April.  The below includes some fixes plus summaries of the
various comments it elicited.  I had originally used an invertible
two-argument function rather than XOR with a possibly-noninvertible
one-argument function (which is in fact a special case of the former).
A separate article containing some additional ideas will follow.]

As many of you know, Feistel ciphers are based on repeated iterations
("rounds") of the following for the two halves A and B of a block of some
predetermined size:
        A' = B
	B' = A xor f(B), f usually having part of the key as hidden arg
with the decryption transform for A',B' being
        B = A'
	A = B' xor f(B)

This idea can be generalized to the N parts of a block (said block naturally
being larger than in the N=2 case normally used).  For instance, if N=4,
then the subblocks A,B,C,D of a block would be transformed as follows for
encryption:
	A' = D
	B' = A xor f(B)
	C' = B xor f(C)
	D' = C xor f(D)
with decryption using
	D = A'
	C = D' xor f(D)
	B = C' xor f(C)
	A = B' xor f(B)

For N subblocks in a block, a minimum of N rounds are required to process
each subblock uniformly through the network, at which point every subblock
of the output depends on every subblock of the input.

Although this approach roughly doubles computation compared to the standard
Feistel network (a total of M*(N-1) applications of the mixing function for
N parts processed through M rounds, compared to M*(N/2) applications), it
also diffuses the bits over a much larger block--where a 32-bit processor
would have used a 64-bit block, it could now use a 512-bit block with 16
rounds.  (One respondent questioned the need for large blocks, but there
are some applications where large blocks are natural, such as sector-level
disk encryption.)

We can further generalize by using multiple mixing functions--there
could be up to N-1 distinct mixing functions applied in each round, and
the invertible top-level operation need not be XOR for all of the
functions (rotation, modulare addition, or group multiplication could
be used instead).  This will naturally require careful design to avoid
sets of functions which neutralize each other.

---------

From: straits@crash.cts.com (Stewart Strait)

If the mixing functions are linear, we get a simple form of
the Hill System, i.e.  ciphertext vector=key matrix *
plaintext vector, since every invertible matrix is a product
of matrix representations of elementary row operations. The
Hill System is not secure (at all!) against known plaintext
attack, but it's interesting that it is Feistel-like.

---------

From: schneier@klondike.winternet.com (Bruce Schneier)

Matt Blaze and I also tried to generalize the Feistel construction, but
in such a way as to preserve the use of a noninvertable function f.  The
way we did it is to, in each round, break the block into two unequal halves.

A construction using four subblocks might be:

     A' = D
     B' = A
     C' = B
     D' = C XOR f(A,B,D)

The downside is that only one quarter of the bits get encrypted in each round.
The upside is that more bits go into the encryption.

We presented our strawman construction, MacGuffin, at the Leuven Algorithms
Workshop last December, and it was immediately broken.

[And, responding to a query by John Lull <windsmit@ix.netcom.com>, who
also noted that Bruce's construction looked a lot like HAVAL:]
The attack was based on our choice of f, which was ripped out of DES with
little thought about how the changes might affect it; the attack didn't
hve anything to do with the structure.  

Springer-Verlag will be publishing the papers from the Leuven Workshop sometime
soon (as they published the papers from the Cambridge Workshop the previous
year) and both our paper and the attack are included.