Subject: Re: Triple DES

From: [email-masked] (David A. Wagner)
Date: 20 May 1995 18:51:41 GMT

In article <[email-masked]>,
John Kelsey  <[email-masked]> wrote:
> Mike Dell <[email-masked]> writes:
>  
> >To be really really safe it can't hurt to add an extra 56 bits 
> >for 3 keys instead of 2. 
>  
>    Actually, DA Wagner pointed out on sci.crypt.research (I don't know if
> he caught this himself or read it somewhere), there *is* a related-key
> attack against 3DES with three keys that doesn't exist against 3DES with
> two keys.  It's only practical if you can get an opponent to use pairs of
> 3-key 3DES keys so that the second key is the first key rotated 56bits.
> This isn't likely to be a problem in the real world....
> 

Hrmm, that wasn't the related key attack I was thinking of:
I'll admit I don't see how to get your idea to work with less
than ~ 2^{64-n} related key known plaintexts and ~ 2^{56+n}
computations...  Can that be improved?

I was thinking of a slightly different attack.  I get you to
encrypt a known plaintext P under 3DES key (K_1,K_2,K_3); then
I get you to decrypt the ciphertext C under 3DES key (x,K_2,K_3)
to get P', where x can be any 56 bits of your choosing.  Now
I know that P' = DES_Decrypt(x, DES_Encrypt(K_1, P)), so with
the meet-in-the-middle attack on double DES, I recover K_1
and x.  Let A = DES_Encrypt(K_1, P); knowing A and
C = DES_Encrypt(K_3, DES_Encrypt(K_2, A)), I can find K_2
and K_3.  This whole deal requires ~ 1 related key chosen
ciphertext and ~ 2^56 computations.

I haven't seen this in the literature anywhere, but there's
nothing tricky about it, so I doubt I'm the first one to
notice it.

In any case, I don't think two-key triple-DES suffers from
this problem.

-------------------------------------------------------------------------------
David Wagner                                             [email-masked]