Newsgroups: sci.crypt
Path: cactus.org!ritter
From: ritter@cactus.org (Terry Ritter)

Subject: Re: Block Mixing Transformations
Message-ID: <1994Mar15.194249.28915@cactus.org>
Keywords: DES replacement, Large blocks
Organization: Capital Area Central Texas UNIX Society, Austin, Tx
References: <1994Mar13.051515.27175@cactus.org> <1994Mar15.124011.
+           19463@mnemosyne.cs.du.edu>
Date: Tue, 15 Mar 1994 19:42:49 GMT


 In <1994Mar15.124011.19463@mnemosyne.cs.du.edu> colin@nyx10.cs.du.edu
 (Colin Plumb) writes:


>T is A^B, which is the same as X^Y.  The high bit is
>highly visible.

 Yup.  I had not seen it.


>And I observed that half the bits of the input are trivially derivable
>from the output (A^B = X^Y), and the other half are also trivially derivable
>half the time (and you know which half!), and almost as easy the other
>half of the time.

 Yes.  They are much weaker even than I had thought.


>> In many (most?) cases A and B should already be randomized by the
>> time they get to the mixer being attacked.  Without "exploitable
>> patterns," finding p will get a whole lot trickier.
>
>If that's the case, almost any mixing pattern will suffice.

 OK, let's see some alternatives.

 Then we can itemize their strengths and weaknesses and put them
 in a design catalog.


>My observation about the extremely high degree of linearity in the
>operation was that anything made up only of these mixing operations
>is weak.  I'm not sure the above is more trustworthy than the
>substitutions.

 Fine by me.  96 8-bit substitutions means 256!^96 keys.

 (Obviously we initialize this state by shuffling with a
 cryptographic RNG, but we can make that RNG just as large as we
 want and seed it with all the key material we want.)

 Just the 32 substitutions in the middle would be more than secure,
 *provided* all the stuff around them spread their effects and
 prevented them from being attacked separately.

 All we need the mixings to do is to mix.  Essentially, we want to
 end up with the effect of a bit change in any particular position
 being spread among the entire output (statistically), after a set
 of mixings.  If this can be accomplished, we can use small,
 practical substitutions to make a large-block cipher.

 ---
 Terry Ritter   ritter@cactus.org (cactus.org dies on the 18th)
                ritter@rts.com
                ritter@io.com  (perhaps temporarily)