From: dan@milliways.org  (Dan Bailey)
Date: Wed, 23 Aug 95 12:50:05 PDT
To: andrew_loewenstern@il.us.swissbank.com
Subject: Re: DES & RC4-48 Challenges
Message-ID: <199508231949.AA25702@ibm.net>
MIME-Version: 1.0
Content-Type: text/plain


On Wed, 23 Aug 95 11:53:22 -0500 you wrote:

>Dan Bailey writes:
>>  According to Biham and Shamir's Differential Cryptanalysis of DES,
>>  "An interesting feature of the new attack is that it can be applied
>
>If I read this correctly, then the keys used for generation of the chosen  
>plaintext-cyphertext pairs is irrelevant and once the required computation is  
>done, one can crack any '...one of the keys can be cputed in real time while  
>it is still valid.'..
>
I haven't read this entire book, mainly because a lot of it is over my
head with some pretty esoteric proofs.  The impression I got was that
if the cryptanalyst is steadily keeping up with the key changes until
he collects the required 2^36 from a pool of 2^47 valid
plaintext/cyphertext pairs, he then can recover the last key used.  I
don't understand what constitutes a "valid" pair in this context. 
Also, I'm not sure if all the computation he's done to get to that
point is applicable in his attack on the next key.  It appears not. 
If all of his precomputation was somehow salvagable, I think we'd
already have heard about someone actually doing it.
	But then again, I don't understand how his precomputation could *not*
be applicable. He'd just have to drop off the computations done for
the first key.  Perhaps the difficulty in this problem comes from not
knowing when the source is changing keys.
	According to Schneier, "To get the requisite data for this attack,
you have to encrypt a 1.5Mbits/second data stream of chosen plaintext
for almost three years." (240)  With the massively-parallel nature of
Cypherpunks, this is probably feasible, assuming we could figure out
what needed to be done.
	Another angle is cracking a reduced-round version of DES.  8-round
DES can be analyzed in 2^9 using differential cryptanalysis.  Since
I'm sure the press doesn't really understand using multiple rounds in
iterated cryptosystems, maybe that little detail would slip by.  2^9
could easily be handled by an Alpha in the evening.
						Dan

>So what, exactly does this mean?  Can I do most, if not all of the feeding of  
>chosen plaintext into my personal DES box in my basement, do the required  
>computation (admittedly there is a lot of work to do here), then go out and  
>start breaking wire-transfers with a minimal of chosen plaintext?  That is  
>what the above quotation would seem to imply.
>
>Seems incredible...  I surely must be reading much more into the passage than  
>is really there...
>
>andrew
>
>
>
******************************************************************************
"I think, therefore I am" - Descartes                            Dan Bailey
"I don't think, therefore I'm a moustache." - Sartre		    dan@milliways.org
Worcester Polytechnic Institute and The Restaurant at the End of the Universe
******************************************************************************