Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 40 ยท Symmetric Encryption

Block Ciphers and AES

Understand block ciphers as keyed permutations, compute the real AES S-box in Python, and build a tiny substitution-permutation cipher with avalanche.

A stream cipher produces a keystream and XORs it with the data. A block cipher works differently: it takes a fixed-size chunk of data (a block) and scrambles the whole chunk at once, under control of a secret key. The Advanced Encryption Standard (AES) is the block cipher that protects most of the world's data today: HTTPS connections, disk encryption, Wi-Fi, password managers and cloud storage.

In this lesson you will learn what a block cipher is in precise terms, see why AES works on 128-bit blocks with keys of 128, 192 or 256 bits, compute the real AES S-box from scratch, and build a small cipher of your own that has the same structure as AES, only far smaller and not secure. Building the toy version is the best way to understand why each ingredient is there.

A block cipher is a keyed permutation

Fix a key. A block cipher then becomes a function that maps each possible block to exactly one other block, and no two blocks map to the same output. Mathematically this is a permutation of all possible blocks, so it can be undone: decryption is the inverse permutation. A different key selects a different permutation.

For a block size of n bits, there are 2n possible blocks. AES uses n = 128, so it picks one of the astronomically many permutations of 2128 items. The key does not specify the whole permutation (that would take too much memory); it selects one from a family, and a good cipher makes it look like a randomly chosen one.

Two properties are essential, both described by Claude Shannon in 1949:

  • Confusion: the relationship between the key and the ciphertext should be complicated, so you cannot solve for the key.
  • Diffusion: a change of one input bit should change about half of the output bits, spreading the influence of every bit over the whole block.

The block size matters too. If the block is only 64 bits, then after roughly 232 blocks (about 32 GiB) under one key, identical blocks start to appear by chance and leak information. That is why old 64-bit ciphers such as 3DES and Blowfish were retired, and why AES chose 128 bits.

The structure of AES: rounds

AES does not scramble the block in one step. It repeats a simple round many times, and the repetition is what produces the strong result. Each round of AES works on a 4x4 grid of bytes (the state) and applies four steps:

  1. SubBytes: replace each byte by its entry in a fixed lookup table, the S-box. This is the only nonlinear step and provides confusion.
  2. ShiftRows: rotate row i of the grid left by i positions.
  3. MixColumns: mix the four bytes in each column with a fixed matrix multiplication over a finite field. Together with ShiftRows this provides diffusion.
  4. AddRoundKey: XOR the state with a round key derived from the main key by the key schedule.

The number of rounds depends on the key size:

Variant Key size Rounds Block size
AES-128 128 bits 10 128 bits
AES-192 192 bits 12 128 bits
AES-256 256 bits 14 128 bits

The last round omits MixColumns. The block size is always 128 bits, whatever the key size. A bigger key means a bigger search space for brute force and a few extra rounds.

flowchart TD
    P["Plaintext block<br/>128 bits"] --> A0["AddRoundKey<br/>(round key 0)"]
    A0 --> R["Rounds 1 to N-1:<br/>SubBytes, ShiftRows,<br/>MixColumns, AddRoundKey"]
    R --> F["Final round:<br/>SubBytes, ShiftRows,<br/>AddRoundKey"]
    F --> C["Ciphertext block<br/>128 bits"]

The AES structure. N is 10, 12 or 14 depending on the key size.

The AES S-box, computed

The AES S-box is not a random table. It is defined by a clean piece of mathematics, which is why designers can argue it has no hidden weakness. For each byte x:

  1. Treat x as an element of the finite field GF(28), where addition is XOR and multiplication is polynomial multiplication reduced by the polynomial x^8 + x^4 + x^3 + x + 1 (written 0x11B). Take its multiplicative inverse (and map 0 to 0). The inverse function is highly nonlinear.
  2. Apply a fixed affine transformation (XOR of the byte with four rotated copies of itself, then XOR with the constant 0x63), which removes the algebraic fixed points of the inverse.

The following program computes all 256 entries and checks them against three values from the AES standard.

Python Computing the real AES S-box

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Because the S-box is a permutation, SubBytes can be reversed, which decryption needs. The two last checks show the affine step doing its job: there are no fixed points (S[x] = x) and no "opposite" fixed points.

A tiny AES-like cipher

AES is too long to implement in a lesson, but its design pattern, a substitution-permutation network (SPN), fits in a few lines when we shrink everything. Our toy cipher has a 16-bit block, a 4-bit S-box (the one used by the PRESENT cipher), a fixed bit permutation, and four rounds. Each round does: XOR a round key, substitute each 4-bit nibble through the S-box, then shuffle the 16 bits. A final key XOR finishes it. Round keys come from hashing the main key.

This cipher is a teaching toy. A 16-bit block has only 65,536 values, so it can be fully tabulated and broken in a moment. Never use home-made ciphers for real data; use AES.

