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