For the Vietnam road named RC4, see Route Coloniale 4.

In cryptography, RC4 (or ARCFOUR) is the most widely-used software stream cipher and is used in popular protocols such as Secure Sockets Layer (SSL) (to protect Internet traffic) and WEP (to secure wireless networks). RC4 falls short of the high standards of security set by cryptographers, and some ways of using RC4 lead to very insecure cryptosystems (including WEP). It is not recommended for use in new systems. However, some systems based on RC4 are secure enough for practical use.

History

RC4 was designed by Ron Rivest of RSA Security in 1987; while it is officially termed "Rivest Cipher 4", the RC acronym is alternatively understood to stand for "Ron's Code" (see also RC2, RC5 and RC6).

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.

Description

RC4 generates a pseudorandom stream of bits (a "keystream") which, for encryption, is combined with the plaintext using XOR as with any Vernam cipher; decryption is performed the same way. To generate the keystream, the cipher makes use of a secret internal state which consists of two parts:

1. A permutation of all 256 possible bytes (denoted "S" below).
2. Two 8-bit index-pointers (denoted "i" and "j").

The permutation is initialised with a variable length key, typically between 40 and 256 bits, using the key-scheduling algorithm (KSA). Once this has been completed, the stream of bits is generated using the pseudo-random generation algorithm (PRGA).

The pseudo-random generation algorithm (PRGA)

The lookup stage of RC4. The output byte is selected by looking up the values of S(i) and S(j), adding them together modulo 256, and then looking up the sum in S; S(S(i) + S(j)) is used as a byte of the key stream, K.

For as many iteration as are needed, the PRGA modifies the state and outputs a byte of the keystream. In each iteration, the PRGA increments i, adds the value of S pointed to by i to j, exchanges the values of S[i] and S[j], and then outputs the value of S at the location S[i] + S[j] (modulo 256). Each value of S is swapped at least once every 256 iterations.

 i := 0 j := 0 while GeneratingOutput: i := (i + 1) mod 256 j := (j + S[i]) mod 256 swap(S[i],S[j]) output S[(S[i] + S[j]) mod 256] 

The key-scheduling algorithm (KSA)

The key-scheduling algorithm is used to initialise the permutation in the array "S". "l" is defined as the number of bytes in the key and can be in the range 1 ≤ l ≤ 256, typically between 5 and 16, corresponding to a key length of 40–128 bits. First, the array "S" is initialised to the identity permutation. S is then processed for 256 iterations in a similar way to the main PRGA algorithm, but also mixes in bytes of the key at the same time.

 for i from 0 to 255 S[i] := i j: = 0 for i from 0 to 255 j := (j + S[i] + key[i mod l]) mod 256 swap(S[i],S[j]) 

Implementation

Many stream ciphers are based on linear feedback shift registers (LFSRs), and, while efficient in hardware, are much slower in software. The design of RC4 is quite different, and 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-1], and integer variables, i, j, and k. Performing a modulus 256 can be done with a bitwise AND with 255 (or on some platforms, simple addition of bytes ignoring overflow).

Security

RC4 falls short of the standards set by cryptographers for a secure cipher in several ways, and thus is not recommended for use in new applications.

The keystream generated by RC4 is slightly biased in favour of certain sequences of bytes. The best attack based on this bias is due to Fluhrer and McGrew, which will distinguish the keystream from a random permutation given a gigabyte of output.

RC4 does not take a separate nonce alongside the key. As with any cipher, but particularly with Vernam ciphers, such a nonce is a requirement for security, so that encrypting the same message twice produces a different ciphertext each time. A secure solution to this that works for any secure cipher is to generate each RC4 key by hashing a long-term key with a unique nonce using a construction such as HMAC. However, many applications that use RC4 simply concatenate key and nonce; RC4's weak key schedule then gives rise to a variety of serious problems.

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, leaking information about the key. If the long-term key and nonce are simply concatenated to generate the RC4 key, this long-term key can be discovered by analysing 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. 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.

This attack does not apply if the first 1024 bytes of the keystream are discarded before use.

References

• Scott R. Fluhrer, Itsik Mantin and Adi Shamir, Weaknesses in the Key Scheduling Algorithm of RC4. Selected Areas in Cryptography 2001, pp1–24 (PS) (http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Rc4_ksa.ps).
• Scott R. Fluhrer and David A. McGrew, Statistical Analysis of the Alleged RC4 Keystream Generator. FSE 2000, pp19–30 (PDF) (http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/FluhrerMcgrew.pdf).
• Jovan Dj. Golic, Iterative Probabilistic Cryptanalysis of RC4 Keystream Generator. ACISP 2000, pp220–233
• Jovan Dj. Golic, Linear Statistical Weakness of Alleged RC4 Keystream Generator. EUROCRYPT 1997, pp226–238 (http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Golic.PDF PDF).
• Lars R. Knudsen, Willi Meier, Bart Preneel, Vincent Rijmen and Sven Verdoolaege, Analysis Methods for (Alleged) RC4. ASIACRYPT 1998, pp327–341 (PS) (http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/Knudsen.ps).
• Itsik Mantin and Adi Shamir, A Practical Attack on Broadcast RC4. FSE 2001, pp152–164 (PS) (http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/bc_rc4.ps).
• Serge Mister and Stafford E. Tavares, Cryptanalysis of RC4-like Ciphers. Selected Areas in Cryptography 1998, pp131–143
• Ilya Mironov, (Not So) Random Shuffles of RC4. CRYPTO 2002, pp304–319
• Souradyuti Paul and Bart Preneel, Analysis of Non-fortuitous Predictive States of the RC4 Keystream Generator. INDOCRYPT 2003, pp52–67
• Souradyuti Paul and Bart Preneel, A New Weakness in the RC4 Keystream Generator and an Approach to Improve the Security of the Cipher. FSE 2004, pp245–259

External links

RC4

• IETF Draft - A Stream Cipher Encryption Algorithm "Arcfour" (http://www.mozilla.org/projects/security/pki/nss/draft-kaukonen-cipher-arcfour-03.txt)
• Original 1994 usenet post of RC4 (http://groups.google.com/groups?selm=sternCvKL4B.Hyy%40netcom.com)
• SCAN's entry for RC4 (http://www.users.zetnet.co.uk/hopwood/crypto/scan/cs.html#RC4)
• Attacks on RC4 (http://www.wisdom.weizmann.ac.il/~itsik/RC4/rc4.html)
• RC4 - Cryptology Pointers by Helger Lipmaa (http://www.tcs.hut.fi/~helger/crypto/link/stream/rc4.php)
• RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4 (http://www.rsasecurity.com/rsalabs/node.asp?id=2009)

RC4 in WEP

• (in)Security of the WEP algorithm (http://www.isaac.cs.berkeley.edu/isaac/wep-faq.html)
• Fluhrer, Mantin, and Shamir attack on WEP (postscript format) (http://www.wisdom.weizmann.ac.il/~itsik/RC4/Papers/rc4_wep.ps)

Implementations

• CipherSaber, an easy to implement RC4 encryption system (http://ciphersaber.gurus.com)
• An optimized RC4 implementation in C (full source code and test vectors) (http://www.cr0.net:8040/code/crypto/rc4/)
• An optimized RC4 implementation for AMD64 (http://etud.epita.fr/~bevand_m/papers/rc4-amd64.html)