Misty-eyed old-timers are mourning the passing of one of the world’s most elegant encryption algorithms. RC4 was designed by Ron Rivest in the late 1980s. Initially, RC4 was a proprietary trade secret of RSA Security. Perhaps due to the algorithm’s simplicity (you can keep it in your head), it leaked out into the Internet in the 1990s where it became the de facto TLS bulk encryption protocol for over a decade.
The Simplicity of RC4
RC4 had a fundamental property that made it different from other ciphers such as DES (data encryption standard) and AES (advanced encryption standard). RC4 was a stream cipher, meaning that it operated by generating a stream of random-ish data from a tiny state machine that was initialized via a secret key (such as a password). The output stream was then simply XOR-ed against plaintext.
The state machine of RC4 required only a 256-byte array S (initialized by the password) and just two variables, indexes i and j. Index i slowly walked through S as index j jumped around S. Bruce Schneier, on his blog, memorializes RC4 and condenses its heart to this simple pseudo-code:
# rc4 core algorithm, output 1 byte
1: i = i + 1
2: j = j + S[i]
4: return S[S[i] + S[j]]
To decrypt the data, an operator simply created the same stream (from the password), and then XORed it against the ciphertext, which had the effect of revealing the initial plaintext. The encryption and decryption operations were the same. Neat! RC4 was blazingly fast because processors perform XOR as a simple opcode.
The other major type of encryption cipher is the block cipher. DES is a block cipher, as is AES. Block ciphers work on blocks of data instead of streams of bytes from a for-loop.
RC4 Cryptographic Attacks
Many, many attacks against RC4 weakened its stature within the cryptographic community. In February 2015, RFC 7465 was introduced to the IETF TLS task force and “requires that Transport Layer Security (TLS) clients and servers never negotiate the use of RC4 cipher suites when they establish connections. This applies to all TLS versions.”
Figure 1 – Support for RC4, source SSL Pulse, Qualys Labs
Even though RFC 7465 is tolling RC4’s death knell, it is still supported by approximately half the TLS servers on the Internet. And because there are still a large number of Windows XP client devices coming out of APAC, RC4 support may linger for some time. As of today, Google, the busiest site in the world, still supports RC4, although Google intends to remove it in the future. Most of the major browsers are planning to remove RC4 as an encryption cipher within the next year.
Festive New Stream Ciphers
There are three interesting new stream ciphers, and all have cute names. Ron Rivest, the inventor of RC4, has improved the RC4 algorithm by adding a third index variable k and moving i through the array more quickly. This new, improved RC4 is called Spritz.
# spritz core algorithm, output 1 byte
1: i = i + w
2: j = k + S[j + S[i]]
2a: k = i + k + S[j]
4: return S[j + S[i + S[z + k]]]
While it looks promising, Spritz hasn’t received much support from the TLS community yet.
Daniel J. Bernstein (yes, that Bernstein) has proposed a couple of stream ciphers called ChaCha and Salsa. Unlike Spritz, ChaCha and Salsa are getting some love from some TLS implementations such as Google’s Chrome browser.
None of these three new stream ciphers appears to be supported by the open source project OpenSSL, which powers much of the modern TLS infrastructure. The current TLS 1.3 draft says that compliant applications should implement ChaCha, so there’s a good chance of seeing it in the wild once TLS 1.3 is approved and starts gaining broad adoption.
Counter Mode: the Best of Both Worlds
It is possible to use block cipher algorithms such that they output a key stream like a stream cipher. This technique is called “counter mode” and is quickly becoming a favorite of the TLS community. At the end of 2015, nearly half of the TLS hosts on the Internet will negotiate a “counter mode” cipher —typically the Galois Counter Mode (GCM) variant of AES. In theory, counter mode should offer the best of both worlds (block and stream). Of course, using a block cipher as the basis for a stream cipher increases the complexity of the encryption mechanics.
To misty-eyed old-timers like myself and many others, the simplicity of RC4 was its greatest appeal. And perhaps the simplicity of the newer stream ciphers such as ChaCha will be what drives their adoption moving forward.