From: dan@milliways.org  (Dan Bailey)
Date: Wed, 23 Aug 95 09:17:45 PDT
To: solman@mit.edu
Subject: Re: DES & RC4-48 Challenges
Message-ID: <199508231617.AA25787@ibm.net>
MIME-Version: 1.0
Content-Type: text/plain


On Tue, 22 Aug 1995 00:43:20 EDT you wrote:

>The forms of differential cryptanalysis that I'm aware of require The
>cracker to adaptively atack the encrypting or decrypting device. I
>therefore do not believe that they are especially applicable to
>financial transactions schemes, most of which change keys quite
>frequently.
>
>JWS

According to Biham and Shamir's Differential Cryptanalysis of DES, "An
interesting feature of the new attack is that it can be applied with
the same complexity and success probability even if the key is
frequently changed and thus the collected ciphertexts are derived from
many different keys.  The attack can be carried out incrementally, and
one of the keys can be computed in real time while it is still valid. 
this is particularly important in attacks on bank authentication
schemes, in which the opponent needs only one opportunity to forge a
multi-million dollar wire transfer, but has to act quickly before the
next key changeover invalidates his message.  This is the first
published attack which is capable of breaking the full DES in less
than the complexity of the exhuastive search of 2^55 keys." (7-8)
	The problem with this attack, of course, is generation and analysis
of all the required chosen plaintexts.  The analysis phase eats up
2^37 time looking at 2^36 ciphertexts from a universal set of 2^47
chosen plaintexts.  Brute-forcing SSL has a worst-case time complexity
on the order of 2^40.  It appears that complexity for breaking
16-round DES is on the order of 2^37, according to Biham and Shamir.
(87)
	Is there any published source code available for this type of attack?
 The book itself doesn't contain any code, just lots of proofs.  Since
2^40 > 2^37, I think a group effort would be capable of mounting this
attack.
						Dan

******************************************************************************
"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
******************************************************************************