Breaking Double DES with Meet-in-the-Middle

Breaking Double DES with Meet-in-the-Middle

Introduction

When DES started to look weak, an obvious fix suggested itself: run it twice, with two different keys. Double DES encrypts a block as C = E(K2, E(K1, P)). Two 56-bit keys should mean 112 bits of key, and a brute-force search of 2^112 keys is hopeless forever.

It does not work out that way. A meet-in-the-middle attack recovers both keys in roughly the time of a single DES key search, not the square of it. Double DES buys about one extra bit of real security over single DES, not fifty-six. This guide shows the attack against real, full DES, recovers both keys, and explains why the fix the world actually adopted was triple DES with three encryptions.

Table of Contents

• Why Twice Should Be Enough
• Meeting in the Middle
• The Memory-for-Time Trade
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Limitations
• Security Status
• FAQ
• References

Why Twice Should Be Enough

Single DES has a 56-bit key, which is 2^56 possibilities. In 1998 the Electronic Frontier Foundation’s Deep Crack machine searched that whole space in days, so DES was finished as a standalone cipher. Double DES looks like the natural rescue. Encrypt with K1, then encrypt that result with K2, and an attacker seems to face 2^56 times 2^56, which is 2^112 keys.

The flaw is that the two encryptions can be attacked separately. The attacker does not have to guess both keys at once. Given a single known plaintext and its ciphertext, they can work forward from the plaintext and backward from the ciphertext and look for where the two meet in the middle. That turns a 2^112 problem into something close to 2^57.

Meeting in the Middle

Write the double encryption with its middle value named:

P --E(K1)--> M --E(K2)--> C

The midpoint M is E(K1, P), and it is also D(K2, C), the ciphertext decrypted once under K2. The attacker knows P and C but not M, K1, or K2. The attack finds M by meeting there from both sides:

1. Forward. For every possible K1, compute M = E(K1, P) and store the pair M -> K1 in a table.
2. Backward. For every possible K2, compute M' = D(K2, C) and look M' up in the table. A hit means some K1 produced the same midpoint, so (K1, K2) is a candidate key pair.
3. Confirm. A reduced search can throw up a rare false match, so check each candidate against a second known plaintext-ciphertext pair. The pair that works for both is the real key.

The forward pass does 2^56 encryptions and the backward pass does 2^56 decryptions, so the total work is about 2^57, not 2^112. The cost is memory: the table has to hold 2^56 midpoints.

The Memory-for-Time Trade

A full 2^56 table is far too big to run in a browser, so this guide shrinks the keyspace while keeping the attack exactly the same. Each key has its first six bytes known and its last two bytes searched, the same device the DES brute-force breaker uses. Two unknown bytes carry fourteen real key bits, so each key has 2^14, or 16,384, candidates.

With that reduction, brute-forcing both keys together would take 2^14 times 2^14, which is 2^28, or about 268 million DES operations. The meet-in-the-middle attack instead does one forward pass of 16,384 encryptions, then a backward pass that stops as soon as it finds the meet. The difference between the two is the whole point of the attack, shrunk to a size you can watch run.

Interactive Visualizer

The visualizer above runs the real meet-in-the-middle attack on reduced-key double DES. It builds the forward table, then searches backward until the midpoints meet, and shows the recovered keys, the meeting value, and the exact number of DES operations it used. Beside that it shows how many operations brute-forcing both keys would have taken, so the saving is visible directly.

The DES inside is the full cipher, the same implementation the DES guide verifies against the official test vectors. Only the keyspace is reduced, by fixing the first six bytes of each key, so the attack finishes in a moment instead of a geological age.

A Worked Example

The example encrypts under the DES guide’s own test key 133457799BBCDFF1 as K1 and a second standard DES test key 0E329232EA6D0D73 as K2. The attacker knows two plaintext-ciphertext pairs and the first six bytes of each key. The double-DES ciphertext of 0123456789ABCDEF is:

