Can we kill single DES?

Since it looks like the US government will be allowing the export of 
56 bit espionage-enabled software, it's time to kill single DES.

As some of you will recall, a while back I wondered aloud about the
feasibility of brute-forcing DES on general purpose machines, ala the
RC4-40 crack last year. 

Unlike many cypherpunks, I actually write code (:-). I took Phil
Karn's DES386 as a starting point, and modified it to run effiiciently
on the Pentium. The code I've written will run 14 round DES (all
that is required for a key test app) at 254,000 crypts/sec on a
90 MHz Pentium.  

Allow about 10% overhead for key scheduling (there are some tricks to
speed this up), and we're still at about 250,000 keys/sec on a 100MHz
Pentium (I'm using a nominal 100 MHz Pentium as my 'unit' of
cpu power).  On a Pentium, it runs entirely in the L1 cache.  The code 
will also run on a 486, but at less than half the number of crypts/sec 
for the same clock speed.

On this type of processor, it would still take 9133 years to exhaust 
a 56 bit key space. On the other hand, on 20,000 processors of this
power it would take less than 6 months. If the target is encrypted
in a chaining mode with an unknown 8 byte IV, the time more than 
doubles. 

Clearly, this goes far beyond the number of cpus available to the 
members of this list (though well within the power of most governments
and  many corporations)

The best idea I've heard for recruiting this many cpu cycles is to create
a screen saver which does DES-cracking while machines are idle.
Another incentive is to offer a cash prize to the person(s) who find the
key.

Yes, I KNOW that a hardware based cracker is a LOT more efficient,
but between the up-front cost and the difficulty of design and production,
it's less likely to get done.  (Still if someone wants to buy me a nice
FPGA board, I'll see what I can do).

If you're interested in volunteering machines to do a key search, please
read to the end.

Questions for general discussion:

1. Is this a good idea? What will happen if DES becomes perceived
    as insecure?
2. What is the probability of success required to make it worth doing?
3. What would be the consequences of failure?
4. What other platforms than NT/Win95/Pentium should be considered?
   I could write a Unix demon version, but unless it's tailored for the 
   cpu, a lot of efficency is lost
   (The aggregate number of idle cycles available for testing is the 
  crucial number).
5. What's a good target? Ideally, we need a plaintext/ciphertext pair,
   encrypted in Single DES ECB mode. Preferably from a commercially
   available program, in which a single key is used for a great deal
   of traffic over a long period. I would strongly prefer, however, that 
   the target key be a  *test* key - I don't want to compromise 
   anyone's actual security.
   We need a target which is both convincing and realistic.
6. What other incentives can be used to recruit machines?
------------------------------
If you're interested in volunteering cycles:

RESPOND ONLY TO ME (trei@process.com), NOT TO THE LIST.  The 
last thing we need is a hundred 'I'll help' messages on the list.

Assume that the program will be a Win95/NT screen saver or 
Unix deamon. Think about how many machines you could get 
it to run on (maybe you can talk other people into installing
it as a screen saver or background task)

I have not written the screen saver yet. I will not do so unless it looks 
like we'lll get enough machines, so nothing is likely to happen for 
a couple of months at least.

I need to estimate how many cpu cycles will be available:

Calculate:

