From dawagner@tucson.princeton.edu Sat May 20 14:58:44 EDT 1995
Article: 35465 of sci.crypt
Path: cnn.Princeton.EDU!tucson.princeton.edu!dawagner
From: dawagner@tucson.princeton.edu (David A. Wagner)
Newsgroups: sci.crypt
Subject: Re: Triple DES
Date: 20 May 1995 18:51:41 GMT
Organization: Princeton University
Lines: 40
Message-ID: <3pldnt$rad@cnn.Princeton.EDU>
References: <3p500n$2jo@cyber.tn.tudelft.nl> <3pfa98$puc@cyber.tn.tudelft.nl> <3pfetb$8su@krant.cs.ruu.nl> <hO4e7Hr.jmkelsey@delphi.com>
NNTP-Posting-Host: tucson.princeton.edu
Cc: jmkelsey@delphi.com

In article <hO4e7Hr.jmkelsey@delphi.com>,
John Kelsey  <jmkelsey@delphi.com> wrote:
> Mike Dell <mndell@cs.ruu.nl> 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                                             dawagner@princeton.edu