2DES ciphertext of P1: B4A46FBF0342085D

The attack builds a forward table of 16,384 midpoints, then searches backward until a midpoint matches:

recovered K1: 133457799BBCDFF1
recovered K2: 0E329232EA6D0D73
meet in the middle at: 85E813540F0AB405
DES operations used: 17210 (forward table of 16384 entries)
brute-forcing both keys would take: 268435456 DES operations

Both keys come back exactly. The meeting value 85E813540F0AB405 is the single-DES encryption of the plaintext under K1, which is the midpoint M. The attack used 17,210 DES operations against the 268 million a brute-force of both keys would need, a saving of more than ten thousand times, and that ratio only grows as the keys get longer.

Python Implementation

The DES core is the DES guide’s own encryption code. On top of it sit double encryption and the meet-in-the-middle search, which returns both keys and the midpoint they met at.

# double_des_mitm.py
#
# Meet-in-the-middle attack on double DES. 2DES encrypts with C = E(K2, E(K1, P)). Encrypting twice
# looks like it should double the 56-bit key to 112 bits of security. It does not. A meet-in-the-middle
# attack trades memory for time and recovers both keys in roughly the work of ONE key search, which is
# why real triple DES uses three encryptions, not two. To keep the demo runnable, each key here has its
# first 6 bytes known and its last 2 searched (2^14 = 16,384 candidates each), exactly as the DES
# brute-force breaker does. The DES core below is the DES guide's own code, encryption only.


# ---- DES (from the DES guide) ----

IP = [58,50,42,34,26,18,10,2, 60,52,44,36,28,20,12,4,
      62,54,46,38,30,22,14,6, 64,56,48,40,32,24,16,8,
      57,49,41,33,25,17,9,1, 59,51,43,35,27,19,11,3,
      61,53,45,37,29,21,13,5, 63,55,47,39,31,23,15,7]

FP = [40,8,48,16,56,24,64,32, 39,7,47,15,55,23,63,31,
      38,6,46,14,54,22,62,30, 37,5,45,13,53,21,61,29,
      36,4,44,12,52,20,60,28, 35,3,43,11,51,19,59,27,
      34,2,42,10,50,18,58,26, 33,1,41,9,49,17,57,25]

E = [32,1,2,3,4,5, 4,5,6,7,8,9, 8,9,10,11,12,13, 12,13,14,15,16,17,
     16,17,18,19,20,21, 20,21,22,23,24,25, 24,25,26,27,28,29, 28,29,30,31,32,1]

P = [16,7,20,21, 29,12,28,17, 1,15,23,26, 5,18,31,10,
     2,8,24,14, 32,27,3,9, 19,13,30,6, 22,11,4,25]

PC1 = [57,49,41,33,25,17,9, 1,58,50,42,34,26,18,
       10,2,59,51,43,35,27, 19,11,3,60,52,44,36,
       63,55,47,39,31,23,15, 7,62,54,46,38,30,22,
       14,6,61,53,45,37,29, 21,13,5,28,20,12,4]

PC2 = [14,17,11,24,1,5, 3,28,15,6,21,10, 23,19,12,4,26,8,
       16,7,27,20,13,2, 41,52,31,37,47,55, 30,40,51,45,33,48,
       44,49,39,56,34,53, 46,42,50,36,29,32]

SHIFTS = [1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1]

SBOX = [
 [[14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7],[0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8],
  [4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0],[15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13]],
 [[15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10],[3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5],
  [0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15],[13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9]],
 [[10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8],[13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1],
  [13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7],[1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12]],
 [[7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15],[13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9],
  [10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4],[3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14]],
 [[2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9],[14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6],
  [4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14],[11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3]],
 [[12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11],[10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8],
  [9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6],[4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13]],
 [[4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1],[13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6],
  [1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2],[6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12]],
 [[13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7],[1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2],
  [7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8],[2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11]],
]


