Re: Distributed DES crack

[jim bell <jimbell@pacifier.com>]

At 04:34 PM 7/24/96 +0200, Remo Pini wrote:

>By the way, using FPGA's (as suggested earlier) at around 100 MHz should be
>extremely fast (after all, on one 100000 Gate FPGA, one should be able to 
>do lot of parallel things at one clock cycle -> test several keys at 
>once...).
>I estimate, that at reasonable cost (lets say, <$500) you should be able to 
>put enough FPGAs on a board to do enough keys in parallel to equal 1 key 
>per cycle, i.e. 1e8 keys/sec.

I'm skeptical of any attempt to use general-purpose computers to crack DES.  
For example, if you could get a Pentium-class system to try 100,000 keys per 
second, that's about 200 million machine hours for a total keyspace search. 
Even if the power consumption of the hardware was the only cost, and 
assuming you could get the consumption of an individual machine down to 100 
watts, that's 20 million kilowatt-hours  of electricity, or somewhere around 
$1.5 million at 7.5 cents per kwh.  That's not particularly promising.

However, assuming DES can be implemented by a number of 64-bit wide 
pipelined stages within a single chip, it should be possible to have that 
chip do a single key per clock cycle, perhaps at about 50 megahertz. (This 
would probably be trivial on a full-custom chip.  Whether it could be done 
straightforwardly on a hard-wired gate array, or a FPGA, I don't know.)   
Tiled on a pc board perhaps 10 by 10, it would check 5 billion keys per 
second.  This works out to 167 days to search the entire keyspace.  

Electricity consumption is almost ignorable:  Even if that 100-processor 
board consumed 1 kilowatt, that's still only 4000 kilowatt-hours, or $280 at 
7.5 c/Kwh.  The reason for this enormous difference (about 5000 to one) is 
mostly due to the fact that general-purpose computers are very inefficient 
at solving this problem, but also partly because a typcal Pentium-class 
computer keeps a large amount of circuitry powered up all the time, and not 
just the portion needed to solve a CPU-bound task.

Obviously, costs other than electricity are the dominant factor with a 
specialized-hardware approach.  But the only attraction of the farmed-out 
(borrowed) general-purpose CPU approach is the fact that the computers are 
already paid for, and the elctricity will be paid for by somebody else.  
Once the average participant realizes how wasteful this solution is, he will 
likely balk.  It would be far more economical to take 10% of that 
electricity cost (possibly in the form of donations), maybe around $150,000, 
and build the custom hardware that could be used again and again.









Jim Bell
jimbell@pacifier.com