# RC4 Keylength Limits

While reading the Wiki page on RC4 I noticed that the key size must be in the range of 40–2,048 bits.

Why is that? Is there a reason it can't have a lower or higher length?

-

The minimum of 40 bits is conventional; below 40 bits of key material, RC4 (or practically any cipher without some built-in key stretching) is just too unsafe.
At some point in history, in many countries, ciphers with a key above 40 bits where illegal in some usage (in USA: export; in France: use, sale, export); thus cipher designers wanting to prescribe something as secure as possible often used that 40-bit limit.

The maximum of 2048 bits is a consequence of RC4's key scheduling. Quoting Wikipedia's page on RC4

for i from 0 to 255
S[i] := i
endfor
j := 0
for i from 0 to 255
j := (j + S[i] + key[i mod keylength]) mod 256
swap values of S[i] and S[j]
endfor


We see that 256 passes are made, and each pass manipulates 8 bits of key; above $8\cdot256=$ 2048 bits, extra key material would be ignored.

Anyway, array S[] remains a permutation of 256 distinct values, hence can hold a maximum of $\log_2(256!)\approx$ 1684 bits of entropy, and that key size limit of 2048 bits is only a practical issue when the key is not truly random in the first place.

In order to strengthen RC4 against weakness in its key scheduling / setup (leading e.g. to break of WEP encryption), it is advisable to stretch the size of the key material (e.g. to the maximum of 2048 bits) using a pseudo-random transformation (alternatively, or in combination, the first 256 or 512 bytes generated can be discarded). And if the original key is low-entropy (e.g. a password), it must be strengthened by a slow key derivation function in order to resist brute-force password cracking. Both can be done using scrypt with dkLen=256, and other parameters set as appropriate for the environment.

-
Thanks @fgrieu. What weaknesses are there in the key scheduling algorithm of RC4? –  Andrew Jones Jul 4 '12 at 16:45

To add to what fgrieu said, think of RC4 as a self-modifying rotor. Imagine a wheel with little tiles on it like Scrabble tiles, but labeled 0x00 to 0xff (or 0 to 255). Each time you crank out a value, you flip some tiles on the rotor and ratchet it one place.

You initialize the wheel by spinning it completely once, using your key as values to control how tiles get flipped around. 2048 bits is rotating the wheel a complete revolution and using your own control bits on every click of the wheel.

You could obviously do it with any size control string (key), but it obviously has much less value to do it more than one complete revolution. So just as by convention there's a minimum of 8 bytes (40 bits) of key, there's a max of 256 bytes.

We call RC4's initialization a "key schedule" but it isn't a key schedule the way that a key schedule is done for a block cipher. Typically a block cipher has a number of sub-keys that are mixed in as the cipher runs and the sub-keys are derived from the base key, and that's what we call a key schedule. RC4 has an initialization -- the rotor is initialized and then you just run it like a pseudo-random number generator and XOR those onto the plaintext.

RC4 has a weakness that the initialization is weak. The typical suggestion to strengthen it is to generate N (usually 256 or 512) bytes of the stream and throw them away. That's turning the rotor once or twice, just to mix it up more.

WEP used RC4 in a spectacularly bogus way, but that's a completely different discussion, because one of the things WEP should not have done was to use a stream cipher at all. Stream ciphers follow the model of creating a PRNG and then XORing against plaintext. If you use the same stream on every packet (which WEP did), then if you have known plaintext, you can derive the key stream byte, and then decrypt that byte on every packet that ever follows. You then just make guesses about the rest of the plaintext to get the whole of the stream.

You should never, ever, ever use the same key twice on any stream cipher. Not RC4, not a block cipher with counter mode, nothing. This attack framework (use known plaintext to guess key stream bytes, and then guess more plaintext) works for any stream cipher with any size key.

While I'm at it, RC4 has lots of little holes. It's not so bad that you should rip it out of a place where it is being used (and there are places where the alternatives have their own problems), but in a new project, you should do something like counter mode that has better properties.

Nonetheless, RC4 is in my opinion, perhaps the most beautiful cipher ever made, and I have a fondness for it. I understand liking it because it's so pretty.

Jon

-