The RC4 cipher

RC4 is a stream cipher Ron Rivest designed in 1987. It's about as simple as a cipher gets: a few lines of code shuffling a table of 256 bytes. For twenty years it protected most web traffic and Wi-Fi. It's also one of the best-documented failures in cryptography. Its output is subtly biased, its key setup leaks, and TLS prohibited it in 2015. Textbooks still teach it as the example of a cipher that looks random and isn't.

How it works

RC4's entire state is a table S of 256 bytes and two pointers, i and j. It runs in two stages.

1. Key scheduling. Start with S holding 0, 1, 2, … 255. For each i from 0 to 255, add S[i] and the next key byte (repeating the key as needed) to j, then swap S[i] with S[j]. When the loop finishes, the key has shuffled the table.
2. Generating the stream. For each byte you want, add 1 to i, add S[i] to j, swap S[i] and S[j], and output S[(S[i] + S[j]) mod 256].

XOR the key stream with the message to encrypt, and XOR again to decrypt, as with any stream cipher. The standard small test uses the key Key and the plaintext Plaintext, which encrypt to BBF316E8D940AF0AD3. The key Secret with Attack at dawn gives 45A01F645FC35B383552544B9BF5. The listing below is the whole cipher, and the project's tests check both results.

Why it was everywhere

RC4 was fast and tiny and needed no special hardware, which suited the 1990s. RSA Security kept the algorithm a trade secret until September 1994, when someone posted a description anonymously to the Cypherpunks mailing list. After that it became the cipher of the early web (SSL and TLS), of Wi-Fi's original security (WEP) and of plenty of applications besides.

The bias

A perfect stream cipher would produce each byte value with probability 1/256. RC4 doesn't. In 2001 Itsik Mantin and Adi Shamir found that its second output byte is zero with probability 1/128, twice what it should be. You can see it yourself. The project's script scripts/examples/rc4-bias.mjs encrypts two zero bytes under two million random 16-byte keys and finds the second byte is zero with probability 0.00783, against 0.00391 for the first. That's a ratio of 2.00. Encrypt a message under many different keys and the bias starts to show: if the second plaintext byte is always the same, the second ciphertext byte lands on one value more often than it should, and statistics pick that out.

Researchers have found many more biases over the years, in the first few hundred output bytes especially. That's why careful users throw the start of the stream away. The best-known exploit targets HTTPS. When the same secret (a cookie) goes out many times in different TLS sessions, each under a fresh RC4 key, the biases leak it.

WEP: how it broke Wi-Fi

WEP, the original Wi-Fi security, ran RC4 with a key built from a shared secret plus a 24-bit counter (the IV) that went out in the clear. In 2001 Scott Fluhrer, Itsik Mantin and Adi Shamir showed that certain IV values leak information about the key through the key scheduling, so an attacker who collects enough frames can recover the secret. Andreas Klein (2005) and others sharpened the attack. The tool aircrack-ptw breaks a 104-bit WEP key from about 40,000 captured frames with 50% probability, or 85,000 for 95%, and that takes minutes. WEP is the textbook case of a decent-looking cipher breaking inside a bad protocol.

The end

Attacks on RC4 kept coming. Researchers at Royal Holloway reported an attack on RC4 in TLS in 2013 that needed about 2³⁴ messages, and in March 2015 an improved attack against passwords sent over TLS. The RC4 NOMORE attack in 2015 decrypted an HTTP cookie sent over TLS in 75 hours, and broke WPA-TKIP, a Wi-Fi mode based on RC4, within an hour. RFC 7465, in February 2015, prohibited RC4 in all versions of TLS. RC4 had lasted so long in TLS partly because of the BEAST attack of 2011 on CBC mode in TLS 1.0. RC4 was immune to BEAST, so servers preferred it. Once better answers arrived in TLS 1.2, authenticated modes like AES-GCM and ChaCha20, RC4 could finally retire.

What RC4 teaches

• Looking random isn't being random. RC4's output passes casual tests and still carries a measurable bias.
• Key setup matters as much as the generator. WEP's weakness sat in the first output bytes, which depend on only a few key bytes.
• Protocols break ciphers. Gluing a secret to a visible counter turned a flaw into a total break.
• Retiring a cipher takes a decade. The attacks were known by 2001, and the ban came in 2015.

The code

// RC4: shuffle the numbers 0 to 255 using the key, then generate one key byte per message byte by swapping and picking. XOR it with the data.
function rc4(data, key) {
  var s = [], i, j = 0, t, out = [];
  for (i = 0; i < 256; i++) s[i] = i;
  for (i = 0; i < 256; i++) { j = (j + s[i] + key[i % key.length]) & 255; t = s[i]; s[i] = s[j]; s[j] = t; }   // key scheduling
  i = 0; j = 0;
  for (var n = 0; n < data.length; n++) {
    i = (i + 1) & 255; j = (j + s[i]) & 255; t = s[i]; s[i] = s[j]; s[j] = t;                                     // generator step
    out.push(data[n] ^ s[(s[i] + s[j]) & 255]);
  }
  return out;
}

Common questions