From: Matt Blaze <mab@crypto.com>
Date: Wed, 24 Jul 1996 08:06:06 +0800
To: perry@piermont.com
Subject: Re: Distributed DES crack
In-Reply-To: <199607231331.JAA15803@jekyll.piermont.com>
Message-ID: <199607231412.KAA14573@crypto.com>
MIME-Version: 1.0
Content-Type: text/plain


Perry writes:
> 
> I'm not entirely sure. It is certainly bigger than the factorings that
> have been done, but on the other hand it is fairly easy to put
> together the experiment, and there are an awful lot of idle machines
> out there in the world. I have on several occassions been in
> possession of four or five hundred idle CPUs at night, and I am pretty
> sure that other people are in that position. The net has also grown
> quite dramatically in recent years, and reaching 100,000 reasonably
> high speed machines might not be so hard these days. At that point, it
> becomes a question of how fast one can get the DES cracker. A constant
> factor of two or three then makes a considerable difference in the
> outcome, as does the user friendlyness of the overall system.
> 
Here are my back-of-the-calculator numbers:

2^55 = 3.6 * 10^16 trial ecb operations (+key setup).
Best P-100 DES software implementation I can find can do 110000 ECBs/sec.
Key setup takes about twice as long as a single ECB.
Assuming amazingly fast key setup and careful ECB optimization
(precompute IP and FP, gray coded key enumeration with cached round results,
etc), MAYBE, somehow, you could do 100000 ECB/sec on "average" workstation
(average = 100mhz Pentium).

That's 11000 Pentium-100 years for half the DES keyspace.  

> > Personally, I'd rather someone finish up the Wiener ASIC to the point where
> > it could go out to fab, get some prototype chips made, design a board around
> > it, and publish the design, from board layout on down.  This would be a
> > great Master's project, and some of us (maybe me, but I'll have to check)
> > might even be able to scrape up enough funds to buy enough chips/boards/etc
> > to build a modest size machine (say, that could exhaust a DES key in 1-6
> > months).  Initial engineering costs aside, the marginal cost of each
> > such machine could be well within the budgets of, say, a medium size crypto
> > research lab, and would make a scary enough demo to convince even the
> > most trusting management types of the risks of 56 bit keys.
> 
> Well, that would certainly be cool, but this does require real
> money. If you are willing to spend it, go for it, but I'm not sure we
> can count on people doing that sort of thing. What do you suppose the
> odds are that someone is going to build such a thing any time soon?
> 

Well, I'm working on getting the funds to build (or support someone
to build) some kind of parallel DES engine.  I can probably scrape
together an FPGA-based machine that can do a key in less than 6 months.
I'm very serious about this project, but I can't say for sure when or if
I'll be ready to start.

-matt