Re: Can we kill single DES?
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
In <199610020201.TAA10143@mail.pacifier.com>, on 10/01/96 at 07:01 PM, jim bell <jimbell@pacifier.com> said: .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. basicly, we're proving that the Feds are a fraud, giving the public a gift of something that NSA can blow it away in real time. If the project is not ballyhoo'd when we're getting our act together, and it goes underground when the team and fab is ready to role, we won't have the Clinton-speak media taunting us, or screaming for our capture and obliteration.... basically, shock is an effective communicator, just like the networks find it necessary to hustle more bombings, more death and pain &C to get attention. grab 'em by the short hairs and give them a good shake or two. we might even be perceived as a good, not evil force... but I doubt it; the press mentality is too low. no, I certainly do not think hardware in particular is a bad idea. .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. . .Now, THAT sounds like a real threat! particulary if the design emphasizes unlimited linear extension! .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. . without a doubt, this is the best approach, but you will find the chassis have a mix of ISA and PCI, or in some cases like I specify, they will be EISA and PCI . I know where there is a 20 slot PCI passive backplane in a rack mount for $350 and I think the vendor has P133 cards with either 128 or 512 M 72 pin slots. 512M is about 4,000 smackaroos at this point. PCI is much easier to interface than ISA and you have the bus bandwidth to support the processor to co-processor transfer rates. I'm not going to go through the mental masturbation of what DSPs and FNGAs could manage in iterations/second until there is a firmer design, but 350 chain/parallel or tiered chips sounds like it might be more than 10% of the way to a terawhatever. .So how would all this be done? First, write a serious proposal for the .project and circulate it among companies with fab capacity. disagree, I would not even consider begging at the door of any charitable fab until the design, and probably the layout, is in the can. we might find it necessary to expand the trace depending on the capabilities of the offered facilty, thereby by burning both more power, and reducing our yield per wafer. secondly, circulating a proposal among the hungry pack is shopping around, which is almost always suicidal in raising money and finding manufacturing partners. they all know each other, and you will end up with a "decision by commitee" and we know committees are always formed to absolve the participants of blame for failing to act, or whatever. on the other hand, I may personally have a rather strong distaste for selected reviewing, but it does give a taker some- thing to crow about, that he was honoured to float this little package.... part of this is getting to the 'good-feeling' state where the CEO thinks he will be a hero. .Likewise, find a politically-sympathetic designer with access to IC .layout software, etc. that, and determining what form or methodology will optimize the design itself, are the two criticial first steps. until that is resolved, nothing should be done; and get a provisional layout before finding the big sponser. .The way I see it, there has to be a huge amount of .unused 0.5-0.7 micron IC capacity around the world. . yes, in older fabs. but the < 1u lines are loaded as of the August summary. .Remember, we're only .talking about a few hundred wafers. . the real issue is a working prototype --if it's ready to go, there should be no trouble persuading a fab to run a batch. I think the Tylan and Therm etchers are loading about 100 six inch wafers and eight inch may be on line. a six inch wafer has 27 sqin total and depending on the size of the individual .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. . 4500 machines for $1M per year power? .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. you wish to hand over the project to Billy? so all our good designers are shunted off into never-never land as Billy stands up in the spotlight and claims it was his brain, and the muscle he created in MicroSlop, who proved his boot sector virus and pretty programmer whupped the big bad government, who was trampling on our rights? "I, and I mean 'I and my billions,' solved this trivial DES problem, and I, and I mean 'I,' am the champion of your god given rights as promised in the Bill of Rights." count me out; Billy and Big Ears are a perfect pair, they think they walk on the same water! .How about Intel? well, at least Andy Grove would not pull a Bill Gates. however, Grove and company are very bottom line oriented and turn around has been proven to be pretty slow in most of their fab plants --but they have a special section of engineering knock-up. I believe both Silicon Gulch and Hillsboro have 'em. the real issue will be to find a reason for Intel to be able to mass produce the chip for something else --maybe use an FPGA type design, or a digital filtering processor architecture --easier to correct small mistakes, too. If the KISS principle is used exclusively, and mutiple step-and-repeats for the layouts, a large house like Intel could make real short work of it. one more round... --attila -- "I don't make jokes. I just watch the government and report the facts." --Will Rogers
participants (2)
-
attila -
jim bell