Feistel, DES, Triple DES and AES

◈ 7 cards

Why the Feistel structure makes decryption free even when its round function is not invertible, and the block size, key size and round count of the three block ciphers the paper can name.

The Feistel structure — invertible by construction

Feistel's idea solves a real design problem: how do you build a cipher out of a complicated, thoroughly mixing function when you have no idea how to invert that function? The answer is to arrange the rounds so that the structure is invertible whether or not the function is.

Split a $2 w$ -bit block into a left and right half, $(L_{0}, R_{0})$ . Round $i$ computes

$L_{i} = R_{i - 1}, R_{i} = L_{i - 1} \oplus F (R_{i - 1}, K_{i})$

where $K_{i}$ is a subkey derived from the key. Look at what round $i$ preserves: $R_{i - 1}$ survives untouched as $L_{i}$ . So at decryption time you already have the argument $F$ was called with, and you can recompute $F (R_{i - 1}, K_{i})$ and XOR it back off $R_{i}$ to recover $L_{i - 1}$ . $F$ is never inverted; it is only ever evaluated forwards. That is why a one-way function — even a hash — can serve as a Feistel round function, and it is why decryption is the same algorithm run with the subkeys in reverse order.

Worked example — three rounds of a tiny Feistel network

Take an 8-bit block ( $w = 4$ ), the round function $F (R, K) = (R \cdot R + K) mod 16$ , and subkeys $K_{1} = 5$ , $K_{2} = 3$ , $K_{3} = 9$ . Start at $L_{0} = 1011$ (11), $R_{0} = 0110$ (6).

round 1:  L1 = R0                    = 0110 (6)
          F(6, 5) = (36 + 5) mod 16  = 9
          R1 = L0 XOR 9 = 11 XOR 9   = 0010 (2)

round 2:  L2 = R1                    = 0010 (2)
          F(2, 3) = (4 + 3) mod 16   = 7
          R2 = L1 XOR 7 = 6 XOR 7    = 0001 (1)

Complete round 3 the same way: $L_{3} = R_{2} = 0001$ , $F (1, 9) = 10$ , and $R_{3} = L_{2} \oplus 10 = 2 \oplus 10 = 1000$ . The block after three rounds is $(0001, 1000)$ .

Now undo round 3 with nothing but the round-3 subkey. We know $L_{3} = R_{2}$ , so $R_{2} = 0001$ immediately. And $R_{3} = L_{2} \oplus F (R_{2}, K_{3})$ , so $L_{2} = R_{3} \oplus F (1, 9) = 8 \oplus 10 = 0010$ — which is exactly the $L_{2}$ we started round 3 with. Note that this $F$ is genuinely not invertible: $F (1, 9) = 10$ and $F (7, 9) = (49 + 9) mod 16 = 10$ as well, so knowing an output does not determine its input. The round inverted anyway. That is the whole point of the structure.

DES

DES is the standard — FIPS 46, published 1977 by the National Bureau of Standards. The algorithm it specifies is called DEA, and the standard-versus-algorithm split is a classic exam trap. Its parameters: 64-bit block, 56-bit key, 16 rounds with 16 subkeys, a minor variant of the Feistel structure.

The key figure is 56, not 64. DES accepts a 64-bit key input, but every eighth bit is a parity bit and contributes nothing; 56 bits do the work. Swapping the block size and the key size is the most common single error on this material. And the reason DES died matters: decades of public analysis have turned up no fatal cryptanalytic weakness. The key length is the problem, not the algorithm — $2^{55}$ average trials is simply no longer a lot.

Triple DES

3DES keeps DEA and applies it three times in an encrypt–decrypt–encrypt arrangement:

$C = E (K_{3}, D (K_{2}, E (K_{1}, P)))$

With three independent keys the effective key length is 168 bits. With two keys, setting $K_{1} = K_{3}$ , it is 112 bits. Attaching 168 to the two-key variant is the trap.

Why is the middle stage a decryption? There is no cryptographic significance whatsoever — it is backward compatibility. Set $K_{1} = K_{2} = K_{3}$ and the expression collapses to $E (K, D (K, E (K, P))) = E (K, P)$ , ordinary single DES, so a 3DES implementation can talk to a legacy DES peer. Learners routinely invent a security reason for it; there is none. Standardisation ran ANSI X9.17 (1985) to FIPS 46-3 (1999) to NIST SP 800-67 (2017). Its two drawbacks are that it is slow — three passes of an algorithm designed for 1970s hardware — and that its 64-bit block is too small for modern data volumes.

AES

AES is FIPS 197, published November 2001, from NIST's 1997 open call: fifteen candidates, five finalists, and Rijndael the winner. Its parameters:

Block size is always 128 bits. Only the key varies. "AES has a variable block size" is false and is a reliable distractor.
Key size 128, 192 or 256 bits, giving 10, 12 or 14 rounds respectively.
It is not a Feistel cipher. The whole block is processed in parallel every round, and the consequence is that AES decryption is not the same algorithm as AES encryption — the free-decryption property Feistel buys you is precisely what AES gives up.

Each round is built from four transformations, and you should be able to name each one and say what it is for:

SubBytes — a byte-by-byte table lookup. This is the substitution, and it supplies confusion.
ShiftRows — the rows of the state are rotated left by 0, 1, 2 and 3 positions. Diffusion across rows.
MixColumns — each byte of a column becomes a function of all four bytes of that column. Diffusion across columns.
AddRoundKey — a bitwise XOR of the state with the round key. It is its own inverse, and it is the only transformation that uses the key.

Because AddRoundKey is the only key-dependent step, the cipher begins and ends with it: any transformation applied before the first or after the last AddRoundKey could be undone by an attacker without the key and would add nothing. Key expansion turns a 128-bit key into 44 words of 32 bits. And the final round omits MixColumns, which keeps the encryption and decryption structures aligned.

The right half passes through untouched to become the next left half. That is what lets the receiver recompute F forwards instead of inverting it.

The row that gets asked about most is the key size. DES has a 64-bit block and a 56-bit key; the other seventeen key-input bits either do not exist or are parity.