AES (Rijndael)

October 2001. NIST publishes FIPS-197: the winner of a five-year open competition is Rijndael, by two Belgian cryptographers who never worked for any intelligence service. A quarter-century later, this cipher protects iMessage, banking transactions, SSL/TLS traffic to google.com, and NSA TOP SECRET data (AES-256). No publicly known attack exists that beats brute force on the full 14 rounds of AES-256. A standard chosen by open vote became the most-vetted cipher in human history.

• **iMessage and WhatsApp**: end-to-end message encryption is built on AES-256 with a unique session key per chat; key exchange runs over X3DH + Double Ratchet (Signal Protocol)
• **TLS 1.3 (2018)**: about 70% of web traffic uses AES-GCM as the symmetric cipher; AES-NI on servers delivers terabit-per-second throughput
• **BitLocker, FileVault, LUKS**: full-disk encryption on Windows/macOS/Linux is built on AES-XTS (a special mode for disks); the key is derived from a password via PBKDF2 or Argon2

SubBytes: the single nonlinear step

In 1997 NIST announced an open competition to replace DES. Out of 15 candidates, five reached the final round, and in 2001 the winner was Rijndael by Belgian researchers Joan Daemen and Vincent Rijmen. The standard was named AES (Advanced Encryption Standard). The block size is 128 bits, key size is 128, 192, or 256 bits, with 10, 12, or 14 rounds respectively. Unlike DES this is not a Feistel network but an **SP-network** (Substitution-Permutation): each round applies four transformations - SubBytes, ShiftRows, MixColumns, AddRoundKey. **SubBytes** is the only nonlinear operation, and without it AES would be linear, which means it would break under simple linear algebra.

SubBytes treats the state as a 4x4 matrix of bytes. Each byte is replaced via a lookup table (S-box) of 256 entries. This S-box is constructed mathematically: for a byte b, its new value = affine transformation of the multiplicative inverse of b in GF(2^8). This gives the S-box maximum nonlinearity and a balanced distribution, both critical for resistance against differential and linear cryptanalysis. The affine transformation is added separately to eliminate fixed-points (b -> b) and opposite fixed-points (b -> ~b).

ShiftRows and MixColumns: diffusion

SubBytes is a local operation: each byte is replaced independently. To make a change in one input byte affect many output bytes, **diffusion** is needed. **ShiftRows** cyclically rotates the rows of the 4x4 state: row 0 stays, row 1 shifts 1 byte left, row 2 shifts 2, row 3 shifts 3. This step spreads bytes across columns. **MixColumns** multiplies each column by a fixed matrix in GF(2^8) - one input byte affects all 4 output bytes of the column. Together these two steps deliver **full diffusion** in two rounds: one input bit changes all 128 output bits.

AES avalanche effect: one flipped plaintext bit changes on average 64 ciphertext bits (50%) - an ideal score. By comparison, a single-round AES without MixColumns does not reach avalanche because diffusion is slow. Shannon's 1949 principles formalized this as 'confusion' (nonlinear relationship between key and ciphertext, realized via SubBytes) and 'diffusion' (spreading plaintext redundancy through ciphertext, realized via ShiftRows + MixColumns). AES is the canonical example of these principles.

Key Expansion

From one 128/192/256-bit key, AES must derive 11/13/15 round keys of 128 bits each - 176/208/240 bytes of key material total. **Key Expansion** does this. The algorithm: split the master key into 4-byte words (4/6/8 words respectively), then iteratively generate new words: w[i] = w[i - Nk] XOR f(w[i-1]), where f is either a trivial copy or a special transformation RotWord + SubWord + XOR with RCON for every Nk-th word. RCON is a table of powers of 2 in GF(2^8): rcon[i] = 2^(i-1).

Key Expansion properties: (1) nonlinearity via SubWord (S-box applied to 4 bytes) - a linear key schedule would be vulnerable to related-key attacks; (2) one-way by design - knowing one round key, master key recovery is not possible in polynomial time; (3) cheap incremental generation - keys can be computed on the fly in hardware. A weakness was noted in 2009: for AES-256 a related-key attack exists on the full 14 rounds with complexity 2^99 (Biryukov & Khovratovich) - an academic threat, not practical, since it requires control over the relationship between keys.

AES security

After 25 years of public analysis, AES has received no practical attack better than full brute force. The best known attack on AES-128 is biclique cryptanalysis (Bogdanov, Khovratovich, Rechberger 2011) with complexity 2^126.1 - just 2 bits more efficient than 2^128 brute force. On modern hardware 2^128 is fundamentally infeasible: a billion GPUs over a billion years would cover ~2^100. AES-256 has additional margin: 2^254 even for hypothetical attacks on 14 rounds. This is enough even accounting for quantum computers (Grover's algorithm reduces 2^n to 2^(n/2)) - AES-256 delivers 128-bit post-quantum security.

What attacks AES in practice: (1) Side-channel - timing attacks on cache (Bernstein 2005 showed leaks via S-box access time distribution), power analysis, EM emission. Mitigations: constant-time implementations, AES-NI hardware instructions; (2) Implementation bugs - wrong mode usage (ECB instead of CBC/GCM, nonce reuse in GCM); (3) Key management - master key leaks via memory dumps, weak PBKDF2/Argon2 when deriving a key from a password. The algorithm itself is a wall; the attacks target what surrounds it.

Key Ideas

• **SubBytes** is the single nonlinear step of AES, implemented via multiplicative inverse in GF(2^8) and an affine transformation; the source of cryptographic strength
• **ShiftRows + MixColumns** are linear diffusion operations: in 2 rounds one input bit affects all 128 output bits (avalanche effect)
• **Key Expansion** generates 11/13/15 round keys from one master key via SubWord, RotWord, and RCON constants; protection against related-key attacks
• **Security** - no practical attacks against the algorithm in 25 years; real vulnerabilities come from side-channels (timing, power) and misuse (nonce reuse, fixed IV)

Related Topics

FIPS-197 from the opening reshaped the industry: an open competition demonstrated that the best cipher is chosen by public analysis, not by the closed-door principle. AES sits at the center of modern cryptography and connects to an entire stack of practical protocols:

• DES and 3DES — The predecessor to AES; the NIST competition to replace DES in 1997-2001 set the criteria (128-bit block, open design, hardware efficiency) under which Rijndael won
• Block cipher modes — AES itself encrypts only 128 bits; for larger messages modes are required (CBC, CTR, GCM); the wrong mode (ECB, repeated nonce) breaks security worse than a weak block cipher
• AEAD and GCM — AES-GCM is the modern AEAD standard, giving confidentiality and integrity at the same time; used in TLS 1.3 and most production systems

Вопросы для размышления

• AES-128 protects banking traffic and, under a quantum computer, would degrade to 64-bit security (Grover). AES-256 would degrade to 128. Should legacy systems migrate to AES-256 now, or is that premature optimization?
• Daemen and Rijmen published the full Rijndael specification before winning the competition - and it helped, not hurt. Compare this with NSA's approach to designing DES (S-boxes kept secret for 15 years). Which approach wins long-term?
• AES-NI accelerates encryption by 10x and provides a constant-time implementation against timing attacks. What happens to system security if a vulnerability is found in the AES-NI hardware block itself?

Связанные уроки

• crypto-13-des — DES is the predecessor; understanding Feistel vs SPN matters for AES
• crypto-15-block-cipher-modes — AES is used in all block cipher modes
• crypto-07-computational-complexity — 128/256-bit keys: impossibility of brute force through complexity
• alg-01-big-o — O(2^128) for AES-128: why this is unreachable even for quantum computers
• net-23-https-tls
• net-34-ipsec