Breaking RC4 with Its Second-Byte Bias

Breaking RC4 with Its Second-Byte Bias

Introduction

A stream cipher’s keystream has one job: to look perfectly random. The RC4 guide explains that RC4’s keystream fails at this in measurable ways. This post turns one of those failures into a working attack. Mantin and Shamir found it in 2001. RC4’s second output byte is 0 about twice as often as chance allows. That sounds like a tiny flaw. But if the same secret is encrypted many times, the bias adds up. After a few thousand ciphertexts, the secret’s second byte simply stands out. The attacker never learns a single key.

Table of Contents

• Why a Small Bias Is Enough
• Where the Bias Comes From
• The Attack: Count and Pick the Winner
• A Worked Example
• Python Implementation
• Interactive Visualizer
• How Many Ciphertexts Does It Take?
• Limitations of This Attack
• FAQ
• References

Why a Small Bias Is Enough

RC4 encrypts by XORing each plaintext byte with a keystream byte. Where the keystream byte is 0, the XOR changes nothing. The plaintext byte appears in the ciphertext unchanged.

A perfect keystream would output 0 exactly 1 time in 256. RC4’s second byte outputs 0 about 2 times in 256. So in the second position, the real plaintext byte shows up about twice as often as any other value.

One ciphertext reveals nothing, because the attacker can’t tell which captures had a zero keystream byte. But many ciphertexts of the same secret, each under a different key, reveal a lot. Every other value shows up at the fair rate. The true byte shows up at double that rate. Counting is enough to find it.

This is called a broadcast setting. The same message goes out many times under different keys. It happens more often than you might expect. Browsers resend the same cookie on every request. Protocols repeat fixed headers. Mail servers send the same message to many recipients.

Where the Bias Comes From

The bias is not a mystery. It follows directly from RC4’s first two output steps.

Suppose the key schedule finishes with S[2] = 0 and S[1] = X, where X is anything except 2. Then the output generator runs:

1. First step. i = 1, j = S[1] = X. Swap S[1] and S[X]. Now S[X] = X, and S[2] is still 0.
2. Second step. i = 2, j = X + S[2] = X. Swap S[2] and S[X]. Now S[2] = X and S[X] = 0.
3. Second output. S[S[2] + S[X]] = S[X + 0] = S[X] = 0.

So whenever the key schedule leaves S[2] = 0, the second output byte is 0 with certainty. That happens about 1 time in 256. The other 255 times, the second byte is roughly random and also hits 0 about 1 time in 256. Together that gives about 2 in 256. It’s double the fair rate.

The Attack: Count and Pick the Winner

The attacker collects many ciphertexts of the same secret. Each was encrypted under its own random key.

1. Capture. Record the ciphertexts. Keys, plaintext, and keystream all stay hidden.
2. Tally. Count how often each of the 256 byte values appears in position 2.
3. Pick the winner. The most common value is the guess for the secret’s second byte.

There’s nothing more to it. No key is recovered, and nothing is decrypted directly. The bias does all the work, one ciphertext at a time.

A Worked Example

The visualizer’s defaults use the secret Cookie: sid=7f3a. Its second byte is o (0x6F). The victim encrypts it 8,192 times, each under a fresh 128-bit key. The keys come from a seeded generator (seed 2026), so every run is reproducible.

1. Expected counts. With no bias, each byte value would appear about 8,192 / 256 = 32 times in position 2.
2. Tally. The most common value is 0x6F (o), seen 67 times.
3. Margin. The runner-up is 0x27, seen 51 times. Every other value falls below that.
4. Result. The guess o matches the secret’s second byte.

The count of 67 is not a coincidence. Behind the scenes, the second keystream byte was 0 in exactly 67 of these captures. Each of those left o untouched in the ciphertext.

The other positions show why the second byte is special. For byte 1, the top value is 0xD1, tied at 47 with another value, and the true byte is C. For byte 3, the top value is T at 51, not the true o. For byte 4, the top value is 5 at 49, not the true k. Those positions have no bias this strong, so their tallies are just noise.

Python Implementation

The visualizer runs this exact attack in JavaScript. Here’s the same attack in Python. The key generator matches the visualizer’s, so a given seed produces identical results in both.

Key Features

• Real RC4. It uses the same key schedule and output loop as the RC4 guide.
• A fresh key per capture. Each ciphertext uses its own 128-bit key, just like separate connections.
• The attacker sees only ciphertexts. The recovery function takes nothing but the captured ciphertexts.
• Reproducible keys. A small seeded generator, mulberry32, stands in for a real random source. That lets you check the numbers against the visualizer exactly.

