Encrypting and Decrypting a Block

Encrypt the sample block through sixteen rounds, then decrypt it. Then turn off the subkey reversal and watch decryption fail.

DecryptionRound tripdemo

Objectives

Trace a block through the initial permutation, sixteen rounds and the final permutation.
Order the subkeys as encryption and as decryption apply them.
Predict the output of the circuit when the subkeys run forwards instead of backwards.
Explain the role of the final swap of halves in making one circuit do both jobs.
Interpret one row of the trace as a single Feistel step rather than as a whole cipher.

25%

Run a block through sixteen rounds, then disable the subkey reversal and watch decryption fail.

DES encrypts one 64-bit block under one 64-bit key. Type any block and any key as sixteen hexadecimal digits. Every table on this page is recomputed from what you type.

Block (hex, 16 digits)

reads as 01 23 45 67 89 AB CD EF

Key (hex, 16 digits)

reads as 13 34 57 79 9B BC DF F1

The initial permutation

IP reorders the 64 bits of the block and does nothing else to them. The result is split into two 32-bit halves. The left half is called L0 and the right half is called R0.

the split, in bit groups of four

after IP         1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010
L0, left half    1100 1100 0000 0000 1100 1100 1111 1111
R0, right half                                           1111 0000 1010 1010 1111 0000 1010 1010

the same three values

The block as typed, the block after the initial permutation, and the two 32-bit halves the rounds start from.
Value	Hex	Bits
Block as typed	0123456789ABCDEF	0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
After IP	CC00CCFFF0AAF0AA	1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010
L0, left half	CC00CCFF	1100 1100 0000 0000 1100 1100 1111 1111
R0, right half	F0AAF0AA	1111 0000 1010 1010 1111 0000 1010 1010

IP carries no security. Its table is published, so anyone can undo it. It is usually explained as a convenience for the hardware DES was designed for. The strength is in the rounds below.

All 16 rounds

Both halves after every round, the subkey that round used, and whether both halves have passed through the round function by that point.
Round	L	R	Subkey	Both halves through F
0	CC00CCFF	F0AAF0AA		no
1	F0AAF0AA	EF4A6544	K1 = 1B02EFFC7072	no
2	EF4A6544	CC017709	K2 = 79AED9DBC9E5	yes
3	CC017709	A25C0BF4	K3 = 55FC8A42CF99	yes
4	A25C0BF4	77220045	K4 = 72ADD6DB351D	yes
5	77220045	8A4FA637	K5 = 7CEC07EB53A8	yes
6	8A4FA637	E967CD69	K6 = 63A53E507B2F	yes
7	E967CD69	064ABA10	K7 = EC84B7F618BC	yes
8	064ABA10	D5694B90	K8 = F78A3AC13BFB	yes
9	D5694B90	247CC67A	K9 = E0DBEBEDE781	yes
10	247CC67A	B7D5D7B2	K10 = B1F347BA464F	yes
11	B7D5D7B2	C5783C78	K11 = 215FD3DED386	yes
12	C5783C78	75BD1858	K12 = 7571F59467E9	yes
13	75BD1858	18C3155A	K13 = 97C5D1FABA41	yes
14	18C3155A	C28C960D	K14 = 5F43B7F2E73A	yes
15	C28C960D	43423234	K15 = BF918D3D3F0A	yes
16	43423234	0A4CD995	K16 = CB3D8B0E17F5	yes

Round 0 is the state just after IP, before any round has run. Each later row is one Feistel step. The new left half is the previous right half. The new right half is the previous left half XORed with F of the previous right half and this round's subkey.

R0 enters F in round 1, so after round 1 the right half carries F output while the left half is still a copy of R0. From round 2 on, every bit of the state has passed through F at least once. The rule down the left of the table marks those rounds. The last column says the same thing in words.

One row is one round of sixteen. Reading a single row as a whole cipher is the common mistake here. The subkey column is the reminder: each row used a different one.

After round 16 the two halves change places one last time. The final permutation FP is applied to the result. FP is the inverse of IP.

The last swap

after round 16   L16 = 43423234      R16 = 0A4CD995
into FP          R16 = 0A4CD995      L16 = 43423234

Nothing is computed on this line. The two numbers keep their values and change columns, so what FP receives is R16 followed by L16. That one swap is what lets a single circuit run in both directions.

The final permutation

The two halves after the last round, the swapped value FP receives, and the ciphertext FP produces.
Value	Hex	Bits
L16	43423234	0100 0011 0100 0010 0011 0010 0011 0100
R16	0A4CD995	0000 1010 0100 1100 1101 1001 1001 0101
Into FP, R16 then L16	0A4CD99543423234	0000 1010 0100 1100 1101 1001 1001 0101 0100 0011 0100 0010 0011 0010 0011 0100
Ciphertext, after FP	85E813540F0AB405	1000 0101 1110 1000 0001 0011 0101 0100 0000 1111 0000 1010 1011 0100 0000 0101

checks

Same value as encrypt() on these inputs

Same value as the published 85E813540F0AB405

The first chip compares the value built row by row above against the library function, so the table and the cipher agree. The second compares that value against the ciphertext printed in the worked example that circulates with FIPS 46, which is a source outside this site.

IP and FP are a pair of public, fixed permutations. Either one can be undone by anyone. They add nothing an attacker has to defeat. Every bit of the security is in the sixteen rounds and in the key schedule that feeds them.

Decryption is the same circuit. The ciphertext passes through IP, the same 16 rounds run, the halves change places, and FP is applied. One thing is different: the subkeys arrive in the opposite order, K16 first and K1 last.

Round trip

subkey order used to decrypt

K16K15K14K13K12K11K10K9K8K7K6K5K4K3K2K1

result

The ciphertext, the block decryption returned, and the block that was encrypted.
Value	Hex	Bits
Ciphertext	85E813540F0AB405	1000 0101 1110 1000 0001 0011 0101 0100 0000 1111 0000 1010 1011 0100 0000 0101
Returned by decryption	0123456789ABCDEF	0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Original block	0123456789ABCDEF	0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

Original block recovered

The round trip holds for this block, and it holds for every block: nothing in the argument depends on which block was encrypted. The one thing it does depend on is the order of the subkeys.

The reversal is the whole difference. Disable it and the circuit is unchanged: the same IP, the same 16 rounds, the same round function, the same swap, the same FP. Only the order the subkeys arrive in is different.

Reverse the subkeys during decryption

Decryption under the order you chose

subkey order used to decrypt

K16K15K14K13K12K11K10K9K8K7K6K5K4K3K2K1

result

The ciphertext, the block that was encrypted, and the block the circuit returned under the chosen subkey order.
Value	Hex	Bits
Ciphertext	85E813540F0AB405	1000 0101 1110 1000 0001 0011 0101 0100 0000 1111 0000 1010 1011 0100 0000 0101
Original block	0123456789ABCDEF	0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Returned by the circuit	0123456789ABCDEF	0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

Original block recovered

0 of 64 bits differ from the original

Round 1 of decryption applied K16, which is the subkey round 16 of encryption applied, so those two rounds cancelled. Every later pair cancelled the same way, as far as K1, and the original block was returned. Disable the switch above to see the same circuit fail.

Decryption never inverts F. It computes the same F a second time and XORs the same value a second time, so the two copies cancel. The circuit does not have to be reversed, and the round function does not have to be invertible. The only thing decryption changes is the order the subkeys arrive in. That is why one piece of hardware can perform both operations.

step 1/4

CPE 645 / CS 685

Encrypting and Decrypting a Block

Inside a DES S-Box

Avalanche in DES