RC4 (cipher)

In cryptography, RC4 (or ARCFOUR) is a symmetric key stream cipher designed by Ron Rivest of RSA Security in 1987. Though RSA officially terms it "Rivest Cipher 4", the RC acronym is generally understood to stand for "Ron's Code". Also publicly known are his block ciphers RC2 and RC5, and the block cipher RC6 which he designed with others.

RC4 was initially a trade secret, but in September 1994 a description of it was anonymously posted to the Cypherpunks mailing list. It was soon posted on the sci.crypt newsgroup, and from there to many sites on the Internet. Because the algorithm is known, it is no longer a trade secret. The name "RC4" is trademarked, however. The current status seems to be that "unofficial" implementations are legal, but cannot use the RC4 name. RC4 is often referred to as "ARCFOUR", to avoid possible trademark problems. It has become part of some commonly used encryption protocols and standards, including WEP for wireless cards and SSL..

RC4 is a stream cipher. Like many such ciphers, it is essentially a pseudo-random number generator initialized from a secret key of up to 256 bytes. The RC4 algorithm generates a "keystream" which is simply XORed with the plaintext to produce the ciphertext stream. Decryption is exactly the same as encryption. One reason for the algorithm's popularity is its simplicity. The algorithm can be memorized and quickly implemented. Additionally, it is ideal for software implementations, as it requires only byte-length manipulations. It uses 256 bytes of memory, S[0] through S[255], and integer variables, i, j, and k.

The RC4 algorithm consists of an initialization stage, which uses the key to initialize the pseudo-random number generator:

   for i = 0 ... 255

       S[i] = i

   for i = 0 ... 255

       j = (j + S[i] + key[i mod key_length]) mod 256

       swap (S[i],S[j])

Once the generator has been initialized, both encryption and decryption is performed using values output from the generation stage. The process of encryption and decryption is as follows:

   i = 0

   j = 0

   loop until the entire message is encrypted/decrypted

       i = (i + 1) mod 256

       j = (j + S[i]) mod 256

       swap(S[i],S[j])

       k = S[(S[i] + S[j]) mod 256]

output the XOR of k with the next byte of input

Note that it is strongly recommended that the first outputs of this generator be discarded and not used to encrypt messages (256 discards are recommended for maximum security.) Failure to do so can expose messages to an attack in which the RC4 key can be exposed (see "Fluhrer, Mantin and Shamir Attack" below).

RC4 is one of the fastest ciphers to be widely used for serious work.

Cryptanalysis of RC4 is at a rather uncertain stage. When correctly used, theoretical breaks may be possible if gigabytes of known plaintext/known ciphertext stream are available, but this is not necessarily a major problem in practice.

Fluhrer, Mantin and Shamir Attack

In 2001 a new and surprising discovery was made: over all possible RC4 keys, the statistics for the first few bytes of output keystream are strongly non-random. As a result, it is possible to discover the RC4 key if one possesses a large number of messages encrypted with this key. This and related effects were then used to break the WEP ("wired equivalent privacy") encryption used with 802.11 wireless networks. WEP employed RC4 with many similar keys, opening it to attack. This caused a scramble for a standards-based replacement for WEP in the 802.11 market, and led to the IEEE 802.11i effort.

Most other current implementations of RC4 discard the first 256 bytes or more of the stream to avoid these problems.

As with all stream ciphers, RC4 is easily broken if the same key is used twice. This problem is usually solved by hashing the key with a unique initialization vector (IV) each time it is used, and sending the IV along with the message.

RC4 (cipher)

Fluhrer, Mantin and Shamir Attack

External links