From: aba@dcs.exeter.ac.uk
Date: Thu, 17 Aug 95 13:00:33 PDT
To: hfinney@shell.portal.com (Hal)
Subject: Re:  Breaking DES anyone? (was: Breaking RC4-40 for less)
Message-ID: <9403.9508171959@exe.dcs.exeter.ac.uk>
MIME-Version: 1.0
Content-Type: text/plain



Hal Finney <hfinney@shell.portal.com> writes on cpunks:
> > Another approach is to do lots of keys simultaneously - so you set up
> > this distributed effort which is continually re-sweeping the 40 bit
> > keyspace, say every couple of days or whatever.  You can sweep for
> > more than one key at once at very low incremental cost, an extra key
> > costs close to nothing.  So say you are searching for 1000 keys at
> > once [...] on average a key will fall out every 3 minutes.
> 
> I don't see how you can sweep for more than one key at once at low cost.
> Because of the salt, every possible SSL encrypted message has to be swept
> independently.  You can't sweep for two messages' keys at once because the
> input to the MD5 is different even for the same 40-bit key.

Agreed.  I was not being clear and mixing various things in one post.

I was talking about 3 different systems:

1) export SSL 88 + 40
2) pure RC4-40  (hypothetical - possible microsoft / other apps)
4) DES (56 bits, can it be done)

In the part you quote I was talking about pure RC4 40, I'm not sure
which applications fall into this category, but it is one thing we
have yet to determine.  Perhaps Microsoft Access falls in to this
category?  Other microsoft applications / other vendor applications?
someone needs to do the microsoft equivalent of a FOIA to extract this
info.  Anyone have any Microsoft software with encryption that they
could quiz Microsoft tech support about?

For export SSL it does not work for the reason you describe, the 88
bit salt effect.

For DES I think it does work (attacking many keys at once), but then
my understanding of DES is limited, but as a block cipher, presumably
you can just brute keys in a straight forward manner?  If so you can
try multiple keys at once, unless there is some salt effect involved
with typical CBC 56 bit DES operation too?  Depending on the relative
costs of the parts of the block cipher, 

a) key-setup
b) block / stream decrypt

pure RC4 is designed so that a) is vastly more expensive than b).

How does this pan out for DES?  DES (and RC4) are designed for fast
encrypt / decrypt, but is there an appreciable key setup phase?

I have these figures courtesy of Andy Brown:

> Using Eric Young's very fast libdes code, and using the supplied speed 
> test program I get the following output on a Sparc 20 (1 processor):
> 
>   Doing set_key for 10 seconds
>   582771 set_key's in 9.83 seconds
>   Doing des_ecb_encrypt's for 10 seconds
>   989184 des_ecb_encrypt's in 9.85 second
>   Doing des_cbc_encrypt on 8192 byte blocks for 10 seconds
>   982 des_cbc_encrypt's of 8192 byte blocks in 9.92 second
>   Doing crypt for 10 seconds
>   37101 crypts in 9.89 second
>   set_key       per sec =     59284.94 ( 16.9uS)
>   DES ecb bytes per sec =    803398.17 ( 10.0uS)
>   DES cbc bytes per sec =    810941.94 (  9.9uS)
>   crypt         per sec =      3751.37 (266.6uS)

So what is a brute DES program on multiple keys with CBC mode (is this
the most common mode?) going to look like in terms of calls to these
various calls?

The set_key looks slow compared to the DES cbc bytes per sec, even if
you have to cycle a couple of blocks to get to your known plaintext
location.  Am I on the right tracks?  It seems to me that you gain
considerably by doing multiple keys even with CBC and random IV due to
relatively fast block decrypt as compared to key setup.

> If digital cash in micro amounts became practical, people could be paid
> to let the "idle cycles" on their computers be used for this kind of
> highly parallel application.  (Some people have speculated that graphics
> rendering would be another suitable choice.)  It would be interesting to
> see what the market price of cycles became in such an environment.  That
> would give a better benchmark for the cost to break keys.

I think this would be an interesting way to determine the market value
of idle cycles, and likely lead to cheaper figures for breaking things
than are touted (by newspapers, and people to whose advantage it is to
estimate generously the cost).

Adam