Block Ciphers & AES

AES is a substitution–permutation network: unlike the Feistel family, every layer transforms the whole block and every layer must be individually invertible. It operates on a 128-bit block held as a 4×4 byte matrix called the state, with 128/192/256-bit keys and 10/12/14 rounds respectively. Two decades of the most concentrated cryptanalysis in history have produced no practical break of the algorithm — every real AES compromise has been a side channel or a misuse of the mode around it.

The round structure #

Each round applies four transformations (the final round omits MixColumns):

flowchart LR
  S["State 4x4 bytes"] --> SB["SubBytes<br/>nonlinear"] --> SR["ShiftRows<br/>diffusion across columns"] --> MC["MixColumns<br/>diffusion within columns"] --> AK["AddRoundKey<br/>key mixing"] --> S2["next round"]

SubBytes — the only nonlinear step, applied bytewise via the S-box. Its construction is not arbitrary: take the byte's multiplicative inverse in $GF(2^8)$ (with $0 \mapsto 0$), then apply an affine transformation over $GF(2)$:

$$b'_i = b_i \oplus b_{(i+4) \bmod 8} \oplus b_{(i+5) \bmod 8} \oplus b_{(i+6) \bmod 8} \oplus b_{(i+7) \bmod 8} \oplus c_i$$

with constant $c = \texttt{0x63}$. Inversion in the field is the most nonlinear function available over $GF(2^8)$ — it is what gives AES its resistance to differential and linear cryptanalysis. The affine layer exists to destroy the clean algebraic form so the S-box has no simple expression that algebraic attacks could exploit, and to remove fixed points. Example: input 0x19 → output 0xd4.

ShiftRows — row $r$ rotates left by $r$ bytes. A pure permutation, and cheap, but essential: without it each column would evolve independently and AES would decompose into four unrelated 32-bit ciphers.

MixColumns — treats each column as a degree-3 polynomial over $GF(2^8)$ and multiplies it by the fixed $c(x) = 3x^3 + x^2 + x + 2$ modulo $x^4 + 1$. Equivalently, multiply each column by

$$\begin{pmatrix} 2&3&1&1 \\ 1&2&3&1 \\ 1&1&2&3 \\ 3&1&1&2 \end{pmatrix}$$

The matrix is MDS (maximum distance separable): changing one input byte changes all four output bytes. Together with ShiftRows this gives full diffusion in two rounds — after round 2, every output bit depends on every input bit.

AddRoundKey — bytewise XOR of the round key into the state. Trivially its own inverse; this is the only step where the key enters.

KeyExpansion derives the round keys from the cipher key: the last word of the previous round key is rotated, passed through the S-box, XORed with a round constant $\text{Rcon}[i] = x^{i-1}$ in $GF(2^8)$, then XORed forward. The round constants break symmetry — without them, related-key attacks exploiting the schedule's regularity become possible. AES-256 needs 14 rounds partly because its key schedule is weaker per-bit, which is also why AES-256 has known related-key attacks that AES-128 does not (theoretical only, and irrelevant when keys are chosen randomly).

The cipher is not the system #

AES encrypts exactly one 128-bit block. Everything real needs a mode of operation, and the mode is where deployments fail:

Attacks that actually work #

No practical cryptanalytic break exists. Biclique attacks (2011) reduce AES-128 from $2^{128}$ to $2^{126.1}$ — a factor of ~4 against a number with 38 digits, of no operational consequence. The real threats are physical:

• Cache-timing. Software implementations traditionally use precomputed T-tables (4 KB of lookup tables merging SubBytes and MixColumns). Table indices depend on key-mixed data, so cache hit/miss patterns leak them. Bernstein (2005) recovered a full key remotely from timing alone; Osvik–Shamir–Tromer recovered a full dm-crypt partition key from 800 writes, 65 ms of measurement — and an OpenSSL key from 300 encryptions in 13 ms. This is a direct consequence of the table-lookup approach to $GF(2^8)$.
• Power/EM analysis. DPA on smartcards and embedded devices; countered with masking and hardware shielding.
• Fault injection. Differential fault analysis recovers a key from a handful of faulty ciphertexts.

The mitigation that ended the timing problem in practice is hardware: Intel's AES-NI (2010) and ARMv8 cryptographic extensions implement rounds as single instructions, constant-time by construction and roughly 3–10× faster than table code. Where hardware support is absent, bitsliced implementations are the correct fallback — never the naive T-table version.

Source claims audit #

Seeded from a university lab manual (AES lab — the most complete lab in the source). Status of its load-bearing claims: