Losing the Code War by Stephen Budiansky

marius marius.corbu at analog.com
Wed Feb 13 18:50:41 EST 2002


"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

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



More information about the cryptography mailing list