A key-scheduling algorithm (KSA) prepares a cipher’s internal state from a key before output generation begins. In RC4, it turns an ordered 256-byte S-box into a key-dependent permutation: every byte from 0 through 255 remains present exactly once, but its position is shuffled. Like shaking a box of numbered rocks, the contents stay the same while their ordering changes. section 4.3.1
RC4 separates initialization from generation. KSA runs once for a new key, then the pseudorandom generation algorithm (PRGA) repeatedly mutates the prepared state to emit keystream bytes. This resembles seeding a random-number generator once and then calling its next/output operations many times. section 4.3.1
The RC4 KSA has two stages:
- Initialize S so that S[i] = i for every index from 0 to 255. section 4.3.1
- Set j to zero, then scan i from 0 to 255. On each iteration, compute j = (j + S[i] + key[i mod keylength]) mod 256. section 4.3.1
- Swap S[i] with S[j]. The modulo key lookup repeats shorter keys across the full 256-step shuffle. section 4.3.1
Listing 4.10 Pseudocode for RC4 key-scheduling algorithm
for i from 0 to 255
S[i] := i
endfor
j := 0
for i from 0 to 255
j := (j + S[i] + key[i mod keylength]) mod 256
swap values of S[i] and S[j]
endfor
The pseudocode makes the two invariants explicit: S begins as the identity permutation, and each key-influenced update swaps two entries without removing or duplicating any value. section 4.3.1
Tracing the first KSA step
With the key “HELLO,” initialization gives S[0] = 0 and j = 0. At i = 0, the first key byte contributes to j; KSA then swaps S[0] with S[j]. The same pattern runs 255 more times, while i advances sequentially and j jumps according to the evolving S-box and repeating key bytes. section 4.3.1
A KSA is meant to hide any direct relationship between key bytes and later keystream. RC4’s KSA fails that goal in some cases: its statistical biases can make key bytes more likely to influence observable keystream positions. In WEP, a packet key concatenates a public three-byte initialization vector (IV) with a preshared key, giving attackers known key prefixes to exploit. section 4.3.2
The Fluhrer, Mantin, and Shamir (FMS) attack targets WEP IVs shaped [L, 255, X], where L identifies the preshared-key byte to recover. Given many packets using these weak IVs and a known plaintext byte, an attacker derives each packet’s first keystream byte, simulates the early KSA steps using already recovered key bytes, and votes for the next byte candidate. The most frequent candidate can reveal the byte statistically. section 4.3.2
Why sample volume matters
A recovery implementation gathers 50,000 weak-IV packets per target byte and successfully reconstructs sample preshared keys. Reducing collection to 500 packets produces incorrect byte guesses, because the KSA bias is statistical rather than deterministic. section 4.3.2
Treat a complicated state shuffle as a security property to test, not as proof of security. When a protocol exposes structured key material such as public IV prefixes, even small initialization biases can become practical key-recovery signals after enough observations. section 4.3.2
