Meeting in the Middle on Double and Triple DES

Attack double encryption from both ends. Two separate key searches replace one search over both keys. The page prices the attack in time, memory, and known pairs.

CryptanalysisMeet in the middledemo

Objectives

Order the steps of a meet-in-the-middle attack on a double encryption.
Compute the time, the memory and the known pairs the attack needs at a chosen key size.
Contrast the cost of a nested key search against the cost of two independent searches.
Predict how many key pairs survive a match on one known pair, and on two.
Justify the claim that memory, not time, is what keeps this attack from being run.

17%

A double encryption holds one intermediate value that each half of the key material can name on its own, and splitting the cipher there turns a product of key spaces into a sum.

Double encryption applies DES twice, under two independent keys. That is 112 bits of key material. Call the value between the two encryptions A.

A = E(K1, P)
C = E(K2, A)
A = D(K2, C)

The third line is the attack. A guess of K1 alone names a value of A from the left. A guess of K2 alone names a value of A from the right. Neither guess needs the other key, so the two key spaces can be searched separately and compared at A. Diffie and Hellman described this split in IEEE Computer 10(6), 1977.

Plaintext P (hex, 64 bits)

reads as 01 23 45 67 89 AB CD EF

First key K1 (hex, 64 bits)

reads as 13 34 57 79 9B BC DF F1

Second key K2 (hex, 64 bits)

reads as 0E 32 92 32 EA 6D 0D 73

One intermediate value, reached from both ends

This table lists the plaintext, the intermediate value the first encryption produces, the ciphertext the second encryption produces, and the same intermediate value recovered by decrypting the ciphertext under the second key.
Value	How it is computed	Hex
P	the known plaintext	0123456789ABCDEF
A	E(K1, P)	85E813540F0AB405
C	E(K2, A)	B4A46FBF0342085D
A	D(K2, C)	85E813540F0AB405

both routes give one block

The attacker holds P and C, the two rows in plain weight. A is never transmitted, and the attacker never receives it. The two marked rows show that a correct guess of either key computes it.

One result has to hold before any of this is worth doing. Campbell and Wiener, CRYPTO 1992, proved that DES is not a group. If it were, two encryptions under K1 and K2 would equal one encryption under some third key, and the second key would add nothing at all. The 112 bits are real key material. What follows is about the work of finding them.

Now run the attack. A real DES key has 56 effective bits, and 2^56 encryptions is not something a browser can do, so the search below shrinks the key space. A candidate key carries w bits in positions the first permuted choice keeps, and every other bit is held fixed. The cipher is the real DES on all of them.

Effective key bits searched, w

Two keys were drawn from that space and used to produce the target ciphertext below. The search does not know them. It sweeps 2^12 first keys, then 2^12 second keys, for 2^13 = 8,192 DES operations, about 1.2 seconds here.

The shrunken attack, w = 12

what the attacker holds

plaintext P             0123456789ABCDEF
ciphertext C            45FC3A8CA6CF1435
key space               2^12 first keys, 2^12 second keys

Nothing has been searched yet at this width. The button runs the two passes and writes the recovered pair here.

This is the real attack at a toy size. The real one sets w = 56, which is 2^44 times the operations a sweep at w = 12 costs. Nothing else about it changes: the same two passes, the same table, the same match.

Count the same search two ways, at the same width. Guessing key pairs multiplies the two key spaces. Meeting in the middle adds them.

Nested search, w = 12

guesses of K1           2^12 = 4,096
guesses of K2, each     2^12 = 4,096
DES operations          2^24 = 16,777,216
values stored           0

Every guess of K1 is tried against every guess of K2, so the count is a product. It needs no memory at all.

Meet in the middle, w = 12

forward table           2^12 = 4,096
backward sweep          2^12 = 4,096
DES operations          2^13 = 8,192
values stored           2^12 = 4,096

Each key space is swept once and the table holds the results of the first sweep, so the count is a sum. The memory is the price.

The two predictions against the measurement

This table sets the operation count of a nested key search and the operation count of a meet in the middle attack beside the number of DES operations the search in the previous step actually ran.
Strategy	Count	DES operations	Time here
Nested	2^12 x 2^12	16,777,216	42 minutes
Met in the middle	2^12 + 2^12	8,192	1.2 seconds
Measured	the run above	not run yet

The nested figure is not an estimate of a slower program. It is what an attacker without the table has to do, and at w = 12 it is 2,048 times the work of the attack that just ran.

A product became a sum because one value, A, can be named from either end with half the key material. Any construction that has such a value is open to the same split, whatever the primitive is. That is the reason a designer counts key material and attack cost as two different things.

Return w to its real value of 56, and the arithmetic does not change. The forward pass is 2^56 encryptions, the backward pass is 2^56 decryptions, and the total is 2^57.

Double DES against the full key space