Python A 16-bit substitution-permutation cipher

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each round adds diffusion. After one round, flipping a bit changes only the few bits in its nibble's neighbourhood; by the fourth round the average is close to 8 of 16, the ideal "half of the bits". The permutation step sends the four bits of every nibble to four different nibbles, so the next S-box layer spreads the change even further. That cooperation of substitution (confusion) and permutation (diffusion) is exactly what AES does at a larger scale, with MixColumns in the role of the bit shuffle.

Key size and attack cost

The honest attack on AES is brute force: try keys until one decrypts. AES-128 has 2128 keys. Even a billion machines trying a billion keys per second would need billions of times the age of the universe. No practical attack on full AES is known; the best "shortcut" attacks reduce the work by only a couple of bits. Quantum computers, using Grover's algorithm, would roughly halve the key length in bits, which is why AES-256 is recommended for long-term secrecy (see the post-quantum lesson later in this tutorial).

Python How long would a brute-force search take?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice how quickly the cost explodes: a 56-bit key (the old DES) falls in a fraction of a second against such a farm, while 128 bits already needs about 1010 years even with those absurdly generous numbers. Every added bit doubles the work.

A block cipher alone only handles one block. To encrypt a real message you need a mode of operation, and the wrong choice is a famous mistake. That is the topic of the next lesson.

DES, Double DES and Triple DES

Before AES there was DES, the Data Encryption Standard, published in 1977 and based on IBM's Lucifer cipher. It is a 16-round Feistel network on 64-bit blocks with a 56-bit key (stored in 8 bytes, one bit per byte being parity). Each round expands the right half to 48 bits, mixes in a 48-bit round key, passes the result through eight S-boxes (the non-linear step, which gives DES its confusion) and then a permutation that spreads the bits (diffusion). Its design held up remarkably well against differential cryptanalysis, which the designers already knew about. Its strengths were speed in hardware, a public specification (an international standard, which made products interoperable) and decades of scrutiny without any shortcut attack.

Its weakness is the key: 256 keys became searchable. A purpose-built machine found a DES key in days in 1998, and today a cloud rental does it in hours. The 64-bit block is a second problem: after about 232 blocks (tens of gigabytes) repeated blocks become likely, which enables the Sweet32 attack on long-lived connections.

Why not just encrypt twice?

Double DES encrypts with two keys: C = E_k2(E_k1(P)). It looks like a 112-bit key, but a meet-in-the-middle attack breaks it with about 257 work. Given one known plaintext/ciphertext pair, encrypt the plaintext under every k1 and store the results; decrypt the ciphertext under every k2 and look for a match. Each side costs 256, not 2112. The program below shows the idea with a toy cipher whose key is only 12 bits, so the whole attack runs instantly.

Python Meet-in-the-middle attack on double encryption

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Triple DES

Triple DES (3DES, TDEA) applies DES three times in an encrypt-decrypt-encrypt order: C = E_k3(D_k2(E_k1(P))). With three independent keys (168 key bits) the meet-in-the-middle attack still reduces the strength to about 112 bits. The E-D-E order means that setting k1 = k2 = k3 gives ordinary single DES, so 3DES hardware stays compatible with old DES systems. It was a long-lived stopgap, widely used in payment systems (ATMs, chip cards) and financial transactions. It is slow, because it makes three passes, and its 64-bit block still has the Sweet32 problem, so NIST has retired it. New systems use AES.

DES versus AES

DES AES
Year 1977 2001
Structure Feistel network, 16 rounds Substitution-permutation network, 10/12/14 rounds
Block size 64 bits 128 bits
Key size 56 bits 128, 192 or 256 bits
Status Broken by brute force Secure, the global standard
Speed Slow in software Fast, with hardware support in CPUs

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the block size of AES-256?

    AES always uses 128-bit blocks. The key size (128, 192 or 256 bits) only changes the key space and the number of rounds (10, 12 or 14).
  2. 2. Which AES step provides the nonlinearity that protects against algebraic attacks?

    XOR with round keys and row shifts are linear. The S-box is the one nonlinear component, and it is built from the finite-field inverse for that reason.
  3. 3. In our toy cipher, what happens to the average avalanche as more rounds are added?

    A single round spreads a flipped bit only a little. Repeating substitution and permutation lets the change reach every nibble, approaching the ideal 50% of bits.
  4. 4. Why is a 64-bit block considered too small for modern use?

    By the birthday bound, collisions among 64-bit blocks become likely after around 2^32 blocks (roughly 32 GiB), which attacks like Sweet32 exploit.

Summary

  • A block cipher is a key-selected permutation of fixed-size blocks; AES uses 128-bit blocks and 128, 192 or 256-bit keys with 10, 12 or 14 rounds.
  • Each AES round combines SubBytes (confusion), ShiftRows and MixColumns (diffusion) and AddRoundKey; the S-box comes from the GF(2^8) inverse plus an affine map.
  • Repeated rounds turn small local changes into avalanche across the whole block.
  • Brute force against AES is infeasible; the real risks are in how the cipher is used.

Next: Modes of Operation: ECB, CBC, CTR, which turn a one-block cipher into one that handles real messages.