RC4

RC4
Name	RC4
Designer	Ron Rivest
Publish date	1987
Key size	40–2048 bits (commonly 128 bits)
Block size	stream cipher (byte-wise)
Structure	stream cipher
Rounds	variable
Cryptanalysis	extensive

RC4 is a widely deployed stream cipher designed by Ron Rivest in 1987 while at MIT. It became popular in protocols and products from Microsoft's Windows and Internet Explorer to Netscape Navigator, WEP-based Wi‑Fi devices, and many SSL/TLS deployments, due to its simplicity and speed. Over time, numerous researchers from institutions such as Bell Labs, MIT, Princeton University, University of California, Berkeley, and École Normale Supérieure discovered practical attacks that significantly weakened its security, leading major standards bodies and vendors like IETF, NIST, Microsoft Corporation, and Google to deprecate its use.

History

RC4 was created by Ron Rivest at MIT and circulated as a proprietary algorithm within RSA Security's product suite before its algorithm description leaked in 1994 during a Cypherpunks-era release. The cipher gained rapid adoption in commercial software including Netscape Communications's Netscape Navigator and later in Microsoft's Internet Explorer and Windows implementations, as well as in wireless networking through the WEP standard adopted by the IEEE 802.11 working group. Academic cryptanalysts from University of Toronto, Royal Holloway, University of London, and Queen Mary University of London published influential analyses exposing biases and correlations in the keystream, prompting responses from standards organizations such as the IETF and NIST and operational changes by vendors like Apple Inc. and Mozilla Foundation.

Algorithm

The algorithm initializes a 256-byte permutation array using a key-scheduling algorithm (KSA) and then produces a pseudorandom stream via a pseudo-random generation algorithm (PRGA). The KSA mixes the key into a permutation S through iterative swaps; the PRGA advances indices and emits keystream bytes by combining entries from S, which are XORed with plaintext to produce ciphertext. Design and analysis papers appeared from researchers at École Polytechnique Fédérale de Lausanne, University of Bristol, and Cornell University, comparing it to contemporary ciphers like Blowfish, IDEA, Twofish, and AES (the latter standardized by NIST via the Rijndael submission).

Security Vulnerabilities and Attacks

Academic work identified multiple vulnerabilities: initial output biases revealed by researchers at IBM and University of California, Los Angeles allow key-recovery when key material is reused or weak; practical key-recovery attacks against WEP were demonstrated by teams at ICSI and UC Berkeley, notably the Fluhrer, Mantin and Shamir attack. Later statistical distinguishers and key-recovery techniques by cryptographers at Microsoft Research, Technische Universität Darmstadt, and KTH Royal Institute of Technology exploited early keystream biases, leading to plaintext-recovery and chosen-plaintext attacks against protocols like SSL and TLS. Side-channel analyses and timing attacks reported by teams at Cambridge University and ETH Zurich further reduced practical security. These cumulative results motivated deprecation by bodies including the IETF's TLS working group and vendors such as Google and Mozilla.

Implementations and Usage

RC4 appeared in numerous software and hardware products: network stacks in Microsoft Windows NT and Windows XP, web browsers like Netscape Navigator and Internet Explorer, embedded firmware in early Cisco Systems routers, and wireless access points from vendors including Linksys and D-Link. It was used in protocols such as SSL 3.0, early versions of TLS, WEP, and some VPN products. Open-source libraries and projects such as OpenSSL, LibreSSL, GnuTLS, and WolfSSL historically included RC4 implementations, later removing or disabling them in response to advisories from organizations like CERT and US-CERT and guidance from NIST.

Performance and Variants

RC4's simplicity—byte-oriented operations and a compact state—yielded high throughput on general-purpose CPUs and low overhead on constrained devices, making it competitive with block ciphers in stream modes for certain workloads. Variants and proposals include modified KSA/PRGA designs and related algorithms such as RC4A and Spritz (a successor proposed by Ron Rivest), and comparisons involve ciphers like Salsa20, ChaCha20, HC-128, and Grain. Implementations optimized with assembly for architectures from Intel x86 to ARM and microcontrollers such as Atmel demonstrated various speed trade-offs; however, many modern high-performance applications migrated to ChaCha20-Poly1305 and AES-GCM recommended by IETF and NIST.

Deprecation and Replacement

Due to accumulated cryptanalytic results and operational attacks—especially against WEP and legacy TLS—standards bodies and major vendors moved to prohibit RC4 in favor of authenticated encryption and more robust stream and block cipher constructions. The IETF formally prohibited RC4 in TLS, while NIST guidance and vendor policies from Microsoft, Google, Mozilla, and Apple recommended replacing it with AES-GCM, ChaCha20-Poly1305, or other AEAD algorithms. Ongoing research into stream cipher design continues at institutions like École Normale Supérieure, Technische Universität Darmstadt, and École Polytechnique, but RC4 remains largely obsolete in modern secure systems.

Category:Stream ciphers