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 | \--------------+------------------------------------/