Code

# rc4_bias_breaker.py
#
# Recovers the second byte of a secret that was encrypted with RC4 many
# times, each time under a different random key. RC4's second keystream
# byte is 0 about twice as often as it should be (Mantin-Shamir, 2001).
# Wherever the keystream byte is 0, the ciphertext byte equals the
# plaintext byte, so the most common second ciphertext byte is the answer.
#
# Keys come from a small seeded generator (mulberry32) so this script
# reproduces the interactive visualizer's numbers exactly.

from collections import Counter


def mulberry32(seed):
    a = seed & 0xFFFFFFFF
    while True:
        a = (a + 0x6D2B79F5) & 0xFFFFFFFF
        t = ((a ^ (a >> 15)) * (1 | a)) & 0xFFFFFFFF
        t = ((t + (((t ^ (t >> 7)) * (61 | t)) & 0xFFFFFFFF)) & 0xFFFFFFFF) ^ t
        yield (t ^ (t >> 14)) & 0xFFFFFFFF


def random_keys(seed, count):
    rng = mulberry32(seed)
    for _ in range(count):
        yield b"".join(next(rng).to_bytes(4, "little") for _ in range(4))


def rc4_ksa(key):
    S = list(range(256))
    j = 0
    for i in range(256):
        j = (j + S[i] + key[i % len(key)]) % 256
        S[i], S[j] = S[j], S[i]
    return S


def rc4_crypt(key, data):
    S = rc4_ksa(key)
    i = j = 0
    out = bytearray()
    for byte in data:
        i = (i + 1) % 256
        j = (j + S[i]) % 256
        S[i], S[j] = S[j], S[i]
        out.append(byte ^ S[(S[i] + S[j]) % 256])
    return bytes(out)


def capture(secret, count, seed):
    # The victim: the same secret, a fresh 128-bit key every time
    return [rc4_crypt(key, secret) for key in random_keys(seed, count)]


def recover_second_byte(ciphertexts):
    # The attacker: only ever looks at ciphertexts
    tally = Counter(c[1] for c in ciphertexts)
    return tally.most_common(2)


if __name__ == "__main__":
    secret = b"Cookie: sid=7f3a"
    captures = capture(secret, 8192, seed=2026)

    (best, hits), (runner_up, runner_hits) = recover_second_byte(captures)
    print(f"Captured ciphertexts:  {len(captures):,}")
    print(f"Expected per value:    {len(captures) / 256:.0f}")
    print(f"Most common byte:      0x{best:02X} {chr(best)!r} seen {hits} times")
    print(f"Runner-up:             0x{runner_up:02X} seen {runner_hits} times")
    print(f"Actual second byte:    0x{secret[1]:02X} {chr(secret[1])!r}")

Running this script produces the following output:

Captured ciphertexts:  8,192
Expected per value:    32
Most common byte:      0x6F 'o' seen 67 times
Runner-up:             0x27 seen 51 times
Actual second byte:    0x6F 'o'

This matches the visualizer and the worked example exactly.

For Fun: The Whole Attack in 10 Lines

Same spirit as this site’s other golfed bonus sections. Not for learning the algorithm from. This version skips everything but the second keystream byte. It uses truly random keys from os.urandom, so the counts change on every run.

import os
from collections import Counter
def z2(k):
    S=list(range(256)); j=0
    for i in range(256): j=(j+S[i]+k[i%16])%256; S[i],S[j]=S[j],S[i]
    j=0
    for i in 1,2: j=(j+S[i])%256; S[i],S[j]=S[j],S[i]
    return S[(S[2]+S[j])%256]
v=Counter(ord("o")^z2(os.urandom(16)) for _ in range(16384)).most_common(1)[0][0]
print(f"Recovered second byte: {chr(v)!r}")

Verified to print Recovered second byte: 'o' on every one of five runs. Its z2 function was also checked against full RC4 on 2,000 random keys, matching every time. It uses 16,384 captures because that count succeeded in all 200 trials measured below.

For Fun (2): Even Smaller

This version squeezes it down to 8 lines. It unrolls the two output steps onto a single line. Instead of Counter, it uses statistics.mode to pick the most common value.