def permute(bits, table):
    return [bits[i - 1] for i in table]


def bytes_to_bits(data):
    return [(byte >> (7 - i)) & 1 for byte in data for i in range(8)]


def bits_to_bytes(bits):
    return bytes(int("".join(map(str, bits[i:i + 8])), 2) for i in range(0, len(bits), 8))


def xor(a, b):
    return [x ^ y for x, y in zip(a, b)]


def generate_subkeys(key_bytes):
    permuted = permute(bytes_to_bits(key_bytes), PC1)
    C, D = permuted[:28], permuted[28:]
    subkeys = []
    for shift in SHIFTS:
        C = C[shift:] + C[:shift]
        D = D[shift:] + D[:shift]
        subkeys.append(permute(C + D, PC2))
    return subkeys


def feistel(R, subkey):
    x = xor(permute(R, E), subkey)
    output = []
    for i in range(8):
        block = x[i * 6:(i + 1) * 6]
        row = (block[0] << 1) | block[5]
        col = (block[1] << 3) | (block[2] << 2) | (block[3] << 1) | block[4]
        val = SBOX[i][row][col]
        output.extend([(val >> 3) & 1, (val >> 2) & 1, (val >> 1) & 1, val & 1])
    return permute(output, P)


def des_block(block_bytes, subkeys):
    bits = permute(bytes_to_bits(block_bytes), IP)
    L, R = bits[:32], bits[32:]
    for subkey in subkeys:
        L, R = R, xor(L, feistel(R, subkey))
    return bits_to_bytes(permute(R + L, FP))


# ---- The brute-force attack ----


def with_odd_parity(b7):
    # 7 key bits in the top of the byte, parity bit in the lowest position
    byte = b7 << 1
    return byte | (bin(byte).count("1") % 2 == 0)


def candidate_keys(known_prefix, unknown_bytes):
    for n in range(2 ** (7 * unknown_bytes)):
        tail = bytearray()
        for i in reversed(range(unknown_bytes)):
            tail.append(with_odd_parity((n >> (7 * i)) & 0x7F))
        yield n, known_prefix + bytes(tail)



# ---- the attack ----
def des_encrypt(key, block):
    return des_block(block, generate_subkeys(key))


def des_decrypt(key, block):
    # DES decryption is encryption with the 16 subkeys applied in reverse order
    return des_block(block, generate_subkeys(key)[::-1])


def two_des_encrypt(k1, k2, block):
    return des_encrypt(k2, des_encrypt(k1, block))


def meet_in_the_middle(prefix1, prefix2, unknown, pairs):
    # Forward: encrypt the known plaintext under every K1 candidate, storing the midpoint -> K1.
    # Backward: decrypt the ciphertext under every K2 candidate; a midpoint already in the table is a
    # candidate pair. A second known pair rules out the rare false collision.
    p1, c1 = pairs[0]
    ops = 0
    table = {}
    for _, k1 in candidate_keys(prefix1, unknown):
        table[des_encrypt(k1, p1)] = k1
        ops += 1
    for _, k2 in candidate_keys(prefix2, unknown):
        midpoint = des_decrypt(k2, c1)
        ops += 1
        k1 = table.get(midpoint)
        if k1 is not None and all(two_des_encrypt(k1, k2, p) == c for p, c in pairs):
            return k1, k2, midpoint, ops, len(table)
    return None, None, None, ops, len(table)


