Steve Bellovin refers to Hans Eberle's paper on a GAs-based 1Gb/s DES chip, which is available on gatekeeper.dec.com under the SRC directory. The search time of 16 days for $1M, aka 1 day for $30M (incl. support chips), is fairly similar to Peter Wayner's Content-Addressible-Memory approach, which would cost an estimated $30M for a 1 day search. (Average search time is about half as long as exhaustive searches.) To put this in a cost-per-solution context, if you amortize over 5 years, that's about 4000 solutions, so that's a bit under $10K per solution. It's more expensive than David Sternlight's $25/solution guess, but it's interestingly small - certainly worthwhile for occasional national security applications, or robbing electronic funds transfer networks, (at least for the $1M slower version), and it's in the ballpark of the rental rate for Congressmen :-) (the Abscam folks paid $50K to Senator Harrison Williams for some light work...) Since Skipjack uses an 80-bit key, the NSA or other rich organizations with access to it ought to be able to get similar performance in 24-48 years, assuming speed doubling continues at its 1-2 year rate. We'd be better off with something with a longer key, such as triple-DES. Bill Stewart
To put this in a cost-per-solution context, if you amortize over 5 years, that's about 4000 solutions, so that's a bit under $10K per solution.
Here are a few assumptions that lower this estimate for the NSA. -- The NSA has it's own fab and design facilities. If you assume you want a few dozen or hundred DES cracking boxes, you can afford a fair bit of money on design; the design cost per chip drops. The more of these you have, the lower the cost per solution. -- The amortization period is longer than 5 years. From what I have heard, the NSA just keeps running most every machine it owns. -- The possibility of a trap door which gives hints about exhaustive search should not be ruled out. Suppose, for example, that all combinations of 16 bits exhibited flat distribution as 16-grams, but that certain combinations of 22 bits did not. Just to find these correlations might be an infeasible problem, but to exploit them would not be. Drop your cost estimates by 2^6 in the above example if true. -- There will be different machines designed for attacks on different types of intercepts. Known plaintext, probable plaintext, known ASCII, etc. The recognition circuitry on each of these is different and custom design would reduce silicon costs significantly. -- If you use micropipelines, you can keep the encryption circuitry constantly full, as opposed to putting in a new value after the old one pops out. If this technique is not already being used, divide cost by 16, the number of rounds of DES. -- One can design circuitry to test multiple ciphertexts on the same key at some savings in chip cost. Not useful for encryption, but useful for cracking. Call this a factor of 1.5 to 2. -- Wafer scale integration could yield some savings in die cost and packaging. Eric
participants (2)
-
Eric Hughes -
wcs＠anchor.ho.att.com