AES, in depth: GF(2^8) arithmetic, the derived S-box, the four round operations, a verified implementation, modes, nonces and side channels

What AES is

AES is a block cipher: a keyed permutation on 128-bit blocks. With a fixed key it maps each of the 2^128 possible 16-byte inputs to a distinct 16-byte output, and without the key that mapping should be indistinguishable from a random permutation. Keys are 128, 192 or 256 bits, and the cipher runs 10, 12 or 14 rounds respectively. The block size is always 128 bits; Rijndael allowed other block sizes, but the standard does not.

AES is a substitution-permutation network. Each round applies a non-linear substitution to every byte, mixes bytes across the block so that a change anywhere spreads everywhere, and XORs in a round key derived from the main key. Claude Shannon called the two properties confusion and diffusion; after two rounds every output byte depends on every input byte, and the remaining rounds are security margin.

The 16 bytes are arranged as a 4 x 4 state filled column by column: bytes 0 to 3 form the first column, 4 to 7 the second, and so on. Rows and columns matter because two of the operations act on rows and one on columns.

Arithmetic in GF(2^8) and the S-box

AES treats each byte as a polynomial with coefficients in {0, 1}: the byte 0x53, binary 01010011, is x^6 + x^4 + x + 1. Addition is XOR. Multiplication is polynomial multiplication reduced modulo the irreducible polynomial x^8 + x^4 + x^3 + x + 1, which is 0x11B. This structure, the finite field GF(2^8), gives every nonzero byte a multiplicative inverse, and everything in AES except XOR is built from it.

The basic step is multiplying by x, which is the byte value 2: shift left, and if a bit fell off the top, XOR with 0x1B (the low eight bits of 0x11B). Any product follows by shift-and-add, exactly like schoolbook binary multiplication with XOR instead of addition.

The S-box is not a random table. For each byte it takes the multiplicative inverse in GF(2^8) (with 0 mapped to 0), then applies a fixed affine transform over bits: XOR the inverse with four rotations of itself and with the constant 0x63. The inverse supplies strong non-linearity, among the best known resistance to linear and differential cryptanalysis for an 8-bit permutation (differential uniformity 4, nonlinearity 112), and the affine step removes the algebraic simplicity of a pure inverse and ensures no byte maps to itself. Because the construction is public and explained, nobody has to wonder whether the table hides a back door.

A complete implementation

The implementation below is written for clarity, not speed or secrecy, and computes the S-box from its definition. It reproduces the FIPS-197 example vectors for all three key sizes, including ciphertext 69c4e0d86a7b0430d8cdb78070b4c55a for key 000102...0f and plaintext 00112233...ff.

def xtime(a):
    """Multiply by x (that is, by 2) in GF(2^8) modulo x^8 + x^4 + x^3 + x + 1."""
    a <<= 1
    return (a ^ 0x11B) if a & 0x100 else a

def gmul(a, b):
    r = 0
    while b:
        if b & 1:
            r ^= a
        a, b = xtime(a), b >> 1
    return r

def ginv(a):
    """Multiplicative inverse: a^254, since a^255 = 1 for every nonzero a."""
    r = 1
    for _ in range(254):
        r = gmul(r, a)
    return r if a else 0

def rotl8(x, n):
    return ((x << n) | (x >> (8 - n))) & 0xFF

SBOX = []
for v in range(256):
    b = ginv(v)
    SBOX.append(b ^ rotl8(b, 1) ^ rotl8(b, 2) ^ rotl8(b, 3) ^ rotl8(b, 4) ^ 0x63)

