RC4 (cipher)

This page is about the encryption algorithm. For the Vietnam road named RC4, see Route Coloniale 4.

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 and WPA 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 for the state array, S[0] through S[255], n bytes of memory for the key, key[0] through key[n], and integer variables, i, j, and k. n is defined as the number of bytes in the key and can be in the range 1 ≤ n ≤ 255, though for common applications, n = 8 or 16 is common (64 and 128 bits, respectively).

The RC4 algorithm consists of two parts, the first being the Key Setup Algorithm (KSA), which uses the key to initialize the pseudo-random number generator:

The following is wikicode, a proposed pseudocode for BambooWeb articles.

Once the generator has been initialized, both encryption and decryption are performed using values output from the generation stage. This process, called the Pseudo-Random Generation Algorithm (PRGA), is as follows:

Note that it is strongly recommended that the first outputs of this generator be discarded and not used to encrypt messages (at least 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 and WPA.

One way to avoid these problems is to discard the first 256 bytes or more of the RC4 cipher stream.

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.