Block ciphers, S-boxes, P-boxes and Feistel

How a block cipher builds confusion and diffusion out of S-boxes and P-boxes, worked step by step on DES's own S[0] example, and the Feistel structure that chains them into a cipher reversible for decryption.

Explain why an S-box, or the arrangement it sits in, has to be invertible.
Compute an S-box lookup from a 6-bit input by hand, row and column.
Trace one Feistel round: the split, the round function, the XOR and the swap.
Name which ciphers are built on the Feistel structure and which are not.

14 min read

Intuition

A classical substitution cipher swaps one symbol for another using a single fixed rule, which is exactly why frequency analysis breaks it — the statistical shape of the plaintext survives into the ciphertext unchanged. A modern block cipher fixes this by working on a whole fixed-size chunk of bits at once, running it through many rounds of substitution and permutation, so that the relationship between key and ciphertext becomes hard to follow and a single flipped input bit spreads across the whole output. Two components do that work: S-boxes for substitution, P-boxes for permutation. How they are arranged into rounds is what separates one block cipher design from another.

Mechanism

A block cipher takes a fixed-size block of plaintext, typically 64 or 128 bits, processes it with the secret key, and outputs a block of ciphertext the same size. If the plaintext is smaller than the block size, padding fills the gap. Inside the cipher, substitution is implemented by S-boxes and permutation by P-boxes, chained across many rounds to build up confusion and diffusion.

An S-box is a lookup table: it maps a block of input bits to a block of output bits, using a mapping chosen and vetted in advance, not computed on the fly. A well-designed S-box has an avalanche property — changing one input bit flips, on average, half of the output bits — which is where an S-box’s contribution to diffusion comes from.

Decryption has to run the cipher backward, which means every S-box lookup has to be reversible somehow. There are two ways to get that:

The S-box itself is invertible — every output has exactly one input that could have produced it, so the table can be read in reverse directly.
The arrangement around the S-box is invertible, even when the S-box on its own is not. This is what DES uses: each of its eight S-boxes maps a 6-bit input to a 4-bit output, so several different 6-bit inputs can share one 4-bit output — the box itself has no unique inverse. Decryption still works because DES’s Feistel structure, not the S-box, is what gets reversed.

Worked example

AnswerInput 110111 -> row 3, column 11 -> output 1110

DES’s own S[0] is used like this: the input is a 6-bit string $(b_0, b_1, b_2, b_3, b_4, b_5)$ . The two outer bits, $b_0$ and $b_5$ , give the row. The four inner bits, $b_1 b_2 b_3 b_4$ , give the column. The lecture works through input $110111$ :

Split the input into its six bits: $b_0=1,\ b_1=1,\ b_2=0,\ b_3=1,\ b_4=1,\ b_5=1$ .
Row from the outer bits $b_0 b_5 = 11$ : $(11)_2 = (3)_{10}$ .
Column from the inner bits $b_1 b_2 b_3 b_4 = 1011$ : $(1011)_2 = (11)_{10}$ .
Look up row 3, column 11 in the S[0] table. The entry is $14$ .
Write $14$ back out in binary, since that is the S-box’s actual output: $(14)_{10} = (1110)_2$ .

DES has eight S-boxes built the same way; S[0] is only the first of them.

Formula

DES S-box addressing

\text{row} = 2b_0 + b_5, \qquad \text{col} = 8b_1 + 4b_2 + 2b_3 + b_4

$b_0, b_5$: the outer two bits — row, 0 to 3
$b_1 b_2 b_3 b_4$: the inner four bits — column, 0 to 15

Read the row bits and column bits as ordinary binary numbers, exactly as in the worked example above.

Mechanism

A P-box carries out the permutation half of the pair: a simple re-ordering of bit positions, with no substitution involved. P-boxes are usually chained with S-boxes — the output of one layer of S-boxes passes through a P-box before feeding the next layer of S-boxes — and the P-box’s job is to distribute the bits of one S-box’s output across as many of the following S-boxes as possible. That spread is what turns a local avalanche inside one S-box into diffusion across the whole block.

Repeating S-box and P-box layers over multiple rounds is what makes a modern block cipher hard to break even when no single round is especially strong on its own: more rounds mean more opportunities for one changed input bit to keep propagating outward. How those rounds are wired together is called a network. The Feistel structure is one such network, used in DES, Blowfish, Twofish and RC6.

A Feistel round works on a block $X$ split into two equal halves, $X = L_n \parallel R_n$ . Only the right half goes through a keyed round function $F$ ; the left half does not. The output of $F$ is XORed with the left half to produce the new right half, and — this is the step that gives the structure its name — the old right half passes straight through, unchanged, to become the new left half: $L_{n+1} = R_n, \qquad R_{n+1} = L_n \oplus F(R_n, K_n).$ $F$ itself does not have to be invertible for any of this to work. The split-then-swap shape of the round is reversible on its own: running the identical network with the round keys applied in reverse order undoes encryption, regardless of what $F$ computes internally. Inside DES, $F$ is built from an expansion, a round-key XOR, eight S-boxes and a P-box — this is where the machinery worked above actually sits.

A block splits into equal left and right halves. Only the right half goes through the round function F, keyed by the round subkey Kₙ; DES builds F out of an expansion, a round-key XOR, eight S-boxes and a P-box. The F output is XORed with the left half to make the new right half, and the old right half passes straight through to become the new left half — the "swap" that gives the structure its diagonal, crossing shape. Because the structure is reversible regardless of whether F itself is invertible, the same network runs backward for decryption by applying the round keys in reverse order.

Exam detail

Two invertibility claims get confused easily and are worth keeping separate. First, an individual S-box may or may not be invertible on its own — DES’s are not, since 6 input bits collapse to 4 output bits. Second, whether or not the S-box is invertible, the network it sits inside can still be reversible as a whole. DES relies on the second property, not the first.

Feistel ciphers are not the only way to arrange S-boxes and P-boxes. AES uses a different network, a substitution-permutation network (SPN), where every round transforms the whole block rather than splitting it and touching only half. The diagram below shows the generic SPN shape and how AES’s own four named round operations — SubBytes, ShiftRows, MixColumns, AddRoundKey — map onto it; the next topic covers AES in full.

Generic SPN → AES mapping

A substitution-permutation network alternates two layers over many rounds: S-boxes for confusion (each substitution scrambles the relationship between key and ciphertext) and P-boxes for diffusion (each permutation spreads one input bit's influence across many output bits). AES is an SPN, not a Feistel cipher — every round runs all four stages on the whole block: SubBytes is the S-box layer, ShiftRows and MixColumns together are the P-box / diffusion layer, and AddRoundKey mixes in that round's subkey. AES repeats this 10, 12 or 14 times depending on whether the key is 128, 192 or 256 bits.

Pitfall

Do not describe AES as “Feistel with extra steps.” A Feistel round only ever runs its keyed function on half the block and leaves the other half untouched until the swap; an SPN round runs every operation over the entire block, every round. The two are genuinely different networks, and the lecture’s own practice quiz tests this distinction directly.

Recall

Why does DES not need its individual S-boxes to be invertible?

Because decryption reverses the Feistel structure that the S-boxes sit inside, not the S-boxes themselves. A DES S-box maps 6 bits to 4, so it has no unique inverse on its own — but running the same split-XOR-swap network with the round keys in reverse order still recovers the plaintext, whatever $F$ computed along the way.

Source

Week 4 notes PDF