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