Double DES and the Triple DES Keying Options

Build double DES and triple DES, stage by stage. Then find the key choices that reduce triple encryption back to single encryption.

Multiple encryptionKeying optionsdemo

Objectives

Construct double DES and EDE triple DES from single DES operations.
Identify which key equalities reduce triple DES to a single encryption.
Explain why the middle operation of EDE is a decryption.
Test whether two keys differing only in a parity bit are the same key to the cipher.
Distinguish two-key TDEA from double DES, given that both carry 112 key bits.

25%

Build double encryption and the encrypt, decrypt, encrypt construction, then run the cipher on every key-equality case and read the ciphertext each one returns.

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

DES has a 56-bit key. That key length was broken in public in 1998. The first repair anyone proposes is to encrypt each block twice, under two independent keys. The two keys hold 112 bits of key material.

Plaintext P (hex, 16 digits)

reads as 01 23 45 67 89 AB CD EF

First key K1 (hex, 16 digits)

reads as 13 34 57 79 9B BC DF F1

Second key K2 (hex, 16 digits)

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

Double encryption, one block

This table lists the plaintext, the two keys, the middle value the first encryption produced, and the ciphertext the second encryption produced.
Value	Hex
Plaintext P	01 23 45 67 89 AB CD EF
First key K1	13 34 57 79 9B BC DF F1
Middle value E(K1, P)	85 E8 13 54 0F 0A B4 05
Second key K2	0E 32 92 32 EA 6D 0D 73
Ciphertext E(K2, E(K1, P))	B4 A4 6F BF 03 42 08 5D

The middle value never leaves the encryptor and nobody transmits it. It still exists, and every attack on this construction is built on that one fact. Those attacks are priced on pages of their own.

Multiple encryption is worth building only because DES is not a group. Campbell and Wiener proved that at CRYPTO 1992. Suppose instead that every pair K1 and K2 had a single key K12 with E(K12, P) = E(K2, E(K1, P)) for every block P. Two encryptions would then be one encryption under some other key, and every construction on this page would reduce to single DES.

Every number on this page is computed in your browser by a teaching implementation of DES. It is written to be read. It is not constant time, and it is not production code.

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

Triple DES applies three DES operations in encrypt, decrypt, encrypt order. The middle operation is a decryption, and that is not a security decision. Set all three keys equal and the middle decryption removes the first encryption. The construction then reproduces single DES exactly, so one device performs both jobs.

Third key K3 (hex, 16 digits)

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

The three stages, on your own values

keys in the order the construction applies them

133457799BBCDFF10E329232EA6D0D731F1F1F1F0E0E0EFE

stage by stage

This table lists the plaintext, the value after each of the three stages of the construction, and the block that triple decryption returned.
Stage	Hex
Plaintext P	01 23 45 67 89 AB CD EF
A = E(K1, P)	85 E8 13 54 0F 0A B4 05
B = D(K2, A)	37 1F 99 5C A2 67 FB 42
C = E(K3, B)	1F BA 8F 22 4F 80 1A E3
D(K1, E(K2, D(K3, C)))	01 23 45 67 89 AB CD EF

The block was recovered

Decryption applies the inverse of each stage in the opposite order, which is the last row of the table. A construction that mixes an encryption with a decryption is still invertible, because each stage has an inverse and the order is reversed.

Every key-equality case, with the ciphertext it gives

Your three keys differ in the bits the cipher reads

Each row gives one case of equality among the three keys, the keying option that case corresponds to, the ciphertext the construction produced, and the single encryption that ciphertext is equal to.
Case	Keying option	C = E(K3, D(K2, E(K1, P)))	Equal to a single encryption
k1 = k2 = k3	keying option 3	85 E8 13 54 0F 0A B4 05	equals E(K1, P)
k1 = k2	misuse, not an option	60 7E AE 1B 67 36 B6 EF	equals E(K3, P)
k2 = k3	misuse, not an option	85 E8 13 54 0F 0A B4 05	equals E(K1, P)
k1 = k3, k2 differs	keying option 2	05 51 52 35 0C D7 A4 BB	no single encryption matches
all three differ	keying option 1	1F BA 8F 22 4F 80 1A E3	no single encryption matches

Three of the five cases return exactly the ciphertext of one single encryption. The last column is decided by running that single encryption and comparing the two 64-bit values, not by algebra on paper. The marked rows are the three that reduce.

Keying option 1 uses three different keys. Keying option 2 sets K1 = K3 and keeps K2 different, which is the two-key construction and holds 112 bits. Keying option 3 sets all three keys equal, which is single DES exactly, and it exists so that one device can also interoperate with equipment holding a single DES key.

Two of the three reducing cases are not keying options at all. K1 = K2 gives a single encryption under K3, and K2 = K3 gives a single encryption under K1. Each is what a key bundle produces when two of its three parts hold the same value. A construction that claims 168 bits of key material then encrypts with 56.

One equality is invisible in the key bytes. PC-1 keeps 56 of the 64 key bits and discards the other 8, which are the parity bits. Two keys that differ only in those 8 positions produce the same 16 subkeys, so they are one key to the cipher.

parity bit position to flip in K1, counted from the most significant bit

Two key values, one key to the cipher

This table lists the first key, the same key with one parity bit flipped, the positions at which the two differ, and the ciphertext each of them produces for the plaintext.
Value	Hex
K1	13 34 57 79 9B BC DF F1
K1 with bit 8 flipped	12 34 57 79 9B BC DF F1
Positions where they differ	8
E(K1, P)	85 E8 13 54 0F 0A B4 05
E(the flipped key, P)	85 E8 13 54 0F 0A B4 05

the sixteen subkeys under each of the two key values

round   subkey under K1   under the flipped key   same
K(1)    1B02EFFC7072      1B02EFFC7072            yes
K(2)    79AED9DBC9E5      79AED9DBC9E5            yes
K(3)    55FC8A42CF99      55FC8A42CF99            yes
K(4)    72ADD6DB351D      72ADD6DB351D            yes
K(5)    7CEC07EB53A8      7CEC07EB53A8            yes
K(6)    63A53E507B2F      63A53E507B2F            yes
K(7)    EC84B7F618BC      EC84B7F618BC            yes
K(8)    F78A3AC13BFB      F78A3AC13BFB            yes
K(9)    E0DBEBEDE781      E0DBEBEDE781            yes
K(10)   B1F347BA464F      B1F347BA464F            yes
K(11)   215FD3DED386      215FD3DED386            yes
K(12)   7571F59467E9      7571F59467E9            yes
K(13)   97C5D1FABA41      97C5D1FABA41            yes
K(14)   5F43B7F2E73A      5F43B7F2E73A            yes
K(15)   BF918D3D3F0A      BF918D3D3F0A            yes
K(16)   CB3D8B0E17F5      CB3D8B0E17F5            yes

The two key values are different integers

All 16 subkeys are identical

Both keys give the same ciphertext

The flipped bit is one of the eight positions PC-1 never names, so it reaches no subkey. The key register is built from the other 56 bits, and those are unchanged.

What that does to a key bundle

Now build a bundle from three key values: K1, the flipped key above, and K3. A check that compares the 24 bytes in three groups of eight reports three different keys, so the bundle looks like keying option 1. Run the construction on it.

This table lists the ciphertext the construction produced from the bundle and the ciphertext a single encryption under the third key produces for the same plaintext.
Value	Hex
Third key K3	1F 1F 1F 1F 0E 0E 0E FE
The bundle, run as EDE	60 7E AE 1B 67 36 B6 EF
Single DES, E(K3, P)	60 7E AE 1B 67 36 B6 EF

The bundle is equal to E(K3, P)

Equal once the parity of every byte is recomputed

The bundle is the k1 = k2 case of the table in the previous step, hidden by the parity bits. The check that works recomputes the parity of every byte first and compares the results, which is the second mark above. Comparing the 56 bits PC-1 keeps gives the same answer.

This is the case an implementer misses. A three-key bundle arrives as 24 bytes. The cipher reads 56 bits of each key and never reads the other 8. A distinctness check written on all 64 bits of a key therefore accepts a bundle that reduces to a single encryption. Write the check on the bits the cipher uses, not on the bytes the bundle was delivered in.

Two constructions on this page hold the same 112 bits of key material. They are not the same function.

two-key TDEA: C = E(K1, D(K2, E(K1, P)))
double DES: C = E(K2, E(K1, P))

Two-key TDEA applies K1 at both ends and K2 in the middle, and the middle operation is a decryption. Double DES applies each key once, and both operations are encryptions. Two keys of 56 bits each hold 112 bits in both cases.

Same key material, different function

This table compares two-key triple encryption with double encryption on the same plaintext and the same two keys, giving the ciphertext, the key material and the number of DES operations each one performs.
Property	Two-key TDEA	Double DES
Ciphertext of P	05 51 52 35 0C D7 A4 BB	B4 A4 6F BF 03 42 08 5D
Keys	K1, K2, K1	K1, K2
Key material	112 bits	112 bits
DES operations per block	3	2

The two constructions differ on this block

One block on which the two results differ is enough to prove that the two constructions are different functions. The button repeats the comparison on a sample of 64 blocks drawn by a generator inside the library, and it stops at the first block that separates the two. Nothing is computed until you press it.

Key material is a property of the construction, and it is not the strength of the construction. Two schemes can hold the same 112 bits, compute different functions, and cost an attacker different amounts of work. What each one is worth is measured on its own page.

Each construction here has a published attack. Diffie and Hellman gave the meet-in-the-middle attack on double encryption in 1977. Merkle and Hellman gave a chosen-plaintext attack on two-key triple encryption in 1981. The known-plaintext form of that attack is due to van Oorschot and Wiener, EUROCRYPT 1990. Every cost is on the pages that price these attacks.

NIST SP 800-67 Rev. 2 is the specification of the keying options. SP 800-131A Rev. 2 disallowed TDEA for encryption after 2023. Neither DES nor TDEA is approved for new work. The constructions are still worth reading, because the same key-equality mistakes appear in any scheme built by composing a cipher with itself.

step 1/4

CPE 645 / CS 685

Double DES and the Triple DES Keying Options

Weak Keys and the Complementation Property

Meeting in the Middle on Double and Triple DES