Path: illuminati.io.com!uunet!bloom-beacon.mit.edu!gatech!howland.reston.ans.
+     net!news.moneng.mei.com!uwm.edu!math.ohio-state.edu!scipio.cyberstore.
+     ca!skypoint.com!news3.mr.net!mr.net!winternet.com!news
From: schneier@klondike.winternet.com (Bruce Schneier)
Newsgroups: sci.crypt

Subject: Re: Generalized Feistel Networks
Date: 3 Apr 1995 05:51:13 GMT
Organization: StarNet Communications, Inc
Lines: 64
Message-ID: <3lo2ch$br8@blackice.winternet.com>
References: <3lndp5$nm4@cantaloupe.srv.cs.cmu.edu>
NNTP-Posting-Host: klondike.winternet.com

In article <3lndp5$nm4@cantaloupe.srv.cs.cmu.edu>,
Ralf Brown  wrote:

> 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' = f(A,B), for some invertible function f
> with the decryption transform for A',B' being
>    B = A'
>    A = f'(B,B'), where f' is the inverse of f

The key idea of a Feistel network is it turns a non-invertable one-way
function into an invertable block cipher.  Look at DES; what is usually
considered to be function f is everything but that final XOR.  A Feistel
network is really:

     A' = B
     B' = A XOR f(B)

That function f does not have to be invertable at all; the Feistel structure
takes care of the invertability.

> 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' = f(A,B)
>    C' = f(B,C)
>    D' = f(C,D)
> with decryption using
>    D = A'
>    C = f'(D,D')
>    B = f'(C,C')
>    A = f'(B,B')

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.

I believe there is something to our ideas, though, and am still working on
them.

Bruce

**************************************************************************
* Bruce Schneier
* Counterpane Systems         For a good prime, call 391581 * 2^216193 - 1
* schneier@counterpane.com
**************************************************************************