RC4 cipher

RC4 is a symmetric key[?], secret key, stream cryptographic cipher designed by Ron Rivest. RC apparently stands for "Ron's Code". Also publicly known are the block ciphers RC2 and RC5, and the block cipher RC6 which he designed with others. RC4 was designed sometime in the 1990s.

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 can't 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 SSL, that is used for secure network web browsers.

RC4 is initialised from a secret key. Then it generates a "keystream" which is simply XORd with the plaintext to produce the ciphertext. Decryption is exactly the same as encryption. One reason for its popularity is its simplicity. The algorithm can be memorized and quickly implemented from memory. It uses 256 bytes of memory, S[0] through S[255], and it uses integer variables, i, j, and k. A message is encrypted or decrypted with this algorithm:

    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] and S[j]
    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] and S[j]
        k=S[(S[i]+S[j]) mod 256]
        output the XOR of k with the next byte of input

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

Cryptanalysis of RC4 is at a rather uncertain stage. 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 byte of output keystream are seriously non-random. This and related effects were then used to break the WEP encryption used with 802.11 wireless networks. WEP employed RC4 with many similar keys, opening it to attack. Current implementations often 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.