2.1 The pseudo-random generation algorithm (PRGA)

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 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]

2.2 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 ≤ 255, typically between 5 and 32, 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.

The following is wikicode , a proposed pseudocode for use in many articles:

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])

2.3 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).

3 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.

3.1 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.

4 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).
• Scott R. Fluhrer and David A. McGrew, Statistical Analysis of the Alleged RC4 Keystream Generator. FSE 2000, pp19–30 (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).
• Itsik Mantin and Adi Shamir, A Practical Attack on Broadcast RC4. FSE 2001, pp152–164 (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

5 External links

RC4

• IETF Draft - A Stream Cipher Encryption Algorithm "Arcfour"
• Original 1994 usenet post of RC4
• SCAN's entry for RC4
• Attacks on RC4
• RC4 - Cryptology Pointers by Helger Lipmaa
• RSA Security Response to Weaknesses in Key Scheduling Algorithm of RC4

RC4 in WEP

• (in)Security of the WEP algorithm
• Fluhrer, Mantin, and Shamir attack on WEP (postscript format)

Implementations

• CipherSaber, an easy to implement RC4 encryption system
• An optimized RC4 implementation in C (full source code and test vectors)
• An optimized RC4 implementation for AMD64

Stream ciphers Pseudorandom number generators

<Hide>