Date: Wed, 19 Feb 1997 08:16:46 -0800 From: Bill Stewart <stewarts@ix.netcom.com> To: Scott Auge <scotta@sauge.com> Cc: cypherpunks@toad.com Subject: Re: Cryptanalysis

At 11:21 AM 2/15/97 -0500, you wrote:

...

Was wondering if anyone could help me with short explainations on the cryptanalysis of SKIPJACK and DES. If ya hit www.sauge.com/crypt you might get a better idea of what i'm trying to accomplish.

Cryptanalysis of DES is a 25-year ongoing academic exercise, with lots and lots of results. It's easy to attack it in 2**55 tries, because of symmetry, but that's a very large number :-)

Many people have made statements to the effect that the complement key property (if key K encrypts plaintext P to ciphertext C, then K' encrypts P' to C', where A' is the one's complement of A') of DES halves the work for a brute force attack, but these people don't seem to have ever tried to actually use this property - it's effectively useless. You still need to run the DES rounds, and the only win would be in the fact that preparing the key schedule of K' from the key schedule of K used to be easier than preparing it from K' directly. This is no longer a win, since preparing key schedule for (K+1) from the key schedule of K is just as easy. There's the possibility that I'm seriously dense (even Denning has made statements about halving the effort), but I just don't see it. [...]

The slow part of the attack _had_ been key scheduling, but recent work by Peter Trei and others shows that you can do key scheduling very efficiently for the brute-force keysearch problem by picking keys in Gray Code order (since a one-bit change in key causes a simple change in key-schedule - it's totally useless for normal encryption/ decryption, but it's a big win for brute-force cracks.)

It's not totally useless - if you're going to have to prepare a lot of different key schedules (say, for many session keys under IPSEC), it's still a win to OR together the key bit fanouts than to generate the key schedule by the traditional method. It trades a lot of upfront, one-time work for a later speedup.

There may be a distributed Internet crack using that approach, though DES is still very inefficient on general-purpose computers and works better on bit-twiddliing chips.

There's one slowly shaping up, organized by the same people who did the RC5-48 crack. I'm still rooting for an uncoordinated search, which is already underway. Peter Trei trei@process.com PS: Is this the last message to cypherpunks actually about crypto?