Re: Double DES calculations

Hal Finney wrote:

> I'll give you one similar example, though.  I think this is the technique
> used in Pollard "rho" factoring.  You have an iterated series, x=f(x), and
> you want to know if it has any cycles, any values which are eventually
> repeated.  At first glance you might think that to look for a cycle of
> length N you would have to store N values of the series and check each
> value for a match, taking order of N in time and space.  The Pollard tech-
> nique instead runs two copies of the iteration at once, one twice as fast
> as the other: x=f(x) and y=f(f(y)).  Each time you just compare x and y
> for a match.  This takes about twice as long but uses no memory.

The thread was concerning the vulnerability of Double-DES with an
intermediate layer of IDEA in the middle.  It was proposed that if IDEA
could ultimately be TRIVIALLy cracked, then DES-IDEA-DES was no stronger
than Double-DES.  At that point I did some "back of the envelope"
calculations on the cost of breaking Double-DES using a MITM attack.

I'm not sure how "cycles" fit into DES.  The brute-force technique I was
hypothesizing involved trying all possible keys on the encrypt and decrypt
sides, storing them the resultant 64 bit blocks (all 2^60 bytes of them),
then comparing them.  How would Pollard rho speed that up?

 /--------------+------------------------------------\
 |              |  Internet: davesparks@delphi.com   |
 | Dave Sparks  |  Fidonet:  Dave Sparks @ 1:207/212 |
 |              |  BBS:      (909) 353-9821 - 14.4K  |
 \--------------+------------------------------------/

DAVESPARKS@delphi.com writes:

>The thread was concerning the vulnerability of Double-DES with an
>intermediate layer of IDEA in the middle.  It was proposed that if IDEA
>could ultimately be TRIVIALLy cracked, then DES-IDEA-DES was no stronger
>than Double-DES.  At that point I did some "back of the envelope"
>calculations on the cost of breaking Double-DES using a MITM attack.

>I'm not sure how "cycles" fit into DES.  The brute-force technique I was
>hypothesizing involved trying all possible keys on the encrypt and decrypt
>sides, storing them the resultant 64 bit blocks (all 2^60 bytes of them),
>then comparing them.  How would Pollard rho speed that up?

I don't know how to speed this up.  Pollard rho was a cautionary tale of
how sometimes time/space tradeoffs exist.  If the main cost of double-DES
is in space but the time cost isn't that bad, then if there were such a
tradeoff it could be dangerous to use it.

Most of the time-space tradeoffs that I can think of for a basic MITM
attack like this are pretty costly.  For example, instead of trying all
the keys on both sides you could try just half the keys each time.  This
would take only half as much space but up to four times the time.  You
could also do some hashing to save space at the cost of false positives and
more time.  Again, the point is not so much that double DES is weak, but
more that if its strength is solely due to space costs that gives much
less of a good feeling than if you had an algorithm that was strong both
in space and in time.

Hal