Inside a DES Round: Expansion, the S-boxes and the Permutation

Each S-box is a table of 4 rows and 16 columns holding numbers from 0 to 15. It takes six bits and gives four.

• The outer two bits, that is the first and the sixth, give the row, read as a two-bit number from 0 to 3.
• The middle four bits, that is bits two to five, give the column, read as a four-bit number from 0 to 15.
• The entry at that row and column is the output, written as four bits.

The trick is that the row comes from the first and last bits and not from the first two. Getting that wrong is the commonest error in the whole of DES, and the run below prints the two parts separately for every box so that the reader can see which bits went where.

The round function, computed on the standard values

# The DES round function F, from Tables 3, 4 and 5 of FIPS 46-3: the expansion
# permutation E, the eight S-boxes, and the permutation P.

E = [32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9, 10, 11, 12, 13,
     12, 13, 14, 15, 16, 17, 16, 17, 18, 19, 20, 21, 20, 21,
     22, 23, 24, 25, 24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32, 1]

P = [16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,
     2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25]

S = [
 [[14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7],
  [0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8],
  [4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0],
  [15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13]],
 [[15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10],
  [3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5],
  [0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15],
  [13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9]],
 [[10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8],
  [13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1],
  [13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7],
  [1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12]],
 [[7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15],
  [13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9],
  [10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4],
  [3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14]],
 [[2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9],
  [14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6],
  [4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14],
  [11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3]],
 [[12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11],
  [10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8],
  [9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6],
  [4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13]],
 [[4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1],
  [13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6],
  [1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2],
  [6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12]],
 [[13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7],
  [1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2],
  [7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8],
  [2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11]],
]

def hex_bits(hexstr):
    n = len(hexstr) * 4
    v = int(hexstr, 16)
    return [(v >> (n - 1 - i)) & 1 for i in range(n)]

def bin_bits(binstr):
    return [int(c) for c in binstr]

