Re: Can we kill single DES?

[jim bell <jimbell@pacifier.com>]

At 04:27 PM 10/1/96 -6, Peter Trei wrote:
>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).  
[snip]
>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. 
[snip]
>Questions for general discussion:
>
>1. Is this a good idea? What will happen if DES becomes perceived
>    as insecure?

Reluctantly, I'd have to say that I don't think this is a good idea.  If 
anything, what this would inadvertently demonstrate is how difficult (at 
least, with non-dedicated hardware) it is to crack DES. The resulting number 
will be misleading if it doesn't represent the real danger to encryption 
users.  I contend that a misleading estimate is actually worse than none at 
all, because it is a number which can be misused.  They can say, "Hey, these 
guys had to apply $10-20 million dollars worth of computer equipment for a 
full year just to get the contents of a SINGLE MESSAGE!"  

The real danger is, indeed, a dedicated system, because it would presumably 
be the way a "real opponent" would do it.  First, my assumptions: I assume 
that it would be generally straighforward to build a cracking chip that 
tries 10 million keys per second, with a great deal of internal parallelism 
and pipelining.  This is a factor of 40 higher than the number you quoted 
above for a 100 MHz Pentium.  Further, I assume that at least 10 of these 
chips could be installed on a single card in a PC, monitored by a program 
running on that PC.  Thus, it would take 9133 years/400, or 23 years, for a 
single one of these modules to try all keys.  With "only" 100 of these 
units, a crack would take about 3 months max, 1.5 months on the average.

Now, THAT sounds like a real threat!  It would be a far more effective 
demonstration of the weakness of DES. Compared to this, the alternative, say 
an average of a crack in a year with 4500 machines, is practically 
meaningless.   An even more ominous configuration would involve perhaps 50 
chips per full-length board, seven boards installed in a stripped-down  PC, 
which would produce a crack in 4 months average with one system alone.


So how would all this be done?  First, write a serious proposal for the 
project and circulate it among companies with fab capacity.   How about 
finding a custom, semi-custom, or other semiconductor manufacturer who would 
be willing to do the fab in exchange for the publicity, or a deep discount. 
It might be particularly "relevant" if that company had an interest in 
seeing DES discredited, possibly because it was going to be building an 
encryption chip with greater security. (NTT?  and their new encryption 
chip?)  Likewise, find a politically-sympathetic designer with access to IC 
layout software, etc.  The way I see it, there has to be a huge amount of 
unused 0.5-0.7 micron IC capacity around the world.  Remember, we're only 
talking about a few hundred wafers.

And for example, as I recall, I've seen a number of ads over the years for a 
company called "Orbit Semiconductor,"  which builds small-volume  IC's by 
putting a number of different designs on a single wafer.  The number of die 
per wafer is, more or less, based on the volume needed for that particular 
chip.  They do a new fab run fairly regularly, to accomodate designs with 
fast turnaround.  Presumably, they occasionally would like to do a run 
quickly without waiting for the wafer to "fill up" with new designs.  

Anyway, the way I see it, you're probably going to burn up over a million 
dollars worth of ELECTRICITY alone on a single crack with Pentiums.  Why not 
get whoever is doing these cracks to donate 1/10th of this value to finance 
the portion of this project which cannot be "finagled"?

Maybe Microsoft would be willing to help?  After all, it is THEY who are 
going to be limited to DES-strength exports if things continue as they've 
been going.  How about Intel?



Jim Bell
jimbell@pacifier.com