Inside a DES S-Box

Send six bits into any of the eight S-boxes. See which bits choose the row and the column, how many inputs share one output, and where those four bits go next.

S-boxesDiffusiondemo

Objectives

Apply the outer and inner bit rule to address one entry of an S-box.
Compute the four-bit output for a six-bit input by hand and check it against the page.
Test whether every row of a box is a permutation of the values 0 to 15.
Count the preimages of a chosen four-bit output and check that the count is four.
Trace which S-boxes in the next round one box's output reaches.

20%

Address one entry by hand, count the inputs behind each output, measure how far the box sits from linear, then follow the four output bits into the next round.

A DES S-box is a table of four rows and sixteen columns. It takes six bits and returns four. The six bits do not address the table in the obvious way: the two outer bits select the row, and the four inner bits select the column.

which of the eight boxes

the six input bits

bit 1

row

bit 2

column

bit 3

column

bit 4

column

bit 5

column

bit 6

row

In round 1 of the sample block this box receives 011000, one of the eight six-bit chunks the expansion and the subkey XOR produce.

How the six bits address the table

position   1  2  3  4  5  6
value      0  1  1  0  1  1
selects    R  C  C  C  C  R

R = row      bits 1 and 6 = 01   =  1
C = column   bits 2 to 5  = 1101 = 13

Bit 1 and bit 6 are read as a two-bit number, which gives a row between 0 and 3. Bits 2, 3, 4 and 5 are read as a four-bit number, which gives a column between 0 and 15. The outer pair is split across the two ends of the input, so the row index is never a contiguous field.

the entry those two indices name

S1[row 1][column 13] = 5 = 0101

S1, four rows of sixteen

The sixty-four entries of this S-box, arranged as four rows of sixteen, with the row and the column the six input bits select.
row	0	1	2	3	4	5	6	7	8	9	10	11	12	13 the selected column	14	15
0 = 00	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
1 = 01 the selected row	0	15	7	4	14	2	13	1	10	6	12	11	9	5 the addressed entry	3	8
2 = 10	4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
3 = 11	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

The selected row carries a rule down its left edge, the selected column header carries a rule under it, and the addressed entry is ringed and set in bold. Change any bit above and the marks move.

The common error is to read the top two bits as the row and the bottom four as the column. That gives a valid table entry, so nothing crashes and no test fails until the whole cipher produces the wrong block. Do one lookup by hand before you trust any code you write.

Six bits in and four bits out means sixty-four inputs share sixteen outputs. Two bits of information are lost in every box. The question a designer has to answer is whether they are lost evenly.

Every output of S1, and what reaches it

For each of the sixteen four-bit outputs of this S-box, the six-bit inputs that produce it and how many there are.
Output	Four bits	Inputs that produce it	Count
0	0000	000001 011100 111011 111110	4
1	0001	000110 001111 100010 101101	4
2	0010	001000 001011 100111 101100	4
3	0011	010000 011101 110101 111000	4
4	0100	000010 000111 100000 101001	4
5 the addressed output	0101	011000 011011 110001 111100	4
6	0110	010011 010100 101010 111101	4
7	0111	000101 011110 101111 110110	4
8	1000	001110 011111 100101 100110	4
9	1001	011001 011010 101011 110100	4
10	1010	010001 010010 111001 111010	4
11	1011	001100 010111 101110 110011	4
12	1100	010101 010110 100011 110010	4
13	1101	000100 001101 101000 111111	4
14	1110	000000 001001 100100 110111	4
15	1111	000011 001010 100001 110000	4

Each of the four rows holds 0 to 15 once

Every output of all eight boxes has exactly four preimages

Each row is a permutation of the values 0 to 15, and there are four rows, so every output value is produced by exactly four of the sixty-four inputs. Every bar above is the same length. The two lost bits are lost evenly, and no output value is easier to reach than any other.

An uneven box would leak. If one output value had eight preimages and another had none, an attacker who saw that value would already know something about the input to the round. Uniform preimage counts remove that.

The box is not reversible, and it is not supposed to be. Four inputs share every output, so no inverse table exists. DES places the box inside the round function of a Feistel network, which never inverts that function. It computes the same function a second time and XORs the same value again.

Even preimage counts are not enough on their own. A box could share its outputs evenly and still be a linear map over GF(2). That would be fatal. E, P, IP and the subkey XOR are all linear, so a linear box would leave the whole cipher as one system of linear equations in the key bits. An attacker would then solve for the key instead of searching for it.

