THE GARDEN

RC4 Weak-IV Key Recovery (FMS Attack)

Updated 19 Sep 2026

• •

  What it is

  • •

    RC4's Key Scheduling Algorithm (KSA) mixes a secret key into a 256-byte permutation $S$ over 256 swap-steps. Fluhrer, Mantin and Shamir showed that "weak" 3-byte IVs of the form $(A{+}3,\ 255,\ X)$ — for a target key-byte position $A$ — cause a resolved condition in the early KSA swaps with roughly 5% probability; when it holds, the very first RC4 output byte directly leaks key byte $K[A]$ through a computable relationship with the permutation state at that point. Since each trial only succeeds ~5% of the time, an attacker sends many IVs of that shape (varying only the free byte $X$) and takes the most common ("majority vote") implied key byte across all trials, which reliably surfaces the correct value despite the ~95% noise. This is the exact attack that broke WEP Wi-Fi encryption, since WEP prepends a short IV to a fixed key for every packet, guaranteeing weak IVs show up naturally in normal traffic.

• •

  When to apply

  • •

    You're given (or can induce) an RC4 keystream-decryption oracle where you control the IV/nonce prepended to the real (unknown, fixed) key, and can query it many times with different IVs while observing (or deriving) each response's first keystream byte.

• •

  Math

  • •

    For a weak IV $(A{+}3, 255, X)$, simulating the KSA up to round $i = A{+}2$ using only the known IV+key-prefix bytes gives $S[i]$ and the running index $j$; when the resolved condition holds, the first keystream byte $z_0$ satisfies $z_0 \approx S[i] + j$, so a candidate key byte is $K[A] \approx z_0 - S[i] - j \pmod{256}$.

• •

  Worked example

  • •

    For each key position $A$, gather many weak-IV samples $(A+3,255,X)$, apply the FMS candidate formula only when its resolved condition holds, and count votes. The correct byte is expected to be biased toward the top; one 256-sample pass is not guaranteed, so validate the growing key prefix against fresh observations.

• •

  Python

  • •

    def simulate_ksa_partial(key_prefix, rounds):
        S = list(range(256)); j = 0
        for i in range(rounds):
            j = (j + S[i % 256] + key_prefix[i % len(key_prefix)]) % 256
            S[i], S[j] = S[j], S[i]
        return S[rounds], j   # S[i] and j after `rounds` KSA swaps
    
    # candidate = (first_keystream_byte - S_i - j) % 256, majority-voted over many X
    

• •

  Related

• •

  Cards

  • •

    What shape of IV does the FMS attack look for, and why?

    • •

      IVs of the form (A+3, 255, X) — they induce a resolved KSA state with ~5% probability that leaks key byte K[A] through the first keystream byte.

  • •

    Why does querying many values of X and majority-voting recover the key byte reliably?

    • •

      Each trial only succeeds ~5% of the time, but the correct key-byte value is the one candidate that shows up disproportionately often across many trials, standing out from the noise.

◌ Explore connections in Graph view