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 , 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.