The test is a sweep. Take one of the four output bits, take one of the 64 masks on the six input bits, and count how many of the 64 inputs make the parity of the masked input equal that output bit. An output bit that is affine in those input bits agrees 64 times or 0 times. An output bit with no linear structure agrees 32 times, which is chance. The count below is the largest any output bit and any mask reach, so it is the best affine approximation the box allows.

The sweep is 131,072 evaluations. It runs from the button and never while the page is drawing.

That distance from chance is what linear cryptanalysis uses. Matsui chained the per-box approximations into one approximation of the whole cipher, and the biases multiply, so the product shrinks quickly as rounds are added. Against sixteen rounds the attack still needs about 2^43 known plaintexts, which is more data than any real deployment encrypts under one key. A box that agreed 64 times out of 64 would cost nothing to approximate, and the key would follow from linear algebra. Matsui, Linear cryptanalysis method for DES cipher, EUROCRYPT 1993, and the experimental break, CRYPTO 1994.

One box on its own is now settled. The next question is what it feeds. A box writes four bits into the 32-bit S output, box b writing positions 4b+1 to 4b+4. The permutation P moves those four bits to four other positions of the half block, and the expansion of the round after it reads each position again.

P sends the four bits to four positions, which is at most four S-boxes. E is what makes the number six. E names sixteen of the thirty-two positions twice, once at the end of one six-bit group and once at the start of the next, and exactly two of the four positions of any box are among them. Two positions reach two boxes each, two reach one box each, and the six are always distinct.

the four bits of the selected box, one at a time

S output bit    after P   twice?    arrives at
1                     9   yes       S2  S3
2                    17   yes       S4  S5
3                    23   no        S6
4                    31   no        S8

four bits, 2 of them named twice by E
6 S-boxes reached: S2  S3  S4  S5  S6  S8

Which S-boxes each box feeds in the next round

For each of the eight S-boxes, the four positions of the half block that P sends its output bits to, how many of those positions the expansion names twice, and the S-boxes of the next round that read them.
Box	Positions after P	Named twice by E	S-boxes reached	Count
S1	9 17 23 31	2	S2 S3 S4 S5 S6 S8	6
S2	13 28 2 18	2	S1 S3 S4 S5 S7 S8	6
S3	24 16 30 6	2	S2 S4 S5 S6 S7 S8	6
S4	26 20 10 1	2	S1 S3 S5 S6 S7 S8	6
S5	8 14 25 3	2	S1 S2 S3 S4 S6 S7	6
S6	4 29 11 19	2	S1 S2 S3 S5 S7 S8	6
S7	32 12 22 7	2	S1 S2 S3 S4 S6 S8	6
S8	5 27 15 21	2	S1 S2 S4 S5 S6 S7	6

Every box reaches exactly six of the eight

No box reaches itself in the next round

Six is the same number for all eight boxes, and the page measures it rather than asserting it. The count is a property of P and E together, not of either one. Remove P and box 1 would keep its own four positions of the half block, which the expansion carries to 3 S-boxes: the box itself and its two neighbours. P is what raises 3 to 6.

This is one reason DES needs sixteen rounds. One round carries a difference in one S-box to six S-boxes, the round after it carries each of those to six again, and a few rounds later every bit of the block depends on every bit of the input. The avalanche page measures that growth on real blocks.

Two questions remain. Who chose these sixty-four numbers in each box, and who chose the wiring of P? The tables and the permutation are the two parts of DES that had to be designed rather than derived, and both arrived with no reason attached.

The design criteria for the S-boxes were classified when DES was published in 1977. The tables arrived as numbers with no stated reason, and many people assumed a hidden weakness. Don Coppersmith published the criteria in 1994. The IBM team had known differential cryptanalysis since 1974 and chose the boxes to resist it. Biham and Shamir rediscovered that attack and published it in 1990. Given its structure and its sixteen rounds, DES was close to the strongest design possible against that attack. The tables were strong. The secrecy still cost the design seventeen years of public doubt. Publish the reasoning with the numbers.

The published criteria cover the wiring as well as the tables. The six-box spread of the previous step is one of the stated properties of P, which is why it is the same number for all eight boxes rather than an average.

Coppersmith, The Data Encryption Standard (DES) and its strength against attacks, IBM Journal of Research and Development 38(3), 1994. Biham and Shamir, Differential cryptanalysis of DES-like cryptosystems, CRYPTO 1990.

step 1/5

CPE 645 / CS 685

Inside a DES S-Box

The DES Key Schedule

Encrypting and Decrypting a Block