FPGAs and Heat (Re: Paranoid Musings)

[tcmay@got.net (Timothy C. May)]

At 5:05 AM 7/31/96, Bill Frantz wrote:
>I'm really feeling much better now :-).

I guess Ritalin really does work.


>How many encrypted messages do you think NSA wants to read?  I have no idea
>either, but in the spirit of never depend on expert opinion when simple
>arithmetic will do, let's assume a world where major email packages use
>encryption as a matter of course.  If we assume that the 30 million net
>users send one email/day, then that results in about 350/second.  If I
>assume your "several thousand" is 2000, then we need a machine with 700,000
>FPGA's.  Given Matt Blaze et. al.'s estimate of $10/chip complete, that is
>$7 million.  However if you take the NSA's estimate (in their response to
>Blaze et al) of $1000/chip, then you get $700 million.

I for one don't have any way of estimating how many messages they might
want to read. But note some figures we've discussed here before:

* NSA spent upwards of $100 M to build the "Harvest" machine in the late
50s and early 60s (you worked with Norm Hardy, Bill, so you undoubtedly
know about this). Some of this machine's capacity was for cryptanalysis,
some for voice analysis, and no doubt a lot for other things. But it says
something about the kinds of money that will be spent.

* Spysats routinely cost a billion dollars or more. (A single launch of the
space shuttle costs at least $500 M, as I recall. Some shuttle launches
have been to deploy SIGINT sats.)

* The NSA was one of the main investors in several high tech companies,
including Control Data Corporation and Cray Research.

I conclude, roughly speaking, that spending $100 M on a specialized machine
to break RC4 or any other modern cipher (that is breakable at the key
lengths used) would not even give them pause.

>If we assume a machine designed to break *every* message, NSA's response
>makes more sense.  From their response (reordered):

I don't believe that even _they_ would plan for something like this, unless
RC4 is a lot weaker than experts seem to think it is.

[stuff elided]

>>  o As more and more chips are added to a machine, two effects occur:
>>
>>      o Interconnections increase and increase running time;
>>      o Heat from the chips eventually limit [sic] the size of a
>>        machine.
>Fast machines produce a lot of heat.

But, as many have pointed out, this is not a realistic limit. The pieces of
the solution could be scattered from one end of Fort Meade to another, and
still not be affected much by communications costs and delays. Power
density is thus not going to be a problem. (A calculation can be done on
how long it will take before electricity costs exceed chip costs...I
haven't done this for the crypto FPGAs, as so many things are unclear about
what they might be, but for the 200 MHz Pentium (CPU alone, not a system) I
get: 40 kilowatt-hours per year x $0.10 per KWH = $4 per year in
electricity costs. Heat removal costs are comparable.)

FPGAs and custom chips will not be much different. I conclude that the
costs of building the chips and system will be orders of magnitude more
expensive than the costs of running the chips with power, and that removing
the heat is not an issue. (Spread out enough, simple heat removal a la
office computers is fine. Leaving windows open is even cheaper ;-))


>Now I have no problem with believing NSA would invest $7 million.  However,
>$700 million makes me wonder.  With FPGAs, there is a significant risk that
>people will change the crypto system and make the investment worthless.
>(Which, I guess, is why they prefer general purpose computers.)  However,
>if they can get the equivalent of a few bits of key back by cryptanalysis,
>then they knock the costs down to entirely reasonable (for them) levels.

An FPGA is field-programmable. (FPGA = Field Programmable Gate Arrays) The
Xilynx and Altera lines of FPGAs could be reconfigured for other
algorithms, surely. (I recall several preliminary designs discussed in
various places.)

This doesn't mean they've done it, only that they could buy millions of
FPGAs for the cost of a single spysat or shuttle launch. So, it seems
likely.

--Tim May



Boycott "Big Brother Inside" software!
We got computers, we're tapping phone lines, we know that that ain't allowed.
---------:---------:---------:---------:---------:---------:---------:----
Timothy C. May              | Crypto Anarchy: encryption, digital money,
tcmay@got.net  408-728-0152 | anonymous networks, digital pseudonyms, zero
W.A.S.T.E.: Corralitos, CA  | knowledge, reputations, information markets,
Licensed Ontologist         | black markets, collapse of governments.
"National borders aren't even speed bumps on the information superhighway."