We’ve seen that stream ciphers like RC4 encrypt each character of a message individually. This seems intuitive, but this can actually make a cipher insecure. That is, the one-to-one correspondence between plaintext characters and ciphertext characters makes stream ciphers susceptible to certain attacks. For example, if Eve intercepts Bob’s RC4-encypted message, she can use mathematical analysis to break the encryption. We can solve this problem by using block ciphers.
The Block Cipher
Information Theory pioneer Claude Shannon described two important properties that make ciphers secure: Confusion and diffusion. The former obscures the relationship between plaintext and ciphertext, and the latter spreads the influence of each plaintext bit over many ciphertext bits. In other words, a single bit change in the plaintext may change many bits in the ciphertext. Stream ciphers like RC4 aren’t great at this, but block ciphers are really good at confusion and diffusion. These characteristics make block ciphers popular choices for encryption.
How is a block cipher different from a stream cipher? Instead of encrypting each plaintext character individually, the plaintext’s characters are divided into a series of equal-sized blocks.[1] These blocks are then fed one-by-one into the cipher to produce the blocks that comprise the final ciphertext.
The Data Encryption Standard (DES) is the classical example of a block cipher. The cipher was originally designed by IBM and the NSA in the 1970s to secure government communications. In 1977, the cipher became publicly available and saw widespread use in many nongovernmental applications. The DES cipher was the de facto standard for encryption for 20 years, but despite that impressive history, DES has since been retired. We’ll see why that’s the case, but let’s first explore how the DES cipher actually works.
At the highest level, DES is a symmetric block cipher that operates on 64-bit blocks.[2] These blocks are fed through the cipher with a 56-bit key, which produces 64-bit blocks of ciphertext. Internally, DES is composed of a series of mathematical structures known as Feistel networks, and it’s these constructs that perform the actual encryption.
Encryption and Decryption with Feistel Networks
Encryption with DES is a fairly straightforward process. Before any encryption takes place, the input block’s bits are permuted in a pseudorandom way—that is, they’re shuffled around to mask their original order. The permuted block is then fed into the actual encryption process, which consists of 16 “rounds” (i.e., series of actions) that all perform identical operations. After the last round, there is a final permutation that undoes the initial permutation.[3] The result is a 64-bit block of ciphertext.
Before we check out the internals of the DES rounds, let’s briefly outline the DES key-scheduling algorithm. The cipher begins with a 56-bit key supplied by the user. Ideally, this key should be randomly generated and be different for each message. To effectively use the key, we need to use it somehow in each of the 16 rounds. We could use the entire 56-bit key each time, but that is highly predictable. Instead, a series of permutations and manipulations of the 56-bit key produce a 48-bit subkey k for each round (16 total subkeys). Each 48-bit subkey is merely a version of the original 56-bit key—there are only permutations, no complex computations. Each subkey is fed into its corresponding round.
Each DES encryption round consists of a Feistel network. Each network performs the same operation but with a different subkey produced by the key-scheduling algorithm. The 64-bit input block is split into two 32-bit halves (let’s call them L and R). The R half and the subkey k are fed into the function f (more on this later), and the output from that function undergoes exclusive-or (XOR) with L.[4] Finally, L and R are swapped in preparation for the next encryption round.[5] It’s important to note that R isn’t being encrypted by the function f. The actual encryption is achieved by the XOR operation in the Feistel network; the function f just manipulates R. Let’s dig a little deeper into that function f.
According to Shannon, a good cipher should provide confusion and diffusion. The function f implements these principles in the DES cipher using two inputs: The 32-bit sequence R and the 48-bit subkey k. We break down the function f into four steps.
First, we pass R through another function that expands R to 48 bits. This expansion provides diffusion by spreading out the original 32 bits across 48 bits via a permutation. Second, we perform XOR on the expanded R and the subkey k. The next step is critical to the DES cipher’s security.
Third, we put the result of the XOR through an S-box substitution step. This provides the confusion element and is resistant to cryptanalysis (i.e., it’s impossible to break). Essentially, we have eight S-boxes—an S-box is just a substitution, lookup table—that each take in six bits but produce four bits. We separate the 48-bit output from the XOR operation into eight 6-bit blocks, and each block is fed through a corresponding S-box. Each S-box itself is merely a substitution table that permutes the 6-bit blocks into 4-bit blocks. That is, the input bits are swapped out (substituted) according to some predetermined substitution table. When we take the S-box outputs together, we have a final 32-bit output (eight blocks times four bits equals 32 output bits). So, we reduced the original 48-bit input (from the XOR) to a 32-bit output. Finally, we shuffle the 32-bit output one last time, which completes the function f.
The shuffled 32-bit output from f undergoes XOR with L in the Feistel network. This XOR operation is the actual encryption. The 32-bit result from that XOR operation is then fed through to the next encryption round’s R side. The original R is fed through to the next round’s L side. In other words, we swap the L and R for the next encryption round. This process carries on in each encryption round.
All 16 encryption rounds follow that same process. Encryption with DES is simple in terms of computational complexity, and decryption is just as simple. Essentially, the decryption process in DES is the inverse of the encryption process—this will be a common theme for the other ciphers we see in this blog series. The Feistel network structure is basically the same, but we reverse the order of the initial and final permutations and the order of the subkeys. The important thing is to make sure the subkeys are used in the reverse order: Encryption subkey 16 is used in the first round of decryption, encryption subkey 15 is used in the second round of decryption, and so on. The end result is the original plaintext message. This simplicity is one of the overriding reasons why DES was so popular for 20 years.
Security and Alternatives
The DES cipher was widely used for 20 years, especially as a governmental standard. That history must mean it’s a secure cipher, right? Well, not exactly. For its time in the 1970s and 1980s, DES was probably secure enough, but it was sufficiently broken in 1998. If a computer could easily break DES in the 1990s, then there’s absolutely no hope for DES today. This is especially true as quantum computers become faster and cheaper. That’s why we no longer use DES in its original form. But where does DES breakdown, and how may it be attacked? Can we do anything to save DES?
The simple fact is that the 56-bit key DES uses is too short.[6] It’s too easy for an attacker to discover the key based on given plaintext, ciphertext pairs. Theoretical differential attacks require 247 pairs (140 trillion) to break DES, and theoretical linear attacks require just 243 pairs (8 trillion). Admittedly, those theoretical results don’t sound troubling, especially since they can be defeated by regularly changing encryption keys. The problem is that these theoretical results are rapidly becoming real. Advances in computing power and quantum computing mean that soon we’ll be able to process 8-140 trillion plaintext, ciphertext pairs rather quickly—perhaps in a matter of days, if not hours. This risk is too great to warrant reliance on DES or any similarly weak cipher.
Barring future developments in computing, there are also bruteforce attacks that are performed routinely today. These types of attacks try an exhaustive search of all keys. That is, a known ciphertext is decrypted using all possible keys until the correct plaintext is found—the key that works is assumed to be the correct key.[7] The underlying security assumption is that such attacks are too costly, even for well-resourced state agencies. But, the validity of that assumption is highly dubious.
That assumption was finally disproven by two successful bruteforce attacks that effectively killed DES. In 1998, the Electronic Frontier Foundation (EFF) used special-purpose hardware (codename “Deep Crack”) to break DES in a matter of days. The cracking machine was built for less than $250,000, which showed that any comfortably financed individual or group could break DES. In 2007, university researchers developed the COPACOBANA cracking machine for just $10,000. This machine can crack DES in as little as 1.5 days, much faster than EFF’s Deep Crack. These results signaled the death knell for DES. It was made painfully clear that DES cannot cope with today’s computing power, though it may have been secure just a couple decades ago.
Not all hope for block ciphers has died with DES, however. In fact, it’s possible to achieve a strong level of security using DES. Instead of relying on only one encryption with DES, we encrypt a plaintext message three times with three different keys.[8] This so-called Triple DES (3DES) is much securer than regular DES. Despite the comparative security of 3DES, there was a desire in the 1990s to create a new, stronger cipher independent of the DES design. As such, researchers created the AES, which has since become the de facto world standard for symmetric block ciphers—and for good reason, as we’ll see next time.
