Losing the Code War by Stephen Budiansky

Trei, Peter ptrei at rsasecurity.com
Wed Feb 13 19:50:14 EST 2002



> ----------
> From: 	marius[SMTP:marius.corbu at analog.com]
> Sent: 	Wednesday, February 13, 2002 6:50 PM
> To: 	Trei, Peter
> Cc: 	Joshua Hill; 'Ben Laurie'; cryptography at wasabisystems.com
> Subject: 	Re: Losing the Code War by Stephen Budiansky
> 
> "Trei, Peter" wrote:
> > 
> > > marius[SMTP:marius.corbu at analog.com] wrote:
> > >
> > > > marius wrote:
> > > > > Not quite true. Encrypting each message twice would not increase
> the
> > > > > "effective" key size to 112 bits.
> > > > > There is an attack named "meet in the middle" which will make the
> > > > > effective key size to be just 63 bits.
> > > >
> > > > Peter Trei wrote:
> > > > > Don't forget that the MITM attack (which Schneier claims
> > > > > takes 2^(2n) = 2^112 time), also requires 2^56 blocks
> > > > > of storage.
> > > > [...]
> > > > > I don't lose sleep over MITM attacks on 3DES.
> > >
> > > 2^57 operations, with 2^56 blocks of storage manipulation can be
> > > approximated to: 2^56 * log(2^56) + 2^56 * log(2^56) = 2^62 + 2^62 =
> > > 2^63
> > >
> > > Betting on storage as a show stopper is not a good idea, regardless of
> > > sleep pattern.
> > >
> > > Marius
> > >
> > Oh, I totally agree - my first followup (Feb 4) read:
> > 
> > - start quote -
> > 
> > Either way, my point stands: any attack which requires 2^56 blocks
> > of storage is probably intractable for the time being, imho. 10 years
> > from now, I'm not so sure.
> > 
> > - end quote -
> > 
> > The expansion of storage over the last 20 years is even more
> > astonishing than the  speedup of microprocessors. The first IBM
> > PC to ship with a HD (PC-XT ~1983) had a 5 Mb drive. When I
> > worked for Columbia U, undergraduates were given about 50kb
> > of diskquota for a semester.
> > 
> > Nevertheless, 2^56 blocks of centralized storage is a lot, and
> > will remain a lot for a while.
> > 
> > Peter Trei
> 
> So let say that I don't have 2^56 blocks of centralized storage, but I
> have 2^40. Now by independently guessing 16 bits of each Key1 and Key2,
> I will need only 2^(56-16) = 2^40 blocks of centralized storage . But
> the attack must be run now over 2^16 * 2^16 pairs of such tables to
> allow all possible key pairs. So the time is on order of 2^(2*16) *
> 2^(56-16) = 2^72.
> 
> That means that I can make an time-memory tradeoff, such that it will
> accommodate my resources. 
> 
> Marius
> 
Well, I guess your resources include a LOT of time. 2^72 test
decryptions....
Lets be optimistic. Lets assume you can do a test every clockcycle, and
your cracker is running at 1GHz. How long would it take you to do 2^72
tests???

About 150,000 years, if my math is correct.

If Moore's Law holds out, you might get an answer in 20-30 years, for a
single message. (Subsequent ones would be a lot faster).

But it's all moot - no one who knows what they are doing uses 1 or 2 
key DES, and even 3 key DES is only being put in new apps until 
folks are more confident with 128+bit AES. 

Peter Trei






---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com



More information about the cryptography mailing list