Re: Cryptanalysis

> 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?

Peter Trei <trei@process.com> writes:
> Bill Stewart <stewarts@ix.netcom.com> writes:
> > 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.

The people who did the RC5-48 crack over on <des-challenge@muffin.org>,
and <des-pr@mail.des-challenge.xtn.net>, or at least one of them in 
particular, seems dead set on giving the prize fund 50:50 to the EFF/GNU.  
I'm having a heck of a time talking him out of it.

What does your software do with the key if it finds it?  Attempt to
email it RSA DS/email it to you/report it to user/other?

Do you know how many people are running your uncoordinated breaking
project?  Are you keeping track of how many people have copies.  (I
suppose that not knowing how many people are running the client is a
disadvantage with the uncoordinated approach.)

I'm trying to get UK Computer shopper to include an uncoordinated DES
searcher in their cover CD, along with a feature article on the
challenge (I thought the possibility of winning $10,000 might be a
large part of the interest factor for a reader).  Don't know if
they'll be interested yet.

(What I'm keen on is the sheer size of the readership -- if 10% of
that lot runs the software, something might happen fast!)

Has anyone tried doing something similar in the US?  Anyone with
contacts with other PC magazine with CD/disk on front format,
preferably with large readership, in UK, US, or other countries?

For this kind of project, you'd need something with a simple windows
interface and install script.  I'd have thought a DES breaker which is
installed in win3.1/win95 to always start at boot up, and consume free
cycles (ie set to back off when the machine is doing other things).  A
screen saver with nice presentation would be one way to do this.

Do any of the breakers do this?  Are there clients from other breaks
which could be adapted which do?  I think someone wrote a screen saver
based breaker after the SSL break?

Adam

ps

Have there been any sightings of your code outside the US?

Rumor has it that ftp://ftp.replay.com/pub/incoming is a place where
things often turn up, but I haven't seen it yet.
--
print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`

-----BEGIN PGP SIGNED MESSAGE-----

On Wed, 19 Feb 1997, Adam Back wrote:

> Have there been any sightings of your code outside the US?
> 
> Rumor has it that ftp://ftp.replay.com/pub/incoming is a place where
> things often turn up, but I haven't seen it yet.

Last time I checked, deskr06i.zip, which I believe is the correct filename,
was in /pub/incoming.


Mark
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: noconv

iQEVAwUBMwzm9yzIPc7jvyFpAQHeggf9HN1XnB1pWdwfsDPptMCCJdq6whdDlac/
W2In+Yzxro7n+RyCYdPFHXldlCFDh/st6SbL90XFQp2kS7Mg7Zu7BtgMRuUOugqk
LGW4cDkpjg/gq5/AL4h49puuch4gVV7//pnfGke6fEvaBF/1wvpxNEh1Ades291t
guC1hllIoyQkrZIanwuiMl3ubq5Ep3yuorVoYkqspYYmtfzwkhduDmEbqfMp13mN
BCJG2QIUtm2GctkWn7rQDaLwFBBn+VIhOn1zF9EPfgr1PXt8HIhzWfQ3JkmtF9Ql
wkxz7ebTyhxIMt6culECrcSNBhSGLgxMCLYsnm8NlkGqESbmMVSHjg==
=LePS
-----END PGP SIGNATURE-----

Mark M. wrote:
> Last time I checked, deskr06i.zip, which I believe is the correct filename,
> was in

  Lies, lies. The correct URL is:
ftp://ftp.replay.com/pub/replay/pub/incoming/

(unless you are a drug-pushing, child-molesting terrorist, in which 
case I, too, am lying)