[182] in cryptography@c2.net mail archive
Re: 40-bit rc2/4
daemon@ATHENA.MIT.EDU (Arnold G. Reinhold)
Thu Feb 6 14:33:38 1997
In-Reply-To: <3.0.32.19970205165952.006f0734@192.100.81.136>
Date: Thu, 6 Feb 1997 14:26:26 -0400
To: Lucky Green <shamrock@netcom.com>
From: "Arnold G. Reinhold" <reinhold@world.std.com>
Cc: cryptography@c2.net
>At 01:32 PM 2/5/97 -0800, Steve Reid wrote:
>>I don't know about RC2, but implementing an RC4 cracker in hardware is
>>said to not work very well (compared to DES, for example) because the
>>algorithm was designed to be efficient in software.
>
>It is my understanding that the authors of the RC4-in-hardware paper didn't
>have enough chip real estate to effectively work on RC4. I doubt the NSA
>has a similar problem.
>
>
A while ago, I did a back-of-the envelope design of a hardware N/128-bit
RC4 cracker using the same ASIC cells that Michael Wiener employed in his
paper, "Efficient DES Key Search." N/128-bit RC4 means RC4 with a 128 bit
random key, all but N bits of which are revealed. 40/128-bit RC4 is used in
SSL, for example. True 40 bit RC4 is MUCH weaker since you can test many
cipher text/plain text pairs for each key setup. True 40 bit RC4 is also
subject to code-book attack -- in milliseconds -- with a large, dedicated
disk farm (10,000 Gigabytes).
In my design, almost all the time goes into RC4's key setup stage
(building the 256 byte S-array) and almost all the chip real estate goes to
storing that array. I came up with a multiport memory that initializes the
S-array to [0-255] in parallel and lets the 256 permutations required to
build the S-array take place at one cycle per step. Once the S-array is
complete, most keys are rejected after a single byte of plain text and
cipher text are tested.
The size of my chip came out about the same as Wiener's DES chip, but it
requires about 259 cycles to test one key, vs. one cycle per key in
Wiener's pipelined DES design. This assumes comparable chip cycle times,
but I have not done any timing analysis (I am not an EE).
Therefore, I estimate that RC4 has about an 8 bit key length advantage over
DES in resistance to brute force attack using special purpose hardware.
That is, a 56 bit DES key is about as resistant as a 48/128 bit RC4 key to
exhaustive hardware key search.
By allowing 56 bit DES for export, the USG gives us a factor of 256
improvement over 40/128-bit RC4, not the 16,384 one might assume.
Arnold Reinhold