import os
from statistics import mode
def z(k):
 S=[*range(256)];j=0
 for i in range(256):j=(j+S[i]+k[i%16])%256;S[i],S[j]=S[j],S[i]
 i=1;j=S[i];S[i],S[j]=S[j],S[i];i=2;j=(j+S[i])%256;S[i],S[j]=S[j],S[i]
 return S[(S[i]+S[j])%256]
print(chr(mode(111^z(os.urandom(16)) for _ in range(16384))))

Verified to print o on every one of five runs. Its z function matched full RC4 on 2,000 random keys. The constant 111 is simply ord("o"), the secret’s second byte. The first output step can set j = S[1] directly, because j always starts at 0.

Interactive Visualizer

Try the visualizer above, and watch the 256-bar histogram fill as ciphertexts arrive. One bar slowly pulls away from the dashed fair-share line. Change the secret, the seed, or the capture count. Then run 200 trials to see how reliable the attack is at each capture count.

How Many Ciphertexts Does It Take?

The bias is small, so the attack needs volume. The table below repeats the full attack 200 times, with seeds 1 to 200. It counts how often the tallest bar was the right byte. The visualizer’s trial button reproduces these exact numbers.

At 1,024 captures the true byte appears about 8 times, against a fair share of 4. Random noise often beats that. By 16,384 captures, it appears about 128 times against a fair share of 64. The gap is now far too large for noise to close. That’s the general rule for bias attacks. The signal grows in proportion to the number of samples, while the noise grows only with its square root.

Limitations of This Attack

This attack recovers one byte, the second one. The strong Mantin-Shamir bias exists only there. The worked example shows the other positions failing at the same capture count.

Later research found weaker biases at many more positions. AlFardan and colleagues used them in 2013 to recover the first 256 bytes of repeated TLS plaintext. That needed millions to billions of encryptions of the same secret, not thousands. Vanhoef and Piessens pushed further in 2015 with an attack called RC4 NOMORE. They recovered a secure web cookie in about 75 hours of traffic. Those attacks are out of scope here, but they grew from exactly this idea.

The attack also needs the broadcast setting. The same secret must sit at the same position across many encryptions. A protocol that never repeats plaintext at fixed offsets gives this attack nothing to count.

Discarding the start of the keystream defeats this particular bias. Some RC4 variants did exactly that, throwing away the first 256 or more bytes. It didn’t save RC4. Weaker biases persist further into the keystream, and they were eventually exploited too.

It’s also worth separating this attack from WEP’s break. WEP fell to the Fluhrer-Mantin-Shamir attack, which recovers the key itself. It exploits how WEP built each RC4 key from a public value and a shared secret. The second-byte bias is a different weakness. It recovers plaintext, and it works no matter how the keys were chosen.

FAQ

Does this attack recover the RC4 key?

It doesn’t, because it never learns any key. It recovers plaintext directly, using only the statistics of many ciphertexts.

Why does the same secret need to be encrypted many times?

Each single ciphertext reveals nothing on its own. The attack works only by comparing the same position across many encryptions of the same data. Only then does the doubled frequency show up.

Would a longer or better key help?

It wouldn’t help at all. The bias comes from RC4’s structure, not from weak keys. The demo already uses random 128-bit keys. Any key length shows the same bias.

Why is RC4 still worth studying?

It shows how a cipher can fail without any key being recovered. A tiny statistical flaw, repeated enough times, leaks real data. Modern designs like ChaCha20 were built to rule out exactly this kind of weakness.

Is RC4 still used anywhere?

It’s banned in TLS by RFC 7465, published in 2015. Every major browser has removed it. It still shows up in some legacy systems, which is one more reason to understand its weaknesses.

References

1. Mantin, I. and Shamir, A. “A Practical Attack on Broadcast RC4.” Fast Software Encryption (FSE) 2001.

2. Fluhrer, S., Mantin, I., and Shamir, A. “Weaknesses in the Key Scheduling Algorithm of RC4.” Selected Areas in Cryptography (SAC) 2001.

3. AlFardan, N., Bernstein, D., Paterson, K., Poettering, B., and Schuldt, J. “On the Security of RC4 in TLS.” USENIX Security Symposium, 2013.

4. Vanhoef, M. and Piessens, F. “All Your Biases Belong to Us: Breaking RC4 in WPA-TKIP and TLS.” USENIX Security Symposium, 2015.

5. Popov, A. “Prohibiting RC4 Cipher Suites.” RFC 7465, 2015. Available at: https://www.rfc-editor.org/rfc/rfc7465