def expand_key(key):
    nk = len(key) // 4                  # 4, 6 or 8 words
    nr = nk + 6                         # 10, 12 or 14 rounds
    w = [list(key[4*i:4*i+4]) for i in range(nk)]
    rcon = 1
    for i in range(nk, 4 * (nr + 1)):
        t = w[i-1][:]
        if i % nk == 0:
            t = t[1:] + t[:1]                       # RotWord
            t = [SBOX[x] for x in t]                # SubWord
            t[0] ^= rcon
            rcon = xtime(rcon)
        elif nk > 6 and i % nk == 4:
            t = [SBOX[x] for x in t]                # extra SubWord for AES-256
        w.append([a ^ b for a, b in zip(w[i-nk], t)])
    return [sum(w[4*r:4*r+4], []) for r in range(nr + 1)], nr

def sub_bytes(s):
    return [SBOX[x] for x in s]

def shift_rows(s):
    # state byte index = 4*column + row; row r rotates left by r columns
    return [s[4*((c + r) % 4) + r] for c in range(4) for r in range(4)]

def mix_columns(s):
    out = []
    for c in range(4):
        a0, a1, a2, a3 = s[4*c:4*c+4]
        out += [gmul(a0, 2) ^ gmul(a1, 3) ^ a2 ^ a3,
                a0 ^ gmul(a1, 2) ^ gmul(a2, 3) ^ a3,
                a0 ^ a1 ^ gmul(a2, 2) ^ gmul(a3, 3),
                gmul(a0, 3) ^ a1 ^ a2 ^ gmul(a3, 2)]
    return out

def add_round_key(s, k):
    return [a ^ b for a, b in zip(s, k)]

def encrypt_block(block, key):
    rk, nr = expand_key(key)
    s = add_round_key(list(block), rk[0])
    for r in range(1, nr):
        s = add_round_key(mix_columns(shift_rows(sub_bytes(s))), rk[r])
    s = add_round_key(shift_rows(sub_bytes(s)), rk[nr])   # no MixColumns
    return bytes(s)

ShiftRows rotates row r left by r positions, so the four bytes of each column end up in four different columns. MixColumns multiplies each column by a fixed matrix with entries 2, 3, 1, 1 in rotating positions; the matrix is chosen so that any change in k input bytes of a column changes at least 5 - k output bytes. Together they give full diffusion in two rounds. The final round omits MixColumns, which makes decryption structurally symmetric without costing security. Decryption runs the inverse operations in reverse order, using the inverse S-box and a MixColumns matrix with entries 14, 11, 13 and 9.

The key schedule stretches the key into one 16-byte round key per round plus one. Every Nk-th word is rotated, passed through the S-box and XORed with a round constant (1, 2, 4, 8 and so on, doubling in the field), which breaks symmetry between rounds. AES-256 adds an extra S-box step halfway through each eight-word block.

Worked example: tracing round one

FIPS-197 Appendix B encrypts plaintext 3243f6a8885a308d313198a2e0370734 under key 2b7e151628aed2a6abf7158809cf4f3c. Running the code above, the first round goes like this:

Check one byte by hand. The first byte 0x19 becomes 0xd4 through the S-box; the second row of the first column starts as 0x3d and becomes 0x27. ShiftRows rotates row 1 left by one, so 0x27 wraps to the last column and 0xbf arrives from column 1; rows 2 and 3 bring in 0x5d and 0x30, so the first column reads d4, bf, 5d, 30. After all ten rounds the ciphertext is 3925841d02dc09fbdc118597196a0b32, matching the standard. Write the same table from your own implementation; when a port goes wrong, the first differing row tells you which operation is broken.

Modes of operation

A block cipher encrypts exactly 16 bytes. A mode of operation turns it into something that encrypts messages, and nearly all real AES failures live here.

ECB leaks structure: an image encrypted block by block still shows its outline. CBC suffers padding-oracle attacks (Vaudenay, 2002): if the receiver reveals in any way whether a decrypted message had valid padding, an attacker can decrypt traffic byte by byte. Unauthenticated CBC leaks this directly, and MAC-then-encrypt designs can leak it through different errors or timing for bad padding and bad MACs, as Lucky Thirteen showed against TLS. CTR is clean but malleable: flipping a ciphertext bit flips the same plaintext bit, so an attacker can change an amount in a payment message without knowing the key.

