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 Brownwrote: > 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 **************************************************************************