Re: Paranoid Musings
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
In article <199607310502.WAA09812@netcom7.netcom.com>, Bill Frantz <frantz@netcom.com> wrote:
At 6:48 PM 7/30/96 -0400, Mark M. wrote:
An FPGA can break RC4 in a few hours.
I don't think so. None of the FPGAs Ian & I looked at could even approach the RC4-cracking performance of a fast Intel CPU.
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.
Those estimates assume that a single FPGA can break RC4 in hours. I think that is an extremely optimistic assumption, given the available public information. But perhaps NSA is orders of magnitude ahead of us in chip design (unlikely) or orders of magnitude ahead of us in RC4 cryptanalysis (and we're back to paranoid musings).
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.
Naw, this is orthogonal to the cost of cryptanalysis-- even when all messages are sent in the clear, they still need this storage. I would be willing to believe that message selection & storage is a very expensive part of SIGINT. However, if one has the resources to break all encrypted messages in realtime, I don't see why message selection & storage costs need to increase so significantly.
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.
Nope, I don't buy it. Show me a chip takes longer to load a known plaintext and ciphertext pair than it takes to do a 40-bit exhaustive keysearch for that pair, and I'll show you a chip that has no I/O pins. :-) Remember, if you have a million FPGAs to crack a thousand messages, you don't have to send the first message to all million FPGAs, then send the second message to all million FPGAs, etc. Instead you should send the first message to the first thousand FPGAs, and concurrently send the second message to the second thousand FPGAs, etc.
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.
I agree that key schedule complexity can have a significant influence on the complexity of exhaustive keysearch. However, DES's key schedule is actually much better suited to exhaustive keysearch than RC4's key schedule is. (I speak with implementation experience. However, it's not too hard to see why this should be true-- DES was designed for implementation in hardware, and its keyschedule consists merely of some bit permutations, which are free in hardware. RC4 uses RAM heavily, and thus can incur large I/O costs, and also is highly serialized, so it is not so well-suited to efficient hardware implementation.) Yup, brute-forcing 40-bit Blowfish will probably be even harder than RC4.
With FPGAs, there is a significant risk that people will change the crypto system and make the investment worthless.
No, FPGAs are programmable logic, and thus can be easily reprogrammed if the Netscape default encryption algorithm changes. Perhaps you are thinking of ASICs, which have their logic burned in, and cannot be changed.
participants (2)
-
daw＠cs.berkeley.edu -
frantz＠netcom.com