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 Ritterwrote: > 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