This table gives the cost of searching a single DES key, the key material of double DES, the cost a nested search would have, the cost of the meet in the middle attack, and the size and wall clock of the table that attack has to hold.
Quantity	Value	Note
Single DES key search	2^56	what one key costs
Double DES key material	112 bits	two independent keys
Nested search	2^112	what the key material suggests
Met in the middle	2^57	one pass each way
Table entries	2^56	one intermediate and one key each
Table size	1 EiB	at 16 bytes an entry
Wall clock	2 days	at 1 trillion operations a second

The second key adds 56 bits of key material. Against this attack it adds 1 bit of cost. That single bit is the reason the standards moved to three keys rather than two encryptions.

Read the two marked numbers together. The time is 2 days at a rate the 1998 hardware search of single DES already shows is reachable. The memory is 1 EiB, which is data centre scale rather than machine scale, and every one of the 2^57 operations needs a random read from it. Memory is the binding cost here, not time.

An attacker can hold a smaller table and recompute the rest. Storing 2^m entries needs 2^(56 - m) passes, so the time rises to 2^(112 - m). Time multiplied by memory stays near 2^112 wherever the split is set, which is why no choice of table size makes the attack cheap.

One question is still open. The search returned a key pair, but is it the key pair? There are 2^112 candidate pairs and only 2^64 possible values of A, so many pairs send this P to this C by accident.

known pairs the attacker holds

1 known plaintext and ciphertext pair

This table lists the plaintext and ciphertext of each known pair the attacker holds, encrypted under the two keys typed in the first step.
Pair	Plaintext	Ciphertext
1	0DA64A824245C549	8B08A0476670763D

key pairs that survive the match

candidate key pairs     2^112
values of A             2^64
pairs tested against    1
expected survivors      2^48

about 2^48 survivors, the key is not named

One pair leaves about 2^48 key pairs, near 281 trillion of them, so the search names a set and not a key. A textbook that stops at "the attack recovers the key" has stopped one step early.

The shrunken search in the earlier step returned exactly one match for the same reason, read the other way. At w = 12 there are 2^24 candidate pairs against 2^64 values of A, so the expected count of accidental matches is 2^-40. A small key space and one known pair is a comfortable position that the real key space does not give.

Three-key TDEA encrypts, decrypts and encrypts again under three keys. The same question applies to it: is there a value both sides can name with part of the key material?

C = E(K3, D(K2, E(K1, P)))
E(K2, D(K3, C)) = E(K1, P)

Third key K3 (hex, 64 bits)

reads as 1F 1F 1F 1F 0E 0E 0E FE

The split identity on real values

This table lists the plaintext, the triple encryption of it, the value one key produces from the left, and the value two keys produce from the right, which are the two sides of the split identity.
Value	How it is computed	Hex
P	the known plaintext	0123456789ABCDEF
C	E(K3, D(K2, E(K1, P)))	1FBA8F224F801AE3
left side	E(K1, P)	85E813540F0AB405
after K3	D(K3, C)	371F995CA267FB42
right side	E(K2, D(K3, C))	85E813540F0AB405

the two sides are one block

One block is an example rather than evidence. The button runs the same identity on 64 random blocks under these three keys, which is 384 DES operations. Nothing here sweeps a key space.

The left side names one key. The right side names two. That is the difference from double encryption, where both sides named one.

What the split costs against three keys

This table gives the key material of three-key TDEA, the size of the stored side and the enumerated side of the attack, the resulting attack cost, and the size of the table.
Quantity	Value	Which side
Key material	168 bits	three independent keys
Stored	2^56	every K1, from the plaintext
Enumerated	2^112	every pair K2 and K3, from the ciphertext
Attack cost	2^112	set by the larger side
Table size	1 EiB	at 16 bytes an entry

Time follows the larger side and memory follows the smaller one, so the attack runs in 2^112 with 2^56 stored. This is the Diffie and Hellman split once more, with one key stored and a key pair enumerated. It is why NIST SP 800-57 credits three-key TDEA with 112 bits of security and not 168.

Two-key TDEA, where K3 equals K1, is attacked differently again. Merkle and Hellman, CACM 24(7), 1981, gave a chosen-plaintext attack on two-key triple encryption. van Oorschot and Wiener, EUROCRYPT 1990, gave the known-plaintext form. It costs about 2^121 divided by N operations for N known pairs. That constant is 57 search bits and 64 block bits, because every guessed intermediate value pays for two key searches and not one. At N = 2^40 known pairs the cost is 2^81 operations. NIST SP 800-57 credits two-key TDEA with 80 bits, which is the same estimate with the factor of two dropped. Those costs are priced on a page of their own.

No meet-in-the-middle attack on double or triple DES has ever been run. The operation counts are not what stops it: 2^57 is 2 days at the rate in the table above, and single DES fell to real hardware in 1998. The table of 1 EiB is the reason. Every attack on this page trades memory for time, and memory is the limit.

The DES behind this page is a teaching implementation. It is written to be read, it is not constant time, and it is not for production use.

step 1/6

CPE 645 / CS 685

Meeting in the Middle on Double and Triple DES

Double DES and the Triple DES Keying Options

Trading Known Plaintext for Time Against Two-Key TDEA