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
participants (2)
-
DAVESPARKS＠delphi.com -
Hal