From dawagner@flagstaff.princeton.edu Wed Jun 21 08:46:14 EDT 1995
Article: 36299 of sci.crypt
Path: cnn.Princeton.EDU!flagstaff.princeton.edu!dawagner
From: dawagner@flagstaff.princeton.edu (David A. Wagner)
Newsgroups: sci.crypt
Subject: Re: independent DES keys are not extra secure
Date: 21 Jun 1995 12:39:15 GMT
Organization: Princeton University
Lines: 40
Message-ID: <3s93tj$nrc@cnn.Princeton.EDU>
References: <3s6i97$5ms@cyber.tn.tudelft.nl> <3s76f1$hud@blackice.winternet.com>
NNTP-Posting-Host: flagstaff.princeton.edu

In article <3s76f1$hud@blackice.winternet.com>,
Bruce Schneier <schneier@icicle.winternet.com> wrote:
> 
> I think independent subkeys can be a good idea, if the keys bits are
> available.  It certainly can't hurt,
> 

Sure it can!  It opens you up to nasty nasty related key attacks.

Just a trivial attack breaks DES with independent subkeys with 16
chosen related key queries (and ~ 32 chosen plaintexts).  I'd bet
it's not too hard to come up with even better related key attacks
if you spend an hour or two...

Do you really trust your protocol to protect you against that kind
of attack?  I'd guess lots of protocols don't.

I think the importance of the key schedule is often underestimated.

P.S.  Here's the silly related key attack I was thinking of.

Obtain E(K,P), E(K,Q), E(K',P), and E(K',Q) with two chosen
plaintext queries, where K' is obtained by flipping one bit in
the last round subkey of K, and P,Q are any two known plaintexts.
Now concentrate on S-box 1 in the last round: you know the input
(up to an xor with 6 key bits) and you know the xor of the output
for K and K'; so you can find those 6 key bits entering S-box 1
in the last round.  Continue, deriving the entire round 16 subkey.

You can now peel off the last round and attack DES with 15 rounds
of independent subkeys: i.e. get E(K'',P) and E(K'',Q) where K''
is obtained by flipping one bit in the 15th round subkey of K.
Etc. etc.

Of course, this attack doesn't work at all when you use the DES
key schedule: you can't flip just one bit in the last round subkey
without flipping other rounds' subkey bits at the same time.

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