Path: news.io.com!uunet!in1.uu.net!gatech!udel!princeton!cnn.Princeton.EDU!
+     tucson.princeton.edu!dawagner
From: dawagner@tucson.princeton.edu (David A. Wagner)
Newsgroups: sci.crypt

Subject: Re: Variable Size Block Ciphers
Date: 25 Aug 1995 23:40:52 GMT
Organization: Princeton University
Lines: 78
Message-ID: <41ln24$ebf@cnn.Princeton.EDU>
References: <199508202317.SAA17442@tristero.io.com>
NNTP-Posting-Host: tucson.princeton.edu
Summary: cryptanalysis
Cc: ritter@io.com

In article <199508202317.SAA17442@tristero.io.com>,
Terry Ritter  wrote:
>  For some time now I have been working with some apparently new
>  ciphering structures which I call "Variable Size Block Ciphers."
> 
>   The simplest effective scheme I have found looks like this:
> 
>                    input byte
>                        |
>   (left-adjacent       v       (right-adjacent
>       column)          S0          column)
>                        v
>          from XOR0 -> XOR0
>                        + -> to XOR0
>                        v
>                        S1
>                        v
>                       XOR1 <- from XOR1
>             to XOR1 <- +
>                        v
>                        S2
>                        v
>                       XOR2 <- from XOR2
>             to XOR2 <- +
>                        v
>                        S3
>                        |
>                        v
>                    output byte
> 
>  where S0..S3 are byte-wide substitution tables.
> 

No go: this is easily cryptanalyzed by differential cryptanalysis.
Suppose A -> B by S0 where A,B are bytewide values.  Then I use input
differential (A,A,0,0,0,0,...) which leads to the round differential
(B,B,0,0,0,0,0,...) after S0 and to (B,0,0,0,0,0,0,...) after XOR0.
After that, the XORs all propagate to the left, so the differentials
will be (xxx,0,0,0,0,0,...) all the way down to the ciphertext.
The resulting ciphertext differential is easily recognizable.

I'll assume that the keying material is in the S boxes: then if you
pick A,B at random this differential attack should have probability
2^{-14}, since A -> B with expected probability 2^{-7}.  One can
also use advanced techniques to search over all possible A values
(without needing any more chosen plaintexts) and find the best one.

So how to avoid this attack?  One answer is easy: make your XORs
propagate first right, then left, then right, then left, etc.
Also, you'll need to add lots more rounds to avoid more sophisticated
differential attacks.  More analysis is needed.

Also, you should think about the decision to keep all S-boxes on
a layer the same.  This has an unfortunate consequence: if we're
allowed encryption of a n-byte block B and a (n+1)-byte block (B,xxx)
with the same key, we can start attacking the cipher.  Also,
it means that there are attacks based on getting the encryption
of B and B' (where B' is B rotated right by one block): these
attacks will have complexity something like 2^{8r} where r is the
number of rounds (off the top of my head).  Again, more analysis
is needed.


Your web page includes another type of design (example 2: diffusion
across layers) which has many of the same vulnerabilities.

Interestingly, example 4 there reminds me of a paper by Serge
Vaudenay about multipermutations and cryptanalysis of SAFER and MD4.
I think it was presented at the Leuven algorithms workshop, though
I'm not sure.... you might check it out.


A variable width block cipher would be interesting, but I think
you need to do a bit more careful analysis if you want a solid design.

-------------------------------------------------------------------------------
David Wagner                                             dawagner@princeton.edu