Path: illuminati.io.com!uunet!winternet.com!news
From: schneier@klondike.winternet.com (Bruce Schneier)
Newsgroups: sci.crypt

Subject: Re: Generalized Feistel Networks
Date: 4 Apr 1995 03:39:36 GMT
Organization: StarNet Communications, Inc
Lines: 49
Message-ID: <3lqf1o$8m0@blackice.winternet.com>
References: <3lndp5$nm4@cantaloupe.srv.cs.cmu.edu> <3lo2ch$br8@blackice.
+           winternet.com> <3lpin8$kp5@ixnews4.ix.netcom.com>
NNTP-Posting-Host: klondike.winternet.com

In article <3lpin8$kp5@ixnews4.ix.netcom.com>,
John Lull  wrote:
>Bruce Schneier writes: 
>
>>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.
>
>This looks an awful lot like HAVAL, except HAVAL uses 8 sub-blocks with
>7 of them (plus one sub-block of "key") going into calculation of f().

This is something I noticed.  SHA is an unbalanced Feistel Network: 64 bits
operate on 16 bits in each round.  (Actually, you can look at SHA as a block
function turned into a hash function with a Davies-Meyers-like feedforward
function.)  Haval has a similar construction, as do (more or less) MD4 and 
MD5.

>>We presented our strawman construction, MacGuffin, at the Leuven Algorithms
>>Workshop last December, and it was immediately broken.
>
>Details? Was the attack based on your structure, choce of f(), or some
>other factor? Would this attack be relevant in any way to an attack on
>HAVAL, either used as a hash, or with its core used as a block cipher?

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.

Bruce

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