This is an article in a series on Cryptography for the Everyday Developer. Follow along to learn the basics of modern cryptography and encryption.

When the Data Encryption Standard (DES) was introduced in the 1970s, it was considered a solid block cipher. But DES has one major flaw by today’s standards — a small key space. With only 56 bits of key material, DES can be brute-forced with modern hardware by checking every possible key value. Once it was apparent that DES was no longer secure and could be brute-forced, a natural idea to extend the life of DES without resorting to an entirely new algorithm was to increase the size of the key space by encrypting the data twice with two different keys. The hope was that doubling the encryption operation with different keys would increase the difficulty of brute force attacks.

Double Encryption

The idea behind double encryption is relatively simple:

  1. Encrypt a plaintext message \(x\) with key \(k_L\)
  2. Encrypt the result again with a second key \(k_R\)

Mathematically, this can be expressed as:

$$ y = E(k_R, E(k_L, x)) $$

At first glance, computing a brute force solution to this equation looks daunting:

  • There are \(2^{56}\) possible values for \(k_L\)
  • For each choice of \(k_L\), there are \(2^{56}\) possible values for \(k_R\)

Put together, that’s \(2^{56} \times 2^{56} = 2^{112}\) possible key pairs: far too large of a key space to be cracked with a brute force approach.

The Meet-in-the-Middle Attack

At first glance, double encryption seems to increase the security of the algorithm. However, the meet-in-the-middle attack leverages the idea that you don’t need to search the entire \(2^{112}\) space at once. Instead, you can break the problem into two halves that “meet in the middle.”

The attack works in two phases:

Phase 1: Precompute the Left Side

Take the plaintext \(x\) and encrypt the text with all possible left keys \(k_L\).

  • For each possible key \(k_L\), compute \(E(k_L, x) = a\); the encryption of the plaintext using key \(k_L\)
  • Store the result in a table, using the intermediate value \(a\) as the lookup key, and the candidate encryption key \(k_L\) as the value.

Precomputing all possible results of encryption with \(k_L\) requires \(2^{56}\) encryption operations, and a database of size \(2^{56}\) to store the results.

Phase 2: Brute Force the Right Side

Now, start from the ciphertext \(y\).

  • For each possible key \(k_R\), compute \(D(k_R, y) = b\); the decryption of the ciphertext using key \(k_R\)
  • Check if this intermediate result \(b\) has a matching key in one of the precomputed values from the table from Phase 1

If a match is found, you’ve identified a candidate \((k_L, k_R)\) pair. With enough known plaintext/ciphertext pairs, you can rule out false positives and derive the composite encryption key, breaking the cipher.

The meet-in-the-middle attack reduces the complexity of attacking double DES to \(2^{57}\) operations taking \(2^{56}\) space. That’s only marginally better than single DES. Instead of gaining an effective 112-bit key, double encryption only provides around 57 bits of effective security. Not nearly enough to withstand brute force attacks.

Interestingly, since the meet-in-the-middle attack can only be applied in one place (i.e. there is only one middle) encrypting data three times instead of two, does increase security, which has been applied successfully in the development of triple DES (3DES), which applies DES three times with three different keys. Since the meet-in-the-middle attack can only be applied in one place, 3DES is secure: one side of the key space is \(2^{56}\), which can be brute-forced, but the other is \(2^{112}\), which is not feasible to brute force attack.

Double DES looked like an easy way to extend the lifetime of an aging cipher. But the meet-in-the-middle attack shows that the security gain is negligible. This attack demonstrates a broader lesson in cryptography: you can’t simply stack ciphers and expect their security to automatically be more effective. You have to instead think carefully about how your algorithm is composed.