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