Re: fast des

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