One Round of DES

Step through one DES round. Open the round function into its four stages, and change the subkey to see each stage move.

Block ciphersRound functiondemo

Objectives

Trace one 32-bit half through expansion, key addition, substitution and permutation.
Identify the width of the value entering and leaving each stage of the round function.
Explain why the round function does not need to be reversible.
Predict which halves change when a round runs on the sample block.
Distinguish the work the round function does from the swap the round performs.

25%

Two halves, one 48-bit subkey, and the four stages inside the round function.

A DES block is 64 bits. The initial permutation reorders those 64 bits and the result is split into two halves of 32 bits. A round reads the two halves and one 48-bit subkey, and returns two new halves.

L(i) = R(i-1)
R(i) = L(i-1) XOR F(R(i-1), K(i))

Block (hex, 64 bits)

reads as 01 23 45 67 89 AB CD EF

Key (hex, 64 bits)

reads as 13 34 57 79 9B BC DF F1

The block, before any round has run

This table lists the block as typed, the same block after the initial permutation, and the two halves the first round starts from.
Value	Width	Hex	Binary
Block	64 bits	0123456789ABCDEF	00000001 00100011 01000101 01100111 10001001 10101011 11001101 11101111
After IP	64 bits	CC00CCFFF0AAF0AA	11001100 00000000 11001100 11111111 11110000 10101010 11110000 10101010
L(0)	32 bits	CC00CCFF	11001100 00000000 11001100 11111111
R(0)	32 bits	F0AAF0AA	11110000 10101010 11110000 10101010

IP moves bits and adds no security at all. It is a wiring convention from the hardware of the 1970s, and the final permutation reverses it. L(0) is the left half of the permuted block and R(0) is the right half.

Eight of the 64 key bits are parity bits. The first permuted choice discards them, so 56 bits reach the subkeys, and each round uses a different 48 of those 56.

Choose a round. The new left half is a copy of the old right half. The new right half is the old left half XORed with the 32 bits F returned. Nothing else happens in a round.

Round

Round 1 of 16

This table lists the two halves this round starts from, the subkey it uses, the value the round function returned, and the two halves it produced.
Value	Width	Hex	Binary
L(0)	32 bits	CC00CCFF	1100 1100 0000 0000 1100 1100 1111 1111
R(0)	32 bits	F0AAF0AA	1111 0000 1010 1010 1111 0000 1010 1010
K(1)	48 bits	1B02EFFC7072	000110 110000 001011 101111 111111 000111 000001 110010
F(R(0), K(1))	32 bits	234AA9BB	0010 0011 0100 1010 1010 1001 1011 1011
L(1)	32 bits	F0AAF0AA	1111 0000 1010 1010 1111 0000 1010 1010
R(1)	32 bits	EF4A6544	1110 1111 0100 1010 0110 0101 0100 0100

the round equation on these numbers

L(1) = R(0)                   F0AAF0AA = F0AAF0AA
R(1) = L(0) XOR F             CC00CCFF XOR 234AA9BB = EF4A6544

The first line is a copy, so both sides are the same 32 bits. The second line is one XOR of two 32-bit values. A reader with a pen can check either one from the table above.

K(1) is not part of the block. The second permuted choice selects those 48 bits from the 56-bit key register, and the register is rotated once before each round selects from it. The key schedule has a page of its own.

F is four stages. Expand the 32-bit half to 48 bits, XOR the 48-bit subkey, send eight six-bit groups through eight different S-boxes, which return 32 bits, then permute those 32 bits. Every width in that sentence is printed below.

The four stages, round 1

R(0)           32 bits   1111 0000 1010 1010 1111 0000 1010 1010
E expansion    48 bits   011110 100001 010101 010101 011110 100001 010101 010101
K(1)           48 bits   000110 110000 001011 101111 111111 000111 000001 110010
E XOR K        48 bits   011000 010001 011110 111010 100001 100110 010100 100111

S-box                    S1     S2     S3     S4     S5     S6     S7     S8    
four bits out            0101   1100   1000   0010   1011   0101   1001   0111  

S output       32 bits   0101 1100 1000 0010 1011 0101 1001 0111
P permutation  32 bits   0010 0011 0100 1010 1010 1001 1011 1011

The 48-bit lines are grouped in six because each group is the input of one S-box, and the column an S-box sits in is the column its input sits in. The 32-bit lines are grouped in four because each group is the output of one S-box. The last line is the value the round XORs into the left half, so it is the number the table in the previous step calls F.

The expansion is the stage that lets one bit of the half reach two S-boxes. 16 of the 32 input bits are named twice by the expansion table, and the other 16 are named once. That is where a difference in one bit starts to spread.

How each S-box was addressed

Each row gives one of the eight S-boxes, the six input bits it received, the row and the column those bits select, and the four output bits it returned.
S-box	Six bits in	Decimal	Row	Column	Four bits out	Decimal
S1	011000	24	0	12	0101	5
S2	010001	17	1	8	1100	12
S3	011110	30	0	15	1000	8
S4	111010	58	2	13	0010	2
S5	100001	33	3	0	1011	11
S6	100110	38	2	3	0101	5
S7	010100	20	0	10	1001	9
S8	100111	39	3	3	0111	7

The outer two bits of the six select the row, from 0 to 3. The inner four select the column, from 0 to 15. Reading one entry of the printed table for that box gives the four output bits, and the page with the boxes themselves lets you check any row of this table by hand.

Now ask whether F can be inverted. The expansion is not the problem, because it only repeats bits. The S-boxes are the problem. One box takes 64 different six-bit inputs and returns only 16 different four-bit outputs.

What the round function does to the count of values

This table gives the widths inside the round function and the number of six-bit inputs that share each four-bit S-box output.
Measurement	Value
Bits entering F	32
Bits after the expansion	48
Six-bit inputs to one S-box	64
Four-bit outputs of one S-box	16
Inputs sharing each output	4

The last row is measured over all eight boxes and every output of each. Every count is the same number, 4, so a box loses exactly two bits and loses them evenly. Every row of a DES S-box is a permutation of the values 0 to 15, and each box has four rows, which is what holds the count at one number.

Take the six bits S1 received this round: S1(011000) and S1(011011) both return 0101. Two different inputs give one output. No inverse of that box exists, so no inverse of F exists either.

Why that costs nothing

Encryption never inverts F, and neither does decryption. The value F returns is XORed into the left half, and the only thing needed to remove it is the same value again. Here is that XOR, run twice on the numbers of round 1.

the same 32 bits, XORed twice

L(0)                    CC00CCFF
F(R(0), K(1))           234AA9BB
R(1) = L(0) XOR F       EF4A6544
R(1) XOR F              CC00CCFF

L(0) recovered

The fourth line equals the first. Decryption reaches this round already knowing R(1) and R(0), so it computes F(R(0), K(1)) again and XORs the same 32 bits a second time. It never asks which input produced that value.

This is the freedom the Feistel structure gives a designer. F may lose information, so it can be built from whatever mixes best rather than from operations that can be inverted. DES uses that freedom in the S-boxes, which supply all of the non-linearity in the cipher. The properties F still owes are non-linearity and diffusion, not reversibility.

The code 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/4

CPE 645 / CS 685

One Round of DES

The Brute-Force Baseline

The DES Key Schedule