RC4 was initially a trade secret, but in September of 1994 an anonymous person reverse engineered it and posted it to the Cypherpunks mailing list. It quickly spread to Usenet on the sci.crypt newsgroup, and on to many sites on the Internet. Because the algorithm is known, it is no longer a trade secret. The name RC4 is trademarked. 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, used in secure network web browsers.
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 it 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 from memory. 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, Martin 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.
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 seriously non-random. As a result, it is possible to discover the RC4 key if one posesses 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.Fluhrer, Martin and Shamir Attack