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