AES

AES's key and block sizes, its key expansion, why it is a substitution-permutation network rather than a Feistel cipher, and the four round operations that each carry out one part of confusion or diffusion.

State AES's three key sizes, its fixed block size, and the round count that goes with each key size.
Name the four operations inside an AES round and what each one contributes.
Explain the GF(2^8) connection behind the AES S-box.
Explain why AES is an SPN rather than a Feistel cipher.

15 min read

Intuition

DES’s fixed 56-bit key put a hard ceiling on its own security, one that computing power eventually walked straight through. AES was chosen through an open competition specifically to replace it, with key sizes large enough that the DES keyspace arithmetic from the previous page stops being a threat at all. It is also built differently from DES at the structural level: not a Feistel network, but a substitution-permutation network that runs every operation over the whole block, every round.

Mechanism

AES operates at three key sizes — 128, 192 or 256 bits — with a block size fixed at 128 bits regardless of which key size is chosen. The round count depends only on the key size: 10 rounds for a 128-bit key, 12 for 192-bit, 14 for 256-bit. AES is not itself the name of a specific algorithm design; the Rijndael cipher was the design selected to become the Advanced Encryption Standard.

Formula

AES round count by key size

N_r = \begin{cases} 10 & N_k = 4 \\ 12 & N_k = 6 \\ 14 & N_k = 8 \end{cases}

$N_k$: key length in 32-bit words (4, 6 or 8)
$N_r$: round count for that key size

Mechanism

Before any rounds run, the key itself is expanded. For a 128-bit key, the key expansion algorithm takes the 16-byte key (4 words) and produces a linear array of 44 32-bit words — 176 bytes in total. Each round consumes a 4-word round key sliced from that array; 10 rounds plus the initial AddRoundKey step before round 1 accounts for the 11 round keys, $4 \times 11 = 44$ words. The same $N_b(N_r+1)$ formula, with $N_b=4$ fixed, gives 52 words for AES-192 and 60 for AES-256 — the lecture works through the 128-bit case explicitly; the other two follow the same arithmetic.

Four operations run inside every round, one of permutation and three of substitution:

SubBytes substitutes each byte of the block independently, through the AES S-box. This is the confusion stage.
ShiftRows is a simple permutation: bytes are shifted across the rows of the block’s state.
MixColumns is a substitution that mixes each column using arithmetic over $\text{GF}(2^8)$ .
AddRoundKey is a bitwise XOR of the current block with the round’s own slice of the expanded key.

ShiftRows and MixColumns together do the diffusion work that a P-box does in a Feistel cipher — ShiftRows moves bytes between positions, MixColumns spreads each byte’s influence across the other bytes in its column, so an attacker cannot isolate one S-box’s output from the rest of the block. AddRoundKey is where the secret key actually enters the computation, once per round.

Formula

Key expansion size

w = N_b (N_r + 1)

$N_b$: block size in 32-bit words — always 4, since the AES block is fixed at 128 bits
$N_r$: round count for the chosen key size
$w$: total words produced by key expansion

AES-128: w = 4(10+1) = 44 words, 176 bytes — the case the lecture walks through.

Mechanism

AES’s substitution work depends on arithmetic in the finite field $\text{GF}(2^8)$ , built on the irreducible polynomial $m(x) = x^8 + x^4 + x^3 + x + 1$ . Addition of two bytes in this field is plain bitwise XOR; MixColumns multiplies bytes using this field’s multiplication rule, reducing by $m(x)$ whenever a product overflows 8 bits. The AES S-box is built on the same field: its underlying mathematical function is the multiplicative inverse in $\text{GF}(2^8)$ — every nonzero byte in the field has exactly one multiplicative inverse, which is what makes SubBytes invertible and decryption possible. See Finite fields, GF(p) and GF(2^n) for the field construction and why every nonzero byte is guaranteed an inverse.

Aside

The lecture notes that “the S-boxes actually describe a mathematical function that is believed to achieve excellent diffusion and confusion,” and that cryptanalysis attempts to describe that function in simpler terms “have so far all failed.” The multiplicative-inverse structure above is exactly that function — algebraically simple to state, but combined with the rest of AES in a way that has resisted three decades of attempted shortcuts.

Exam detail

AES is a substitution-permutation network (SPN), not a Feistel cipher. The distinction the exam draws is structural: a Feistel round only ever runs its keyed function $F$ on half the block, leaving the other half untouched until the swap, and that split-swap shape is what makes decryption reuse the same network in reverse. An AES round runs all four operations — SubBytes, ShiftRows, MixColumns, AddRoundKey — over the entire 128-bit block, every round, with no untouched half. That means AES has no automatic reversal the way Feistel does: decryption needs an explicit inverse for each operation (an inverse S-box, an inverse ShiftRows, and so on), applied in reverse order.

Key size and block size are independent numbers and are tested separately: the block is always 128 bits no matter which key size is chosen, while the key size — 128, 192 or 256 bits — is what changes the round count.

Pitfall

Do not write “AES has a 128, 192 or 256 bit block.” The block is fixed at 128 bits; those three numbers are key sizes, and confusing the two is one of the fastest ways to lose a mark on this topic.

Recall

Why can't AES decrypt itself the way a Feistel cipher does, just by reversing the round keys?

Because a Feistel round only ever transforms half the block through its keyed function, leaving the split-swap structure reversible by construction regardless of what that function computes. AES runs SubBytes, ShiftRows, MixColumns and AddRoundKey over the whole block every round, with no untouched half to exploit — so each operation needs its own explicit inverse, run in reverse order, to undo encryption.

Source

Week 4 notes PDF