We saw last time that ciphers are useful tools to hide information from prying eyes. We also classified ciphers into two families: Symmetric algorithms and asymmetric algorithms.[i] As it turns out, symmetric algorithms can be further divided into stream ciphers and block ciphers. We’ll be looking at the former in this post, and we’ll see block ciphers in the next two posts in this series. For now, though, let’s recall our basic setup for encrypted communication.
In this system, Alice and Bob want to exchange messages across an unsecured channel. As we saw previously, best practice is for Bob to encrypt his message before sending it to Alice. We demonstrated this using the Caesar Cipher, but we noticed the security of this type of cipher is very weak due to its key size. As will become clear, conventional wisdom is that larger keys (i.e., more bits) tend to make securer encryption schemes. A long, strong key is worthless without a cryptographically secure cipher, however, and it’s not always feasible to have long keys.
A stream cipher is one alternative to the Caesar Cipher and other weak substitution ciphers. A stream cipher encrypts the plaintext message’s characters individually, one-by-one. A keystream is produced by the cipher, and each character in the keystream is used to encrypt the corresponding character in the plaintext.[ii] The same process can be used to decrypt a ciphertext to produce a plaintext.
In practice, Alice and Bob agree upon a cipher and a key to use. For example, Alice and Bob have agreed upon the key “KHXLO”. In the simplest scheme, Bob can encrypt his message “HELLO” using modular addition, similar to the Caesar Cipher. Thus, Bob encrypts , which produces “R”. If he does this for the rest of his message, he gets the ciphertext “RLIWB”. Alice decrypts this using the same key, but she uses subtraction to reverse the addition. So, Alice calculates , which produces “H”.[iii] She repeats this process for each character to retrieve Bob’s original message. The big catch is that the key must be the exact length of the plaintext. This doesn’t necessarily seem like a huge problem in this simple example, but this strict requirement can become infeasible rather quickly. Other than that, Alice and Bob just need to use a different key each time they communicate to maintain security.
This scheme is the ideal stream cipher: The One-Time Pad (OTP), which has seen widespread use in intelligence communities for over a century. The OTP is a stream cipher in which the key is the same length as the plaintext, and each character in the plaintext is independently encrypted by a character from the key. Incidentally, the keystream in the OTP is the same as the initial key. This is an important qualification for this cipher, but as we’ll see soon, not all stream ciphers follow this practice. These characteristics make the OTP a cryptographically secure cipher—it can’t be broken, at least not without luck. Unfortunately, the OTP is highly impractical for most meaningful plaintext messages.
The problems with the OTP are threefold. First, for any key to be truly secure, it should be randomly generated. We use pseudorandom number generators (PRNGs) to produce numbers that appear random because true randomness is difficult to capture in deterministic computers. That is, computers behave in predictable ways; they perform only the actions they are instructed. Because we can control and predict the outcomes of operations, we refer to computers as having determined behavior. This determinism is antithetical, in principle, to true randomness. So, we do our best to approximate true randomness by using clever mathematics and programming principles to generate pseudorandom numbers.
Second, the key must be the same length as the plaintext. This characteristic is the crux of the OTP’s security. Why must we use such long keys? The underlying reason was shown by Joseph Mauborgne and Claude Shannon: It’s statistically impossible to break the encryption when a randomized key is the same length as the plaintext. That is, we can’t confidently determine the relationships between plaintext and ciphertext when each plaintext character is encrypted independently of the others. But this works only when the key doesn’t repeat—the key cannot be shorter than the plaintext message—and is sufficiently random. The problem with this approach is that it’s totally impractical. For example, if we wanted to encrypt a 100 GB hard drive, then we would need a key that is also 100 GB. That’s a huge inefficiency, because that 100 GB of data used as the key is thrown away almost immediately—that doesn’t even account for the time and computational complexities of operating on huge quantities of data.
Finally, the key cannot be reused. The real problem here is that we’re humans—we like things to be easy. It’s much easier to settle on one or two keys than to swap keys for every message. This reuse of keys increases the chances an attacker will break our encryption by guessing the correct key.
The OTP can be practical for small messages, but we want to extend it to messages of all sizes. To do this we must solve the OTP’s three main problems. Many stream ciphers attempt this, but none is as popular as the RC4 cipher.
The RC4 cipher was designed by Ron Rivest of RSA Security in 1987 and was leaked in 1994. Because it’s simple and efficient in software, RC4 has seen widespread use in a number of applications. As we’ll see, though, RC4 has fallen out of favor in recent years because it has been cryptographically broken. But how does RC4 actually work?
The whole cipher is dependent upon a secret internal state that consists of a 256-byte array S and two indices i and j that point to bytes within S. We initialize S by numbering the bytes sequentially from zero to 255. The bytes in S are permuted (i.e., shuffled around) in a pseudorandom fashion by mixing the bytes in S with the bytes in a variable-length key.[iv] This permuted array of bytes is then used to generate the keystream for the actual encryption. Because RC4 is a stream cipher, each byte in the plaintext must be encrypted individually by an individual byte from the keystream. In the case of the OTP, the key is the keystream, but this is not the case in RC4.
Before we can actually encrypt a plaintext, we need to generate the keystream. We do this by performing some modular addition on the pointers i and j and the values they point to in S.[v] After we perform that addition, we swap those values in S, and we use their sum to look up a keystream byte K in S. Finally, we perform a bitwise exclusive-or (XOR) on K and the next byte in our plaintext message to produce a byte of ciphertext—this is the actual encryption.[vi] We repeat this process until we reach the end of the plaintext message. The end result is an encrypted ciphertext that may be decrypted using the same initial key. Unless the cipher has been altered or a different key is used, the internal state will produce the same keystream regardless of whether we are encrypting a plaintext or decrypting a ciphertext.
The RC4 cipher is a good attempt to realize the OTP, but it’s not perfect. The keystream is pseudorandom, which isn’t as statistically secure as true randomness. The cipher does have the advantages of relatively short keys and an internally generated keystream. Instead of using a 100 GB key to encrypt a 100 GB hard drive, for example, we could use a key as short as a few bits. The cipher generates the keystream internally, so we don’t have to worry about remembering long keys each time we want to encrypt and decrypt. Even better, keys don’t need to be used more than once—they really shouldn’t be, in any case. In short, the cipher is simple and efficient without any obvious flaws. Hence, RC4 has been popular, especially in the WEP, WPA, and SSL/TLS network security protocols. That popularity is waning, however, as vulnerabilities in RC4 have been exposed.
The IEEE 802.11 standard specifies the WEP and WPA protocols for securing wireless networks by using RC4. Both protocols have been deprecated since weaknesses were discovered in RC4’s key-scheduling algorithm (the initial shuffling of S). Essentially, the keystream produced by RC4 has been shown to be statistically predictable and nonrandom, which greatly reduces the security of the cipher. Remember from the OTP that we really need our keystream to be random to maintain security. The randomness is what guarantees the statistical impossibility of breaking the encryption. This lack of sufficient randomness in RC4 led to the specification and adoption of the WPA2 wireless security protocol that uses the AES cipher instead of RC4.
Beyond wireless network security, RC4 has been popularly used in the SSL/TLS protocol that secures Web communications—it’s the reason we have HTTPS website connections. Just a few years ago, the majority of secured Web traffic was transmitted over SSL/TLS using RC4 encryption. This has changed since 2011, however, as escalating attacks have targeted vulnerabilities in SSL/TLS, which led the Internet Engineering Task Force to officially ban RC4 in SSL/TLS connections in 2015. Again, these attacks targeted the weak pseudorandom number generation in RC4. Unfortunately for RC4, any bit-length key is subject to this problem. Luckily, SSL/TLS supports other securer ciphers such as AES and RSA.
Stream ciphers like RC4 are powerful in principle, but better alternatives are available. Our ultimate goal with symmetric ciphers is to realize the security power of the One-Time Pad. The RC4 cipher comes close, but we need to look elsewhere to find a better solution. In the next two parts in this blog series, we’ll see how the block ciphers DES and AES approach the encryption challenge—and we’ll see whether they’re successful.
