Overview
This lecture presents critical weaknesses in RC4’s key scheduling algorithm (KSA), including the existence of weak keys, key-output correlations, and related-key vulnerabilities, with special emphasis on practical attacks such as those breaking WEP encryption.
RC4 Structure and Security Overview
- RC4 is a widely used stream cipher with a large internal state and key sizes between 40-256 bits.
- The KSA generates an initial permutation S from the key; the PRGA generates the output keystream.
- Every element in S is swapped at least once in every N rounds, enabling permutation evolution.
- Standard attacks on PRGA are impractical due to RC4's keyspace; most attacks focus on biases in output (distinguishers).
The Invariance Weakness in KSA
- Certain "weak keys" (with length divisible by a power of two) let a small subset of key bits determine many bits of the initial permutation.
- For b-exact keys, KSA can result in b-conserving permutations, making the output predictable.
- The invariance weakness allows predictable patterns from key bits to propagate through the output, resulting in statistical biases.
Key-Output Correlation
- Weak key patterns in the initial permutation lead to predictable biases in the output keystream.
- For some keys, output bits (e.g., LSBs) can be determined with much higher probability than by random chance.
- These biases help attackers build distinguishers to tell RC4 output from random data and are relevant for ciphertext-only attacks.
Cryptanalytic Applications
- New distinguishers can identify RC4 streams with less data than previous methods, sometimes ignoring the first few output words.
- RC4 has low sampling resistance, making it susceptible to time/memory/data tradeoff attacks utilizing these output biases.
Known IV Weakness and WEP Attack
- When RC4 is used with a fixed key and varying IV (e.g., in WEP), attackers can recover the key by analyzing the first keystream output for many IVs.
- The complexity of key recovery scales linearly with key length, making even long keys vulnerable.
- Attacks are practical and were confirmed by implementation against WEP.
Related-Key Attacks
- Attacks exploiting the invariance weakness reveal key bits in stages, reducing key search complexity from exponential to practical levels for certain key lengths.
- Known IV attacks reconstruct the key sequentially using chosen or known IVs and the resulting output patterns.
Recommendations and Mitigations
- Discard the first N output words to reduce key-output correlation.
- Avoid concatenating IVs with a fixed key; use secure hashes to combine them before key scheduling.
Key Terms & Definitions
- RC4 — A stream cipher using variable-size keys and permutation-based state.
- KSA (Key Scheduling Algorithm) — Process that initializes RC4’s state from the key.
- PRGA (Pseudo-Random Generation Algorithm) — Part of RC4 that generates output keystream.
- Weak key — A key with structure allowing disproportionate control over the output.
- b-exact key — Key type where certain bits repeat in a pattern, causing predictable output.
- IV (Initialization Vector) — A value used to modify the key per message.
- Sampling resistance — A cipher's resistance to attacks exploiting repeated output patterns.
Action Items / Next Steps
- Review how KSA and PRGA function in RC4.
- Read about WEP protocol and known attacks if studying wireless security.
- Practice identifying and understanding weak key structures in stream ciphers.
- Prepare for questions on real-world vulnerabilities due to improper IV handling.