Re: Distributed DES crack

["Perry E. Metzger" <perry@piermont.com>]

Matt Blaze writes:
> 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.

I think it is a stretch, admittedly, but that it can be done, and most
importantly, it can be done nearly for "free".

> 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.

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.

> 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?

Perry