The Advanced Encryption Standard (AES)

AES is a substitution-permutation network (SPN): a block cipher built from a fixed number of rounds, each combining a confusion layer (nonlinear substitution) with a diffusion layer (linear mixing). This contrasts with the PRP abstraction instantiated by DES's Feistel structure, where only half the block is transformed per round and diffusion accumulates slowly. AES instead transforms the entire 128-bit block at once, arranged as a 4×4 matrix of bytes called the state:

The 16 input bytes fill this matrix column by column. AES supports three key lengths — 128, 192, and 256 bits — which fix the number of rounds $N_r$ to 10, 12, and 14 respectively. A longer key does not change the block size (always 128 bits) but adds rounds, since a longer key schedule needs more mixing to fully "use up" the extra key material and resist related-key attacks. Every internal operation lives inside the finite field $GF(2^8)$, represented as polynomials over $GF(2)$ modulo the irreducible polynomial

Byte addition is XOR; byte multiplication is polynomial multiplication modulo $m(x)$. This field structure is what makes the S-box (built from multiplicative inversion in the field) simultaneously algebraically clean — so its properties are provable — and cryptographically strong, since inversion in $GF(2^8)$ has near-optimal nonlinearity and no fixed points that would help a linear attacker.

Each AES round (except the last) applies four transformations in sequence to the state:

1. SubBytes — every byte is replaced independently using a fixed 256-entry lookup table, the S-box. Mathematically, byte $b$ maps to $b^{-1}$ in $GF(2^8)$ (with $0 \mapsto 0$), followed by a fixed $GF(2)$-affine transformation:

where $A$ is a fixed invertible matrix over $GF(2)$ and $c$ is a fixed constant byte. This is the confusion layer: it is the only nonlinear step in the whole cipher, and it is applied to every byte independently.

2. ShiftRows — row $i$ of the state is cyclically shifted left by $i$ bytes ($i = 0,1,2,3$). Row 0 is untouched; row 3 shifts by three positions. This diffuses bytes across columns, since MixColumns (next) only mixes within a column — ShiftRows ensures that after a few rounds, every output byte depends on bytes from every input column.

3. MixColumns — each column, viewed as a 4-term polynomial over $GF(2^8)$, is multiplied by a fixed polynomial modulo $x^4+1$. Equivalently, each column vector $c = (s_0,s_1,s_2,s_3)^T$ is left-multiplied by the fixed matrix

with all arithmetic in $GF(2^8)$. This matrix is MDS (maximum distance separable): any change to a single input byte changes all four output bytes, giving maximal diffusion within a column with minimal cost.