Number of Pentiums * Hours available/week * MHz
+
(Number of 486's * Hours available/week * MHz * 0.30)

For, Alphas, MIPS, Motorola, PowerPC etc, running UN*X, MAC, etc, 
just report how many cpus,  their speed, and OS - I'll need help to 
get versions for other platfoms. 64 bit processors like the Alpha
can run this stuff *fast*.

Send the aggregate numbers to me. I'll also need to know how many 
machines are directly on the Internet and could thus query a 
key-space server, and how many would need some other 
mechanism to get keyspace and report results. If you're volunteering
machines which are outside of the US/Canada, please note the fact:
ITAR may be an issue here.

 I'll summarize to the list.

Peter Trei
trei@process.com

"Peter Trei" writes:
> Since it looks like the US government will be allowing the export of 
> 56 bit espionage-enabled software, it's time to kill single DES.

Double plus agreed.

> On this type of processor, it would still take 9133 years to exhaust 
> a 56 bit key space. On the other hand, on 20,000 processors of this
> power it would take less than 6 months. If the target is encrypted
> in a chaining mode with an unknown 8 byte IV, the time more than 
> doubles. 
> 
> Clearly, this goes far beyond the number of cpus available to the 
> members of this list (though well within the power of most governments
> and  many corporations)
> 
> The best idea I've heard for recruiting this many cpu cycles is to create
> a screen saver which does DES-cracking while machines are idle.
> Another incentive is to offer a cash prize to the person(s) who find the
> key.

These are both possibilities.

> 1. Is this a good idea? What will happen if DES becomes perceived
>     as insecure?

Well, I believe that we are better off if the general perception
catches up with reality.

> 2. What is the probability of success required to make it worth doing?

We need 50% success in one month to make it reasonably worthwhile.

> 3. What would be the consequences of failure?

I don't think we will fail :)

> 4. What other platforms than NT/Win95/Pentium should be considered?
>    I could write a Unix demon version, but unless it's tailored for the 
>    cpu, a lot of efficency is lost
>    (The aggregate number of idle cycles available for testing is the 
>   crucial number).

Other CPUs: MC68k, PowerPC, SPARC and Alpha versions, in roughly that
order.

> 5. What's a good target?

Good question :)

> Assume that the program will be a Win95/NT screen saver or 
> Unix deamon.

An X screen saver would also be good. Lots of
Linux/FreeBSD/NetBSD/BSDI weenies in the world.

Perry

On Tue, 1 Oct 1996, Peter Trei wrote:

> Since it looks like the US government will be allowing the export of 
> 56 bit espionage-enabled software, it's time to kill single DES.
> 
> As some of you will recall, a while back I wondered aloud about the
> feasibility of brute-forcing DES on general purpose machines, ala the
> RC4-40 crack last year. 
[...]

> Yes, I KNOW that a hardware based cracker is a LOT more efficient,
> but between the up-front cost and the difficulty of design and production,
> it's less likely to get done.  (Still if someone wants to buy me a nice
> FPGA board, I'll see what I can do).

I understand that *two* independent efforts cracking single DES using FPGAs 
are currently being set up. If the parties whish to come forward, my offer 
to donate to this cause still stands.

--Lucky

DES CRACKING SCREENSAVER

Sorry for writing twice, beside wanting to add that I might be able to do some
programming for a worthy cause, I just got a rather good idea to make a
screensaver unique and interesting ( making people want to burn cycles )
Picture this: the user upon installing the program points at his/her location on
a world map. This location is send to the keyserver, which sends back highly
compressed information about where other people are running their
"screensavers", the screensaver itself can simply display a rotating globe,
where the different densities of global usage is given in colour shades, showing
an inverse sunclock of sorts. I think such a concept might give the DES-cracking
screensaver a critical mass.

  frank

On Wed, 2 Oct 1996, Frank Andrew Stevenson wrote:

> DES CRACKING SCREENSAVER
[...]
>the screensaver itself can simply display a rotating globe,
> where the different densities of global usage is given in colour shades, showing
> an inverse sunclock of sorts. I think such a concept might give the DES-cracking
> screensaver a critical mass.

That's a great idea. I belive it would be a powerful incentive.

--Lucky

Frank Andrew Stevenson writes:
> This location is send to the keyserver, which sends back highly
> compressed information about where other people are running their
> "screensavers", the screensaver itself can simply display a rotating
> globe, where the different densities of global usage is given in
> colour shades, showing an inverse sunclock of sorts. I think such a
> concept might give the DES-cracking screensaver a critical mass.

Sounds like fun, actually -- are you volunteering to write it?

.pm