Subject: Re: cracking n-DES?

From: [email-masked] (David Wagner)
Date: 27 Jun 1997 23:04:12 -0700

In article <[email-masked]>,
Carl Ellison  <[email-masked]> wrote:
> There are several reasons I have advocated the combination
> 
> 	des|tran|des|tran|des
> 
> if you want really serious multiple-DES.

Ok, challenge taken.  If I understand the proposal correctly, d|t|d|t|d
isn't nearly as strong as 3-DES: this post describes how to break it with
3 * 2^{56} trial decryptions and one chosen plaintext query, I think.

The intuition behind the attack is that des|tran|des|tran|des is using some
form of (roughly speaking) "inner chaining".  As Biham has shown for other
inner chaining modes, outer chaining tends to be much stronger.

The lesson to walk away with (IMHO): if you use triple-DES, use it as a
black box, i.e. as a block cipher with a 168-bit key and a 64-bit block size.

Here is the attack.  I assume you have a known plaintext/ciphertext pair
(P,C) which is about two blocks (16kB) long, or longer.  Generate
another chosen plaintext P' which differs from P only in the first 8
bytes of the second block.  Get the corresponding ciphertext C' by doing
a chosen-plaintext encryption with d|t|d|t|d.  Note that tran does a
transposition on the bytes, keyed by (a histogram on) the (8k) bytes of
the first block.  This means that (des|tran)(P) differs from
(des|tran)(P') in only 8 bytes, which are probably pretty evenly spaced
out over the second block.  Each such byte input to the 2nd des pass
will avalanche to affect an entire 8-byte DES-output.  (I am assuming
des is in ECB mode throughout.)  Therefore, (des|tran|des|tran)(P) will
differ from (des|tran|des|tran)(P') in just 64 bytes, and those 64 bytes
will be pretty evenly spaced out over the 8k bytes of the second block.
Finally, we can see that C and C' will differ in the second block only
at 64 8-byte DES-outputs (corresponding to the 64 bytes which differ at
the input to the 3rd des pass).  Pick one such 8-byte DES-output where
C,C' differ: suppose those two DES-outputs are x,x'.  For each possible
DES key k, try decrypting x,x'; recognize the correct guess at k by the
fact that D(k,x) differs from D(k,x') in just one of the 8 resulting
bytes.  This recovers the 56-bit DES key used in the 3rd des pass.
Strip off the final des pass to obtain known texts for des|tran|des, and
recover the 2nd-pass DES key with 2^56 more trial decryptions by using
a similar technique.

Did I misunderstand the proposed mode of operation?  Any comments?

---

From: David Wagner <[email-masked]>
Date: 28 Jun 1997 09:15:42 -0700

In article <[email-masked]> you write:
> 
> I have to study
> Dave's attack more, [...]
> 

Here's the cliff notes:

You exploit a lack of diffusion.  You put in a one-byte difference
in the plaintext (say).  Each ECB-DES layer can only increase the
number of bytes that differ by a factor of 8 (and then the trans
re-shuffles them around).  After two des|trans passes, you've only
got 8^2 = 64 bytes differing, out of a total of 8192 bytes per "trans
permutation block" -- that's very minimal avalanche.

Now you just guess the last DES key, peel off the last layer, and
check whether the result has the reduced-avalanche pattern that you
expect to see after 2 passes.