AES
Almost every encrypted byte on the internet passes through AES. Unlike the public-key schemes in this catalogue, its security does not reduce to any mathematical problem. It rests on twenty-five years of cryptanalysis that has barely dented it, and in practice the attacks that matter are on how it is implemented.
- Rests on
- Resistance to cryptanalysis; there is no reduction to a number-theoretic problem
- Standards
- FIPS 197 (2001, updated 2023); modes in NIST SP 800-38 series
- Sizes
- 128-bit block; 128-, 192- or 256-bit key; 10, 12 or 14 rounds
- Best known attack
- Biclique cryptanalysis: an AES-128 key in about 2126.1 operations, four times faster than brute force
- Quantum
- Grover's algorithm speeds up key search; NIST uses AES-128 key search as the benchmark for its lowest post-quantum category
The cipher
AES is Rijndael, by Daemen and Rijmen, chosen by NIST in 2000 after an open competition. It encrypts a 16-byte block, arranged as a 4 × 4 array of bytes, through a fixed number of rounds. Each round applies four steps:
- SubBytes. Replace every byte by its image under a fixed 8-bit S-box. This is the only nonlinear step.
- ShiftRows. Rotate row i of the array left by i positions, so each column's bytes move to four different columns.
- MixColumns. Multiply each column by a fixed 4 × 4 matrix over GF(28). A change in one input byte changes all four output bytes of its column.
- AddRoundKey. XOR in a 16-byte round key derived from the cipher key.
The S-box is not an arbitrary table. It is inversion in the field GF(28), with 0 sent to 0, followed by a fixed affine map over GF(2). Inversion was chosen because its differential and linear properties are close to the best any 8-bit S-box can have, and the affine map removes its simple algebraic structure. The code behind this page builds the S-box from exactly that definition, and checks it against the examples in the standard.
With the S-box built, the whole cipher is about a hundred lines. It reproduces the example of FIPS 197 appendix C.1:
key 000102030405060708090a0b0c0d0e0f plaintext 00112233445566778899aabbccddeeff ciphertext 69c4e0d86a7b0430d8cdb78070b4c55a
FIPS 197 appendix C.1, AES-128, recomputed at build time
Diffusion, measured
The design goal of the round structure is that every output bit depends on every input bit after very few rounds, the property Daemen and Rijmen call the wide-trail strategy. It can be watched directly. Take two plaintexts that differ in a single bit, encrypt both under the same key, and count how many of the 128 state bits differ after each round:
| Round | Bits changed |
|---|---|
| 1 | 16.0 |
| 2 | 64.6 |
| 3 | 63.6 |
| 4 | 64.2 |
| 5 | 63.9 |
| 6 | 63.7 |
| 7 | 63.0 |
| 8 | 63.5 |
| 9 | 63.6 |
| 10 | 63.8 |
After one round the difference has spread to a single column, 16.0 bits on average. The S-box changes one byte, and MixColumns spreads it to the four bytes of that column. After round 2, ShiftRows has sent those four bytes to four different columns, and the difference covers the whole state: 64.6 bits, indistinguishable from the 64 of two unrelated random blocks. It stays there through round 10. Full diffusion after two rounds is by design, and it is part of why published attacks meaningfully faster than brute force reach only about seven of AES-128's ten rounds.
Cryptanalysis
The design was built to resist differential and linear cryptanalysis with a provable margin: every four-round trail passes through at least 25 active S-boxes, which bounds the probability of any single differential or linear trail far below what an attack could use. Twenty-five years on, the best attack on the full cipher is the 2011 biclique attack of Bogdanov, Khovratovich and Rechberger. It recovers an AES-128 key in about 2126.1 operations, compared with 2128 for brute force, with a data requirement that makes it purely theoretical. Related-key attacks on AES-192 and AES-256 exist, but need keys with a chosen relationship, which proper protocols never produce.
The attacks that have mattered in practice are side channels. Fast software AES used lookup tables indexed by secret-dependent bytes, and which table entries are in the processor's cache leaks those bytes through timing. Bernstein demonstrated remote timing leakage in 2005, and Osvik, Shamir and Tromer recovered full keys through cache attacks in 2006. The fix is to avoid secret-dependent memory access: the AES instructions in modern processors, or bitsliced constant-time software.
Modes, and what can go wrong there
A block cipher on its own encrypts 16 bytes. Real use needs a mode. The standard choice is GCM (NIST SP 800-38D), which encrypts in counter mode and authenticates with a polynomial hash over GF(2128). GCM's security depends absolutely on never repeating a nonce under one key: a repeated nonce reveals the XOR of two plaintexts and allows forgeries. Where nonces cannot be guaranteed unique, nonce-misuse-resistant modes such as AES-GCM-SIV limit the damage. ECB mode, which encrypts each block independently, leaks the pattern of equal blocks and should not be used at all.
The quantum question
Grover's algorithm searches 2k keys in about 2k/2 quantum steps, which is often summarised as halving the key length. In practice the steps are long, sequential and hard to parallelise, so the real cost is far above 264 for AES-128. NIST defines its lowest post-quantum security category as "at least as hard as key search on AES-128" and does not consider AES-128 broken by quantum computers. AES-256 is the conservative choice where a large margin is wanted. Either way, the symmetric side of the quantum transition is a parameter choice, not a replacement, unlike RSA and elliptic-curve cryptography.
Primary sources
- NIST FIPS 197, Advanced Encryption Standard (AES) (2001, updated 2023)
- J. Daemen and V. Rijmen, The Design of Rijndael, Springer (2002)
- A. Bogdanov, D. Khovratovich and C. Rechberger, "Biclique cryptanalysis of the full AES", ASIACRYPT 2011
- D. A. Osvik, A. Shamir and E. Tromer, "Cache attacks and countermeasures: the case of AES", CT-RSA 2006
- D. J. Bernstein, "Cache-timing attacks on AES" (2005)
- M. Dworkin, NIST SP 800-38D, Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC (2007)