Path: bga.com!news.sprintlink.net!hookup!yeshua.marcam.com!MathWorks.Com!
+     zombie.ncsc.mil!golf!mizzou1.missouri.edu!C445585
From: C445585@mizzou1.missouri.edu
Newsgroups: sci.crypt

Subject: Re: Block Mixing Transformations
Date: Fri, 18 Mar 94 19:39:48 CST
Organization: University of Missouri, Columbia
Lines: 47
Message-ID: <16F7D11487S86.C445585@mizzou1.missouri.edu>
References: <1994Mar13.051515.27175@cactus.org> <1994Mar14.223702.
+           6452@mnemosyne.cs.du.edu> <1994Mar15.065615.3895@cactus.org>
NNTP-Posting-Host: mizzou1.missouri.edu

In article <1994Mar15.065615.3895@cactus.org>
ritter@cactus.org (Terry Ritter) writes:
 
> If we use the simple mixer we have 4 * 128 = 512; with the IDEA-type
> mixer, we have a cost of 2 * 2 * (128)^2 or 65,536; approximately
> 128 times the cost of the simple approach.
>
> Is the version with the IDEA-type mixer stronger?  Probably.  But
> is it likely to be stronger than, say, 100 sequential versions using
> the simple mixer, which would require about the same processing?
>
> Sometimes added strength is not worth the cost.
 
   Hmmm.  Are you familiar with Merkle's Khufu and Wood's REDOC cryptosystems?
Both of these use a scheme that could be used for cheap, fast mixing of blocks.
 
   The basic idea:  To mix two 64-bit blocks, you first do some pre-
processing, to generate a key table (Wood's term) of 256 64-bit entries.
These are secret, derived from key information, probably by running your
general block cipher over a buffer containing key material in CBC mode
over and over again.  (Merkle's Khufu does this.)  The general idea:
   Let T(i) be the ith 64-bit key table entry.  Let L be the left 64-bit
block, and R be the right 64-bit block.  Let R_i be the ith byte of R.
 
   For i = 0 to 7 Do Begin
     L = L xor T(R_i)
     R = R xor T(L_i)
   End
 
   Now, you've done 16 XORs and table lookups.  The table takes 2048 bytes,
so it will fit into a 4K cache.  The same general scheme can be extended to
blocks of arbitrary length, and there are huge numbers of possible variations.
The general idea, however, seems to have cropped up independently in REDOC
and Khufu -- Use the bytes being encrypted to select which key bytes to XOR
into your block.  By itself, one complete trip through the two blocks isn't
enough to guarantee any kind of cryptographic strength, but it *is* enough
to make every bit depend on every other bit--except for the bits in the last
byte of each block.  To get those, too, after you're done with the above,
re-process the first byte in each block, ie L = L xor K(R_0), R = R xor K(L_0)
 
> ---
> Terry Ritter   ritter@cactus.org (cactus.org dies March 18)
>                ritter@rts.com
>                ritter@io.com (perhaps temporarily)
 
   --John Kelsey, c445585@mizzou1.missouri.edu