def to_hex(bl):
    v = 0
    for b in bl:
        v = (v << 1) | b
    return "%0*X" % (len(bl) // 4, v)

def permute(bl, table):
    return [bl[i - 1] for i in table]

# R0 and K1 from the standard walk-through of key 133457799BBCDFF1
R = hex_bits("F0AAF0AA")
K = bin_bits("000110110000001011101111111111000111000001110010")

print("R (32 bits)       :", to_hex(R))
print("subkey K (48 bits):", to_hex(K))
print()

expanded = permute(R, E)
print("after the expansion permutation E, 32 bits become 48:")
print("   E(R)           :", to_hex(expanded))
x = [a ^ b for a, b in zip(expanded, K)]
print("   E(R) XOR K     :", to_hex(x))
print()

print("the 48 bits in eight groups of six, one per S-box:")
print("   " + " ".join("".join(str(b) for b in x[i * 6:i * 6 + 6]) for i in range(8)))
print()

out = []
print("each group of six gives four bits:")
for i in range(8):
    g = x[i * 6:i * 6 + 6]
    row = g[0] * 2 + g[5]
    col = g[1] * 8 + g[2] * 4 + g[3] * 2 + g[4]
    v = S[i][row][col]
    out += [(v >> 3) & 1, (v >> 2) & 1, (v >> 1) & 1, v & 1]
    print("   S%d: bits %s  outer %d%d = row %d, inner %s = column %2d, entry %2d = %s"
          % (i + 1, "".join(str(b) for b in g), g[0], g[5], row,
             "".join(str(b) for b in g[1:5]), col, v,
             "".join(str(b) for b in [(v >> 3) & 1, (v >> 2) & 1, (v >> 1) & 1, v & 1])))
print()
print("the eight S-box outputs, joined:", to_hex(out))
print("after the permutation P        :", to_hex(permute(out, P)))
print()
print("every S-box takes 6 bits to 4, so it is not invertible:")
first = S[0]
print("   S1 row 0 column 0 gives", first[0][0], "and row 1 column 1 gives", first[1][1])
print("   48 bits in, 32 bits out: F throws away one third of what it is given.")

Read five things out of the run.

E(R) is 7A15557A1555, and its 48 bits repeat in a pattern. Look at the eight groups of six: 011110 100001 010101 010101 011110 100001 010101 010101. The first four groups and the last four are identical, because R itself was F0AAF0AA, which is two identical halves. That is not a property of E; it is a property of this particular R, and it is worth noticing so that a reader does not mistake it for one.

The exclusive-or with the subkey gives 6117BA866527. From here on the values depend on the key, and this is the only place the key touches the round.

Every S-box lookup is shown with its row and column. Take S1: the six bits are 011000, the outer bits are 0 and 0 so the row is 0, the inner four bits are 1100 so the column is 12, the entry is 5, and 5 as four bits is 0101. Follow that for all eight and you can do it in an examination.

The eight outputs joined give 5C82B597, and P turns that into 234AA9BB. This is the value the previous chapter used to compute R1, and it is the value every published walk-through of DES gives for round 1 of this plaintext and key. That agreement is the check on this entire chapter.

Each S-box takes six bits to four, so it throws two away. F as a whole takes 48 bits to 32. The round function is therefore not invertible, which is exactly what the Feistel chapter said it did not need to be.

The expansion permutation, and why its rows overlap

The E table is usually printed as eight rows of six. Read it and you see that the last two entries of each row are the first two entries of the next, and that the table wraps: it begins with 32 and ends with 1.

That overlap is the point. Bit 1 of R appears in group 1 and in group 8. Bit 4 appears in group 1 and group 2. So sixteen of the 32 bits go into two S-boxes each, and a change in any one of those bits affects two S-boxes in this round, and therefore many more in the next. That is diffusion produced by duplication, and it costs nothing in hardware.

A worked example: one S-box by hand

Read S5 with the input bits 100001.

Step 1: the row. The outer bits are the first, 1, and the sixth, 1. As a two-bit number that is binary 11, which is 3. Row 3.

Step 2: the column. The middle four bits are 0, 0, 0, 0. As a four-bit number that is 0. Column 0.

Step 3: the entry. S5 row 3 column 0. Counting rows from 0, row 3 of S5 is 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3, and column 0 of that row is 11.

Step 4: as four bits. 11 in binary is 1011.

So 100001 goes to 1011, which is exactly what the run printed for S5. Notice how easy it would have been to take the row from the first two bits, 10, giving row 2 and the answer 0 instead of 11.

Distinctions that carry marks

What beginners get wrong here

Taking the S-box row from the first two bits. It is the first and the last. This one error invalidates a whole answer.

Forgetting that the S-boxes are the only non-linear part. If a question asks why the S-boxes matter, that is the answer, and "they provide confusion" is the second half of it.

Thinking E is a plain permutation. It duplicates sixteen bits, so it is an expansion; the same input bit appears twice in the output.

Confusing P with IP. P is 32 bits, inside F, and contributes diffusion. IP is 64 bits, outside the rounds, and contributes nothing.

Expecting F to be invertible. It takes 48 bits to 32 and discards information. The Feistel structure is what makes that acceptable.

Quick revision

• F has four steps: expansion E (32 to 48), exclusive-or with the 48-bit subkey, eight S-boxes (48 to 32), permutation P (32 to 32).
• E duplicates sixteen bits so that one input bit feeds two S-boxes; that is diffusion, and it is why its rows overlap.
• An S-box takes 6 bits to 4. Row from the first and sixth bits; column from the middle four.
• The S-boxes are the only non-linear part of DES. Without them the cipher is linear and solvable as a system of equations.
• P spreads each S-box's four output bits to four different S-boxes in the next round.
• On the standard block and key: E(R0) is 7A15557A1555, exclusive-ored with K1 it is 6117BA866527, the S-box outputs join to 5C82B597, and after P the round function gives 234AA9BB.
• The S-box design criteria were classified in 1977; when differential cryptanalysis was published in 1990 the boxes proved unusually resistant to it.
• F takes 48 bits to 32, so it is not invertible, which the Feistel structure does not require.

Test yourself

1. Describe the four steps of the DES round function, with the bit counts. The 32-bit input is expanded to 48 bits by the expansion permutation E, which duplicates sixteen bits. The 48 bits are exclusive-ored with the 48-bit subkey. The result is split into eight groups of six, and each group is replaced by four bits through its own S-box, giving 32 bits. Those 32 bits are rearranged by the permutation P.

2. How is an S-box addressed? The first and sixth bits of the six-bit group, taken as a two-bit number, give the row from 0 to 3. The middle four bits, taken as a four-bit number, give the column from 0 to 15. The table entry at that row and column, written as four bits, is the output.

3. Read S5 with the input 100001. The outer bits are 1 and 1, so the row is binary 11, which is 3. The middle bits are 0000, so the column is 0. S5 row 3 column 0 holds 11, which as four bits is 1011.

4. Why is the expansion permutation an expansion rather than a permutation? Because it produces 48 bits from 32 by using sixteen of the input bits twice. Its purpose is both to match the 48-bit subkey and to make one input bit influence two S-boxes, which spreads the effect of a change more quickly through the rounds.

5. Why are the S-boxes the most important part of DES? Because they are the only non-linear component. Every other operation in the cipher, the permutations and the exclusive-ors, is linear, and a cipher built only from linear operations can be expressed and solved as a system of linear equations. The S-boxes supply the confusion that prevents this.

6. What does the permutation P contribute, and what would happen without it? It spreads the four output bits of each S-box across four different S-boxes in the following round, so that the influence of every input bit reaches the whole block within a few rounds. Without it the diffusion would remain local to each six-bit group, and an attacker could attack each S-box almost independently.

7. Why is the round function not invertible, and why does that not matter? Because each S-box maps six bits to four, so F maps 48 bits to 32 and discards information. It does not matter because a Feistel structure only ever evaluates F in the forward direction: going backwards, the right half of the previous round is available immediately, F is recomputed on it, and the result is exclusive-ored out.