Trading Known Plaintext for Time Against Two-Key TDEA

Guess the 64-bit value in the middle, then run the two key searches it opens. A slider shows how more known pairs reduce the work, and how that compares with the 80 bits NIST credits.

CryptanalysisTime and data tradeoffdemo

Objectives

Explain why guessing a 64-bit intermediate is the entry point when one key sits at both ends.
Compute the expected number of guesses and the attack time from a chosen count of known pairs.
Analyze the constant 121 into its 57 search bits and its 64 block bits.
Predict how many candidate first keys the outer key search leaves at 2^40 known pairs.
Distinguish the counted 2^81 figure from the 80 bits NIST SP 800-57 credits, and both from the 112 bits of key material.

17%

The attacker guesses a 64-bit intermediate value, and each guess pays for two key searches. Every known pair removes one bit from the guessing, which is the 2^121 divided by N trade.

Two-key TDEA encrypts a block three times under two keys: C = E(k1, D(k2, E(k1, P))). An attacker who holds matching plaintext and ciphertext holds the two ends of that chain. Each pair also hides two values inside it, A after the first encryption and B after the decryption in the middle.

4 known pairs under one two-key bundle

Each row gives one known pair under a single two-key bundle, with the plaintext and the ciphertext the attacker holds and the two intermediate values the attacker does not.
Pair	P, known	A, hidden	B, hidden	C, known
1	0DA64A824245C549	hidden	hidden	011D9E7210F14D46
2	AEEC0E06CF3B4310	hidden	hidden	C82A975141C4A924
3	4DF7AE38351CEAB9	hidden	hidden	D30AA83347115087
4	6CB5D6B69B357434	hidden	hidden	F3E749539CD8DD70

P and C are what a known-plaintext attacker collects. A and B stay inside the cipher, and no query returns them. Both intermediates and both keys are unknown at the same time.

The attack on double encryption splits the chain at its one intermediate and meets there. Two-key TDEA denies that split, because k1 is used at both ends of the construction.

Where the split works, and where it fails

the intermediate A, reached from each side

double DES        C = E(k2, E(k1, P))
  from the left   A = E(k1, P)              k1 alone
  from the right  A = D(k2, C)              k2 alone

two-key TDEA      C = E(k1, D(k2, E(k1, P)))
  from the left   A = E(k1, P)              k1 alone
  from the right  A = E(k2, D(k1, C))       k1 and k2 together

In double encryption the two sides name different keys, so a stored sweep of k1 meets a second sweep of k2 and the work is a sum. That is Diffie and Hellman, Exhaustive Cryptanalysis of the NBS Data Encryption Standard, Computer 10(6), 1977.

In two-key TDEA the right side names k1 as well as k2. A sweep of second keys cannot start until a first key is already fixed, so there is nothing to meet. The attacker has to supply the missing value instead, and the value to supply is the intermediate.

What a candidate first key exposes

One identity survives the failure of the split. C = E(k1, B), so B = D(k1, C). A first key and the known ciphertext give the second intermediate directly, with no second key involved. Reveal B for the true k1 and compare it against the hidden value.

This is what makes a two-phase attack possible at all. A guessed A plus a candidate k1 fixes B, and B is where the second key search can meet the first.

The known-plaintext form of this attack is van Oorschot and Wiener, A Known-Plaintext Attack on Two-Key Triple Encryption, EUROCRYPT 1990. Its cost is about 2^121 divided by the number of known pairs, and the rest of this page is where that constant comes from.

The attacker picks a 64-bit value and treats it as A for one of the known pairs. With N known pairs there are N right values among the 2^64 a draw can return. One draw is right with probability N in 2^64. About 2^64 divided by N draws are expected before one is right.

Draw a 64-bit value and test it

the drawn value

no draw yet

This table compares the chance of guessing the intermediate and the expected number of guesses for the 4 known pairs on this page and for the 2^40 known pairs the usual figure assumes.
Known pairs held	Chance one draw is right	Expected draws
4, this page	1 in 2^62	2^62
2^40, the usual assumption	1 in 2^24	2^24, which is 16,777,216

The button will not find a hidden A. At 4 known pairs the expected number of draws is 2^62. The page draws one value per press.

The guess is the only place a known pair helps. Each doubling of the pairs removes one bit from the guessing, so 2^t pairs leave 2^(64 - t) intermediates to try. That single exponent is the whole tradeoff. The rest of this page counts what one guess costs, and then what the whole attack costs.

Fix one guessed value a. Phase one is the search for the outer key. It sweeps every first key k and computes D(k, a). If that block is one of the known plaintexts, then k is a candidate first key for that pair, and B = D(k, C) is stored beside it.

