Re: Paranoid Musings

[frantz@netcom.com (Bill Frantz)]

I'm really feeling much better now :-).

At  6:48 PM 7/30/96 -0400, Mark M. wrote:
>On Tue, 30 Jul 1996, Bill Frantz wrote:
>> The paranoid conclusion is that there is a significant weakness in RC4.
>
>An FPGA can break RC4 in a few hours.  With several thousand of these, RC4
>could be broken in about a second.  Besides, RC4 has been around for 9 years
>and has not been successfully cryptanalyzed.  The RC4 algorithm is extremely
>simple and doesn't have any obvious weaknesses.

IMHO, NSA's cryptanalysis is second to none.  I have been assuming a
weakness based on a classified cryptanalysis technique.  They have
certainly been thinking about "S-Box" cyphers since at least Lucifer and
DES.  But let's approach the question from a different angle.  Consider the
number of messages that need to be broken and the costs of machines to do
it.

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.

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

>The factors not accounted for are:
>
>  o Memory costs are not included.
It needs to store all the messages it is attacking.

>  o When get [sic] to the very fast processing speed estimates,
>    machines can become Input/Output bound; so [sic] it cannot achieve
>    the estimated speed.
It needs to get all those messages into the machine, the plaintext out, and
distribute the data to the FPGAs.

>  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.

>  o R&D costs for the first machine, typically on the order of $10
>    million.
R&D costs for high-speed I/O, large memories, and efficient heat removal
might be significant.

>  o Assuming every algorithm can be tested in same amount of time and
>    key length is the only difference.
This is one of Blase et. al.'s simplifying assumptions.  RC4 has a simple
key setup and runs faster than DES.  Brute forcing 40 bit Blowfish would be
considerably harder.  Probably about equal to 9 additional key bits harder.


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.


-------------------------------------------------------------------------
Bill Frantz       | Cave ab homine unius lebri | Periwinkle -- Consulting
(408)356-8506     |  [Beware the man of one    | 16345 Englewood Ave.
frantz@netcom.com |   book]  - Anonymous Latin | Los Gatos, CA 95032, USA