From: Matt Blaze <mab@crypto.com>
Date: Tue, 23 Jul 1996 20:31:20 +0800
To: cypherpunks@toad.com
Subject: Re: Distributed DES crack
In-Reply-To: <Pine.A32.3.93.960722174148.48340B-100000@navajo.gate.net>
Message-ID: <199607230422.AAA09435@crypto.com>
MIME-Version: 1.0
Content-Type: text/plain


I don't want to throw water over what I think would be a very useful
thing to have done, but I'm really skeptical that current "net"
computing power with general purpose processors is up to this.

My back of the envelope calculation, making some generous assumptions
about the implementation, suggests that such an effort would require
somewhere in the range of 10,000 and 50,000 CPU years on general (100MHz
or so Pentium) processors.  This is well beyond any distributed computation
I'm aware of ever having been done, even adjusting for "Moore inflation".
While feasible in a "complexity theory" sense, it's really not realistic
yet.

Even if it were feasible, what would we use as a challenge key?

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.

-matt

(Please cc me on replies, as I'm not reading the list except when someone
alerts me to an interesting topic.  Thanks.)
> 
> I've a few machines around that could be dedicated almost full time to the
> task. What are the bandwidth requirements? Specifically, could the
> keycracker be run over a 28.8 (with a 486 running linux)?  If so, how many
> 486's could I get over a single 28.8 (i.e. 28.8 -> multiple 486's daisy
> chained with ppp over direct serial connection)?
> 
> --nc
> 
> On Mon, 22 Jul 1996, Perry E. Metzger wrote:
> 
> > 
> > Perhaps a Java page containing a DES cracker that one could run for
> > the casual participant, and a set of links to download a real cracker
> > for the non-casual participant...
> > 
> > I think its really time that we did this. DES must be shown to be
> > dead.
> > 
> > When the media hear about it, they will, of course, get "experts"
> > saying "but it took five thousand people millions of dollars in
> > computer time". We should ask Matt Blaze to write a paper in advance
> > explaining that although this test, on general hardware, took a lot of
> > effort, that with specialized hardware it would be cheap as can be.
> > 
> > Perry
> > 
> > Paul Foley writes:
> > > "Peter Trei" <trei@process.com> wrote:
> > > 
> > >    Any one up for a distributed brute force attack on single DES? My 
> > >    back-of-the-envelope calculations and guesstimates put this on the
> > >    hairy edge of doability (the critical factor is how many machines can
> > >    be recruited - a non-trivial cash prize would help). 
> > > 
> > > Not quite sure what you mean by "doability" -- it's obviously doable,
> > > it just depends how long you want to wait.
> > > 
> > > I'm in.
> > 
>