A miniature of phase one

The real sweep is 2^56 keys. The sweep below masks a DES key to a chosen number of effective bits, holds 4 known pairs, and matches on the top 10 bits of the block. Its survivor count follows the same formula as the real one, with each of the three terms shrunk: key bits plus known pairs minus block bits.

Effective key bits in the miniature

the miniature bundle and the guessed intermediate

first key k1, index 167 of the space          010101010101024F
second key k2, index 92 of the space          01010101010101B9
guessed intermediate a, correct for pair 1    54531BAB59E09997
keys to sweep                                 4,096
expected survivors, 2^(12 + 2 - 10)           16
estimated time for this sweep                 under a second

At full scale the same count is 2^(56 + 40 - 64), which is about 2^32 candidate first keys. Phase one narrows 2^56 keys by 24 bits and stops there. The code behind this page is a teaching implementation of DES, and it is not for production use.

Phase two is the search for the inner key. It reads the same guessed value from the other side: for every second key k2 it computes D(k2, a) and reads the table phase one built, which is indexed by B. A match names a first key and a second key at once.

A miniature of phase two

The sweep below runs at the width phase one used. Every candidate from phase one sits in one table, so the sweep of second keys is run once and serves all of them.

Run phase one first. Phase two needs its table, and a change of width discards it.

One guessed intermediate pays for two key searches, one on each side. The count printed above shows why they are added and not multiplied: every candidate first key from phase one waits in a single table, so one sweep of second keys serves all of them.

At full scale each guessed intermediate costs 2^56 decryptions in phase one and 2^56 in phase two. Together that is 2^56 + 2^56 = 2^57 DES operations for one guess. That exponent of 57 is the search half of the constant on the next step.

Now the two costs multiply. With 2^t known pairs the attacker expects 2^(64 - t) guessed intermediates, and each one costs about 2^57 operations. The product is 2^(121 - t), which is the whole curve.

Known pairs against time

Known pairs held, as an exponent of two

the chosen point on the curve

known pairs                                   2^40
guessed intermediates                         2^24
DES operations per guess                      2^57
DES operations in total                       2^81
known-pair data                               16 TiB

Each row gives a count of known pairs, the number of guessed intermediates it leaves, the attack time in DES operations with a bar for that time, the data the pairs occupy, and a note marking the usual assumption and the point the slider sits on.
Known pairs	Guesses	Time	Data	Note
2^10	2^54	2^111	16 KiB
2^20	2^44	2^101	16 MiB
2^30	2^34	2^91	16 GiB
2^40	2^24	2^81	16 TiB	the usual assumption, slider here
2^50	2^14	2^71	16 PiB

The row with the rule down its left edge, labelled the usual assumption, is the one every table of security strengths quotes. It is one point on this curve and not a property of the construction. Every other row is the same attack with a different assumption about data.

Read the constant. 121 is 57 search bits plus 64 block bits. The 57 is the two key searches one guess pays for, 2^56 + 2^56 = 2^57. The 64 is the block, because the value the attacker guesses is a block and not a key. That is why the number is not 112, the key material the construction stores.

Two numbers describe two-key TDEA and they are not the same kind of fact. One is the key material the construction stores. The other is the cost of the best known attack, and that cost moves with an assumption about data.

What each number is a fact about

This table separates the key material two-key TDEA stores from the cost of the attack at the usual data assumption and from the security strength NIST credits.
Quantity	Value	What it is a fact about
Independent key material	112 bits	the construction, two DES keys
Attack time at 2^40 known pairs	2^81 DES operations	one attack under one data assumption
Data that assumption needs	16 TiB	the same assumption, collected under one bundle
Credited security strength	80 bits	NIST SP 800-57, which drops the constant

The counted figure and the credited figure come from the same attack. This page counts both key searches, so its constant is 121 and its answer at 2^40 known pairs is 2^81. The familiar 80-bit estimate suppresses constants or includes further improvements, and NIST SP 800-57 credits two-key TDEA with 80 bits of security. One number is counted and the other is credited.

Keep the two numbers apart. Two-key TDEA holds 112 bits of independent key material, and that is a fact about the construction. Its best known attack costs about 2^81 operations at 2^40 known pairs, and that is a fact about one attack under one data assumption. Change the data and the second number changes. The first one does not move.

Everything on this page was computed by a teaching implementation of DES. 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

Trading Known Plaintext for Time Against Two-Key TDEA

Meeting in the Middle on Double and Triple DES

What ECB Leaks