4. AddRoundKey — the state is XORed, byte by byte, with a 128-bit round key derived from the master key by the key schedule. The final round omits MixColumns (a design choice that makes encryption and decryption structurally symmetric and doesn't weaken security, since one more linear layer at the very end would not add nonlinear confusion).

Key schedule

The master key is expanded into $N_r+1$ round keys (each 128 bits, i.e. 4 words of 32 bits) via a recursive schedule. For 128-bit keys, the total expanded key is $4 \times (N_r+1) = 44$ words. Every fourth word applies a nonlinear transformation: rotate the word's bytes, substitute each byte through the S-box, then XOR with a round constant $\text{Rcon}[i]$ that breaks symmetry between rounds and prevents slide-style attacks. ``` PSEUDOCODE — AES Encryption (128-bit key, Nr = 10) function AES_Encrypt(plaintext[16], key[16]): state ← plaintext arranged column-major into 4x4 byte matrix w[0..43] ← KeyExpansion(key) // 44 words, 4 per round key state ← AddRoundKey(state, w[0..3]) // whitening: round 0 for round in 1 .. Nr - 1: state ← SubBytes(state) state ← ShiftRows(state) state ← MixColumns(state) state ← AddRoundKey(state, w[4round .. 4round+3]) // final round: no MixColumns state ← SubBytes(state) state ← ShiftRows(state) state ← AddRoundKey(state, w[4Nr .. 4Nr+3]) return state as ciphertext[16]

function KeyExpansion(key[16]): w[0..3] ← key split into 4 words (32 bits each) for i in 4 .. 43: temp ← w[i-1] if i mod 4 == 0: temp ← SubWord(RotWord(temp)) XOR Rcon[i/4] w[i] ← w[i-4] XOR temp return w

function SubBytes(state): for each byte b in state: b ← S_BOX[b] // fixed 256-entry table return state function ShiftRows(state): for row r in 0..3: state[r] ← CyclicLeftShift(state[r], r) return state function MixColumns(state): for each column c in state: c ← MDS_MATRIX × c // multiplication in GF(2^8) return state function AddRoundKey(state, roundKeyWords[4]): state ← state XOR roundKeyWords // byte-wise XOR return state ``` Decryption applies the inverse transformations (`InvSubBytes`, `InvShiftRows`, `InvMixColumns`) in reverse order with round keys used in reverse. Because MixColumns is linear and invertible over $GF(2^8)$, and SubBytes is a fixed invertible S-box, every step has a clean, efficiently computable inverse — this is essential for AES to be a genuine pseudorandom permutation rather than a one-way function.

Time complexity. Each round performs $O(1)$ work per byte across a fixed 16-byte state: SubBytes is 16 table lookups, ShiftRows is a fixed byte permutation, MixColumns is 16 constant-size field multiplications, AddRoundKey is 16 XORs. With $N_r \in \{10,12,14\}$ fixed rounds, one block encryption is $O(1)$ time in the block size (constant work per fixed-size block), or more precisely $\Theta(N_r)$ table operations — a small constant. On modern hardware with AES-NI, an entire round compiles to a single instruction, giving throughput of several GB/s per core. Encrypting an $n$-byte message under a chosen mode of operation costs $\Theta(n)$ block operations, i.e. linear in message length.

Space complexity. $O(1)$ beyond the message itself: the state is a fixed 16 bytes, the expanded key schedule is a fixed $4(N_r+1)$ words (176, 208, or 240 bytes), and the S-box table is a fixed 256-byte constant. No dynamic memory scales with input size except for the buffer holding the message being processed.

Correctness (decryptability). Decryption is correct because every round function is a bijection on the state space and the inverse pipeline applies the true inverses in reverse order. Formally, if round $r$ applies $f_r = \text{AddRoundKey}_r \circ \text{MixColumns} \circ \text{ShiftRows} \circ \text{SubBytes}$, then

(AddRoundKey is its own inverse under XOR). Composing these in reverse order recovers the original state exactly — this is a straightforward induction on rounds, using that $g \circ g^{-1} = \text{id}$ for each layer and that composition of bijections is invertible by reversing the order.

Security argument (why it resists cryptanalysis). AES's security is not proven in an absolute sense — like all practical block ciphers, its strength rests on 20+ years of failed attacks — but its design gives quantitative resistance guarantees against the two classical attack families:

• Differential cryptanalysis looks for input differences that propagate to output differences with high probability. The AES S-box has maximum differential probability $2^{-6}$ for any nontrivial input/output difference, and the MixColumns matrix being MDS guarantees that any active S-box in one round forces at least 4 active S-boxes in the next two rounds combined (the branch number is 5). Over 4 rounds this forces at least 25 active S-boxes, driving the best differential trail probability down to roughly $2^{-6 \times 25} = 2^{-150}$ — far below the $2^{-128}$ security target, meaning full-round differential attacks are infeasible.
• Linear cryptanalysis similarly exploits linear approximations to the S-box; the AES S-box has maximum linear bias $2^{-4}$ relative to $2^{-1}$ (uniform), and the same branch-number argument bounds the best linear approximation's correlation to well below what's needed to recover key bits faster than brute force.

The number of rounds (10 for 128-bit keys) is chosen with margin: the best known attacks on reduced-round AES-128 reach about 7 rounds with impractical time/data complexity, leaving a comfortable security margin over the full 10 rounds actually used.

Tradeoffs. AES's design trades a slightly larger, more structured state (versus DES's narrow Feistel channel) for far superior parallelism and diffusion speed — a good tradeoff on modern hardware but one reason it needed dedicated silicon support (AES-NI) to match DES's decades of hand-optimized software implementations at launch. Its clean algebraic structure (everything reduces to $GF(2^8)$ arithmetic) also made it the first major cipher subjected to serious algebraic cryptanalysis (XSL attacks), though these remain theoretical and far from practical.

