Quantum Ecomomics

A. Padgett Peterson P.E. Information Security (PADGETT@hobbes.orl.mmc.com)
Tue, 19 Mar 1996 21:15:37 -0500 (EST) 

I rote:
> Would like to talk for a minute about "costs". The cost to break 40 bits 
> is known: three and a half hours (on the average) with a purpose built
> machine. In dollars, the figure $500 has been mentioned. So for any
> message worth less than $500, 40 bits is "enough".
Don wresponded:
:See <http://www.bsa.org/bsa/cryptologists.html>, co-authored by Ron Rivest. 
:It concludes that while a "pedestrian hacker" using a borrowed workstation
:might take a week to crack 40 bits (and it gives no estimated cost for this),
:someone willing to spend around $500 could use off the shelf prgrammable
:chips to break 40 bits for an amortized cost of 8 per key.  And if you were
:really willing to spend some money, like a few hundred thousand dollars, and
:go for custom designed chips and had enough cracking to keep them busy, the
:cost per broken key drops to a tenth of a cent. 

Evidently either I need to be taught to apply a vacuum to the shells of avian
embryos or you are missing a few things. I do not think this group needs
a discusion of the speeds/costs or PLADs and ASICs. Am familiar with the
paper by the "MIT Seven". Already reveiwed it extensively (ask Matt)
and found it a bit flawed.

Several years ago I began discussing the virtues of "single bit cascadable
boolean processors" and alternate uses of DSP. State of the art today
for a purpose-built seive is 150 Mhz (up from 40 Mhz a few years ago).

The keyspace for 40 bits is 2^40 and will break in an average of 2^39
trials which would take such a device about an hour. To break larger keys
or to break it faster would require many such devices in parallel.

What Matt & friends (are any an EE ?) hypotesized was that this seive could
be put on a single chip and thousands could run in parallel. AFAIR they
decided that the chip could be built (true but the engineering would
be significant, PLADs and ASICs do not support that kind of density/speed
so it would have to be a custom VLSI design *for 40 bit RC4 only* (every
diffet cypher/speed would need its own) and they are not cheap) for about
$10.

Next, nothing was allocated for the support circuitry. Not as complex as a
massively parallel device, but still significant. Nor was any time/effort
spent to address programming/solution retrieval.

Finally, no effort was made to determine when a solution was found. True
most cryptographers assume "known plaintext". Fine except good mail
systems use a different key for every message. If every message (or
a good proportion always started the same way, fine. If not, welllllll.

						Warmly,
								Padgett