From: "Peter Trei" <trei@process.com>
Date: Wed, 2 Oct 1996 12:08:36 +0800
To: cypherpunks@toad.com
Subject: Can we kill single DES?
Message-ID: <199610012026.NAA28151@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


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