Use authenticated encryption, which means GCM in most libraries. Its one hard rule is that a (key, nonce) pair must never repeat. Reusing a nonce in GCM reuses the CTR keystream, so the XOR of two ciphertexts equals the XOR of their plaintexts, and it also lets an attacker recover the authentication subkey and forge messages. With random 96-bit nonces, NIST SP 800-38D limits a single key to 2^32 encryptions; rotate keys well before that, or use counters you can prove never repeat.

import os
from cryptography.hazmat.primitives.ciphers.aead import AESGCM

key = AESGCM.generate_key(bit_length=256)    # store in a KMS, not next to the data
aead = AESGCM(key)

def seal(plaintext: bytes, context: bytes) -> bytes:
    nonce = os.urandom(12)                   # fresh per message, never reused with this key
    return nonce + aead.encrypt(nonce, plaintext, context)

def open_(blob: bytes, context: bytes) -> bytes:
    nonce, ct = blob[:12], blob[12:]
    return aead.decrypt(nonce, ct, context)  # raises InvalidTag if anything was altered

The context argument is associated data: authenticated but not encrypted. Bind each ciphertext to where it belongs, such as a record ID and table name, so an attacker cannot move a valid ciphertext from one row to another.

Hardware and side channels

Textbook implementations, including the one above, index tables with secret-dependent bytes. Fast software AES traditionally merged SubBytes, ShiftRows and MixColumns into four 1 KB lookup tables, and in 2005 Daniel Bernstein, and separately Osvik, Shamir and Tromer, showed that cache timing reveals which table entries were used and therefore key bytes. The lesson generalises: a cipher can be mathematically sound and leak its key through timing.

Modern CPUs remove the problem with dedicated instructions: AES-NI on x86 (AESENC, AESENCLAST, AESDEC, AESKEYGENASSIST and others) and the ARMv8 cryptography extensions (AESE, AESD, AESMC). Each instruction performs a full round in constant time, and because CTR and GCM blocks are independent, pipelining several blocks at once lets throughput reach several gigabytes per second per core. Without hardware support, use a bitsliced constant-time implementation or switch to ChaCha20-Poly1305, which was designed to be fast and constant-time in plain software. Never ship your own implementation; use a maintained library such as OpenSSL, BoringSSL or libsodium.

How secure is it, and how it really fails

Against full AES the best known single-key attacks, the biclique attacks of 2011, shave only a couple of bits off exhaustive search, leaving AES-128 at roughly 2^126 work. Related-key attacks on AES-256 exist in theory but require the attacker to obtain encryptions under keys with chosen relationships, which correctly generated keys never have. Grover's algorithm would give a quantum computer at most a square-root speedup on key search, and it parallelises poorly; AES-256 is the usual choice when data must stay confidential for decades.

The failures that actually occur are elsewhere: nonces reused after a VM snapshot is restored, keys hard-coded in source, ECB chosen by a library default, unauthenticated CBC, or keys derived directly from passwords. Derive keys from passwords only through a deliberately slow function, as covered in password hashing with bcrypt, and agree on session keys with an exchange such as Diffie-Hellman or by wrapping them with RSA. For integrity on its own, without secrecy, use a MAC or the hashes described in the SHA family.

What to do next

1. Run the implementation above and confirm it prints the FIPS-197 vectors for all three key sizes.
2. Write decryption with the inverse S-box and inverse MixColumns, and check round trips on random blocks.
3. Encrypt an image with ECB to see the leak for yourself, then with CTR.
4. Grep your codebase for ECB, CBC without a MAC, hard-coded keys and fixed nonces.
5. Move application encryption to a library AEAD (AES-GCM or ChaCha20-Poly1305) with associated data bound to the record.
6. Document a nonce strategy and a key rotation threshold for every key, and keep keys in a KMS.