Trace one round of AES-128 acting on a single state, focusing on how a one-byte change diffuses. Suppose the state (shown as hex bytes, column-major) begins as:

This is the well-known FIPS-197 test-vector plaintext state. Step through one round:

SubBytes. Each byte is replaced via the S-box, e.g. `32 → 23`, `88 → C4`, `31 → C7`, `E0 → E1`, ... (looked up from the fixed table). The transformation is nonlinear and byte-local: changing input byte `32` to `33` changes the S-box output completely (avalanche within the byte), but at this stage the change has not yet spread to other bytes.

ShiftRows. Row 1 shifts left by 1, row 2 by 2, row 3 by 3. A byte originally in row 1, column 0 moves to row 1, column 3. This step alone does not mix values — it only relocates bytes — but it guarantees that MixColumns (which only operates within a column) will next combine bytes that originated from different original columns.

MixColumns. Column 0, say $(63, 47, F6, A8)$ after the previous steps, is treated as a polynomial and multiplied by the fixed MDS matrix in $GF(2^8)$. Concretely the first output byte is:

where $2 \cdot b$ means "multiply by $x$ in $GF(2^8)$" (a left shift, XORed with `0x1B` if overflow occurs) and $3\cdot b = (2\cdot b)\oplus b$. Because the matrix is MDS, this single output byte now depends on all four input bytes of the column — a one-bit change anywhere in the column changes this byte with overwhelming probability.

AddRoundKey. The mixed state is XORed with round key 1 (derived via `KeyExpansion`), completing the round.

Diffusion trace. If we flip a single bit in the original plaintext byte at row0,col0 and re-run the pipeline: after round 1, the change has spread to all 4 bytes of column 0 (via MixColumns) but no others (ShiftRows hasn't yet mixed columns together for this round's output). After round 2, because ShiftRows moved column-0's transformed bytes into rows 1, 2, 3 of other columns before the next MixColumns, the change spreads to all 16 bytes of the state. This is the strict avalanche criterion in action: by round 2–3, roughly half of all output bits flip on average for a single input bit flip — exactly the diffusion behavior a secure block cipher requires, and it is measurable, not merely asserted, by running the pipeline explicitly as above.

AES emerged from an open, adversarial competition rather than a closed design process — a deliberate contrast to earlier standards designed behind closed government doors.

The competition itself was historic: unlike DES, whose S-boxes were altered by the NSA without public justification (later found to strengthen resistance to differential cryptanalysis, a technique not yet public at the time), every AES candidate and every design decision was published, scrutinized, and attacked in the open by academic teams worldwide. This transparency is now the accepted model for cryptographic standardization — the same open process was later used to select SHA-3 and post-quantum cryptographic standards.

AES sits underneath nearly the entire modern encrypted internet. TLS 1.2 and 1.3 use AES (typically in GCM mode) as the default symmetric cipher for HTTPS traffic. Disk encryption systems — BitLocker, FileVault, LUKS — use AES to protect data at rest. Wi-Fi security protocols WPA2 and WPA3 rely on AES for frame encryption. Messaging apps (Signal, WhatsApp) use AES as a building block inside their end-to-end encryption ratchets. Government and military systems use AES-256 for classified data under NSA Suite B / CNSA guidance. Hardware vendors — Intel, AMD, ARM — bake AES round functions directly into silicon (AES-NI, Crypto Extensions) because its ubiquity justifies dedicated transistors. Every use case builds AES into a system by first choosing a mode of operation (CBC, CTR, GCM) that specifies how successive blocks are chained — a decision every bit as important to overall security as the cipher itself.

Ask the tutor: How does choosing CBC versus GCM mode change the security guarantees AES alone doesn't provide?