if __name__ == "__main__":
    K1 = bytes.fromhex("133457799BBCDFF1")   # the DES guide's own test key
    K2 = bytes.fromhex("0E329232EA6D0D73")   # a second standard DES test key
    P1 = bytes.fromhex("0123456789ABCDEF")
    P2 = bytes.fromhex("4E6F772069732074")   # "Now is t"
    C1 = two_des_encrypt(K1, K2, P1)
    C2 = two_des_encrypt(K1, K2, P2)
    print("2DES ciphertext of P1:", C1.hex().upper())

    unknown = 2
    prefix1, prefix2 = K1[:8 - unknown], K2[:8 - unknown]
    k1, k2, midpoint, ops, table_size = meet_in_the_middle(prefix1, prefix2, unknown, [(P1, C1), (P2, C2)])
    print("recovered K1:", k1.hex().upper())
    print("recovered K2:", k2.hex().upper())
    print("meet in the middle at:", midpoint.hex().upper())
    print("DES operations used:", ops, "(forward table of", table_size, "entries)")
    print("brute-forcing both keys would take:", (2 ** (7 * unknown)) ** 2, "DES operations")

Running it prints the worked example:

2DES ciphertext of P1: B4A46FBF0342085D
recovered K1: 133457799BBCDFF1
recovered K2: 0E329232EA6D0D73
meet in the middle at: 85E813540F0AB405
DES operations used: 17210 (forward table of 16384 entries)
brute-forcing both keys would take: 268435456 DES operations

Limitations

This demonstrates the real attack on a deliberately reduced keyspace:

• The keys are shortened for the demo. Each key has its first six bytes fixed and its last two searched, giving 16,384 candidates per key. The full attack works identically on complete 56-bit keys, but its 2^56-entry table cannot run in a browser or a quick script.
• It needs known plaintext. The attacker must know at least one plaintext-ciphertext pair, and a second pair to rule out the rare false collision in a reduced search.
• It trades memory for time. The forward table holds one entry per K1 candidate. On full DES that table would need petabytes, which is the attack’s real-world cost and the reason it is a theoretical bound as much as a practical recipe.

Security Status

• Double DES is not used, because of this attack. The meet-in-the-middle result, due to Diffie and Hellman in 1977, is why no one standardized two-key double DES. Its real security is about 2^57, one bit above single DES, nowhere near the 2^112 the key length suggests.
• Triple DES was the answer. Running DES three times as E(K3, D(K2, E(K1, P))) resists the simple meet in the middle. A meet-in-the-middle attack still applies across the three stages, so three-key triple DES gives about 2^112 security rather than the full 2^168. That is comfortably out of reach, which is why triple DES survived for decades after single DES fell.
• The lesson generalizes. Composing a cipher with itself under independent keys rarely multiplies security the way the key length implies. Meeting in the middle is the standard reason why, and it is why modern ciphers reach for longer keys and more rounds rather than simple repetition.

FAQ

Why doesn’t encrypting twice double the security?

Because the two encryptions can be attacked one at a time instead of together. Working forward from the plaintext and backward from the ciphertext, an attacker searches each key’s space once and matches the results in the middle, which costs about twice a single search rather than its square.

What is the midpoint value?

It is the block halfway through double encryption: the plaintext encrypted once under K1, which is the same as the ciphertext decrypted once under K2. The attack succeeds by finding the key pair that makes those two values equal.

Why is a second plaintext-ciphertext pair needed?

A reduced or even a full search can produce a midpoint collision for a wrong key pair by chance. Checking each candidate against a second known pair eliminates those false hits, leaving the real keys.

How does this relate to triple DES?

Triple DES exists precisely because double DES fails here. Three encryptions push the meet-in-the-middle cost up to about 2^112, which is secure, where two encryptions leave it near 2^57, which is not.

Is this a practical attack on real DES keys?

The time is practical, about twice a single DES search, but the memory is not. A full attack needs a table of 2^56 entries. The reduction used here keeps the method identical while shrinking both the time and the table to something you can run immediately.

References

1. Diffie, Whitfield, and Martin Hellman. “Exhaustive Cryptanalysis of the NBS Data Encryption Standard,” Computer, 1977 (the paper that introduced the meet-in-the-middle attack on double encryption).

2. The DES guide on this site, whose DES implementation this breaker reuses: /blog/des_guide/

3. The DES brute-force breaker on this site, which searches a single DES key the same reduced way: /blog/des_bruteforce_breaker_guide/