01 · Sixteen bytes

Part I · The parts

01 Sixteen bytes

Figure 1 · The fold

Sixteen bytes, as they arrive

Answer below and the fold runs.
Byte 4 — the fifth byte of the block — lands where?
2 steps · the fold as text
  1. Sixteen bytes in the order they arrive, numbered 0 to 15: 32 43 f6 a8 88 5a 30 8d 31 31 98 a2 e0 37 07 34.
  2. Folded: each line of four stands up as a column, so the cell at row r, column c holds byte r + 4c. Column 0 reads 32 43 f6 a8, top to bottom, and byte 4 is now at the top of column 1.

AES does not encrypt a message. It encrypts sixteen bytes at a time, and it always encrypts exactly sixteen of them. A byte is a number from 0 to 255, and in hexadecimal that is the two characters printed on every cell above. Files, packets, this sentence — all of that is somebody else’s problem until Chapter 12, where it becomes ours.

The sixteen bytes are written into a four-by-four square, the state, and they are written down the columns rather than across the rows. Bytes 0 to 3 fill the first column top to bottom; byte 4 starts the second. The cell at row r, column c holds byte r + 4c, and that is the one line in this chapter worth keeping. Yours are 3243f6a8 885a308d 313198a2 e0370734, and every figure in this document is computed from them.

The fold moves nothing. It is a way of reading the same sixteen bytes, and three of the four operations cannot tell the difference: SubBytes replaces each byte on its own, AddRoundKey exclusive-ors each byte with its own key byte, and MixColumns works on whichever four bytes it is handed. ShiftRows is the one that notices, because it rotates rows, and rows are the axis the two readings disagree about.

So an implementation that fills the square the other way round still runs. It produces output that looks exactly like ciphertext, disagrees with the published test vectors for any block that does not read the same down as across, and cannot be decrypted by anybody else’s AES. It is worth throwing the switch and watching how long it takes for anything to look wrong.

Loads the block row-major, which is what most wrong AES diagrams draw. Every figure from here on uses it.

That is why every cell in this document prints its flat index permanently in the corner. Ten chapters from here, in the middle of a round, it is the difference between recognising your own byte and counting cells.

The controls under the figure are the controls under every figure here. Back and Next move one step, and between them is a track with one detent per step that takes the arrow keys, Home and End. Nothing in this document moves because you scrolled: scrolling moves the essay, and the machine only ever moves because you pressed something.

Part I · The parts

02 The mask

Figure 2 · AddRoundKey

The block

Byte 0 · r0 c0

32 ⊕ 2b = 19

Sixteen bytes of message. Cyan, with a solid edge, means a byte that came from what you typed.
6 steps · the mask as text
  1. Your sixteen bytes in the state: 3243f6a8 885a308d 313198a2 e0370734. Nothing has been done to them yet.
  2. Round key 0 is sixteen bytes in the same four-by-four square as the block: 2b7e1516 28aed2a6 abf71588 09cf4f3c. It is the first sixteen bytes of your key, copied in unchanged.
  3. Byte 0 of sixteen. The block byte 32 is 00110010; the key byte 2b is 00101011. They differ at bits 4, 3 and 0 and agree everywhere else, and the masked byte has a bit set at exactly those places: 00011001, which is 19.
  4. Before round 1, step 1 of 40: adding the round key (AddRoundKey). Every byte of the state is exclusive-ored with the matching byte of the round key. The key added here is the one for round 0. All sixteen bytes changed. Byte 0 (row 0, column 0) went 32 to 19 and byte 1 (row 1, column 0) went 43 to 3d, and so on.
  5. Byte 0 of sixteen. The masked byte 19 is 00011001; the key byte 2b is 00101011. They differ at bits 5, 4 and 1 and agree everywhere else, and the block byte has a bit set at exactly those places: 00110010, which is 32.
  6. Every byte is back: 3243f6a8 885a308d 313198a2 e0370734. Adding the same round key a second time undid the first, bit for bit.

AddRoundKey adds the round key to the block, one cell at a time. Byte 0 of the state meets byte 0 of the key, byte 5 meets byte 5, and so on to byte 15. Nothing is looked up and nothing moves: the round key is the same four-by-four square as the block, so the two line up cell for cell and sixteen small sums happen at once.

The addition is exclusive-or, written ⊕. Take the two bytes a bit at a time; where the two bits differ the answer is 1, and where they agree it is 0. What matters is what is missing. Ordinary addition carries, so a 1 in the units column can travel the whole width of a byte — here it cannot, and each of the eight columns is a sealed little sum of its own. Addition without carries is addition in a field of two elements, which is why this is the one operation in AES worth drawing at bit level. Chapter 4 is where the rest of that field turns up.

A sum with no carries undoes itself. Add the same key byte a second time and every bit it flipped flips back, because k ⊕ k is zero and adding zero does nothing: a ⊕ k ⊕ k = a. Addition and subtraction are the same operation here, so there is no inverse to build and none to get wrong. Decryption’s first move is to add the last round key straight back in, and this identity is the whole reason that works.

This is also the only place the key touches the block. SubBytes, ShiftRows and MixColumns are published, fixed and identical for everybody; you could write all three on a postcard and give nothing away. Every scrap of secrecy in the cipher enters through this one exclusive-or, once before the first round and once inside every round after it. Zero the round keys and AES still runs, still shuffles, still hands back sixteen plausible-looking bytes, and protects nothing — which is worth watching rather than believing.

Leaves the rest of AES exactly as published. Every figure from here on uses it, and the verification badge is struck wherever one appears.

Which leaves the question of where those sixteen bytes came from. For now they are handed to us: round key 0 is 2b7e1516 28aed2a6 abf71588 09cf4f3c, the first sixteen bytes of your key copied in unchanged, and every round key after it is derived from that one. Chapter 9 does the derivation properly. Until then, take the round key as sixteen bytes that arrive on time.

Part I · The parts

03 The table

The key is in, and by itself AddRoundKey is not a cipher: one known block of plaintext hands the key over byte for byte. The second operation is a lookup, and it is the one part of AES that looks like it was decided rather than computed. Chapter 4 is where that turns out to be false.

Figure 3 · SubBytes, sixteen lookups

Sixteen bytes, before the table

Open the map for all 256

Byte 0 holds 19. The high nibble 1 picks the row, the low nibble 9 picks the column, and the entry there is d4. Pick any other cell to follow that one instead.
4 steps · the four steps as text
  1. Sixteen bytes as they reach the table: 193de3be a0f4e22b 9ac68d2a e9f84808. Each one is about to be replaced by the table's entry for it, on its own, whatever its neighbours hold and wherever it sits.
  2. Round 1 of 10, step 2 of 40: byte substitution (SubBytes). Every byte is replaced by its entry in the S-box, independently of where it sits. All sixteen bytes changed, as they always do: the table maps no byte to itself. Byte 0 (row 0, column 0) went 19 to d4 and byte 1 (row 1, column 0) went 3d to 27, and so on.
  3. The reverse table applied to those sixteen brings every one of them back to 193de3be a0f4e22b 9ac68d2a e9f84808. No two bytes share an entry, so nothing was lost and every lookup can be undone.
  4. Two pairs of bytes differing by 24: 19 against 3d, and be against 9a. Every other operation in AES turns one difference into one other difference, so both pairs would come out alike. Through the table the first pair differs by f3 and the second by 16.

The S-box is one fixed table of 256 bytes, the same in every implementation there has ever been. It does not depend on the key, on the round, or on where a byte sits in the square: 19 becomes d4 in the first column and in the last, in round 1 and in round 10. Note what is going in — you typed 32 as your first byte, and by the time it reaches the table AddRoundKey has already turned it into 19.

Nothing is lost in a lookup. The 256 entries are 256 different bytes — every possible byte appears exactly once — so the table can be read backwards, and that reverse table is what decryption uses. A table with one value in it twice would destroy information that no key could put back.

Everything else in AES is linear over exclusive-or. Add a round key, rotate a row, multiply a column by a fixed matrix: for all three, the difference between two blocks going in decides the difference coming out. Stack a hundred steps like that and you still have a system of linear equations, which a computer solves whatever the key is. The table is the one place where the difference going in does not decide the difference coming out, and the last step of the figure is that failure, run on your own bytes.

It is not random, although it looks it — the map above is 256 entries with no pattern visible in them, and that appearance is the whole of the misconception. Each entry is computed: the byte’s inverse in a field of 256 elements, put through one fixed bit-mixing step. Chapter 4 builds all of them and diffs the result against the published table. A random table would also be a poor thing to ship, because everybody needs the same one and nobody could say why it resisted anything.

What the table does not do is move anything. Byte 4 is still byte 4, in the same cell, related to nothing around it. That is confusion, and it is half the job; the two chapters after the deep end are about the other half.

Part I · The parts · the deep end

04 Where the table comes from

This is the deep end. Skipping it costs nothing structural — Chapter 5 picks up with the row shift and never looks back — but it leaves two questions standing that the rest of the document keeps raising: why 0x1b appears in every AES implementation ever written, and why the table in Chapter 3 holds 256 particular bytes rather than 256 arbitrary ones.

AES multiplies bytes, and not the way a processor multiplies them. It reads a byte as a polynomial whose coefficients are its bits, so the byte you typed first, 32 — which AddRoundKey has already turned into the value the two figures below run on — is a sum of powers of x. Adding two of them adds coefficients that live in GF(2), where nothing carries: addition is exclusive-or, and since a byte exclusive-ored with itself is zero, it is subtraction as well. There is no minus sign anywhere in this document. Multiplying is the interesting half.

Figure 4 · The bench

Rung 0 of 9 · doubling

0x19 = x to the 4 plus x cubed plus one

x⁸76543210
·00011001

press Next to double it

·········

·········
·········

0x01 · 0x19

in GF(2⁸)

0x19

under mod 256

0x19

Both agree — until a bit leaves the top.

  1. 19
  2. 32
  3. 64
  4. c8
  5. 8b
  6. 0d
  7. 1a
  8. 34
  9. 68
  10. d0
Doubling a byte here shifts every bit left one place. What becomes of a bit that runs off the top?
10 steps · the ladder as text
  1. Step 1 of 10. The starting byte is 0x19, your block’s first byte as it reaches SubBytes in round 1, which read as a polynomial is x⁴+x³+1. Nothing has been multiplied yet, so the field reading and the ordinary mod-256 reading are still the same number.
  2. Step 2 of 10. 0x19 doubled. Every bit shifts left one place, giving the nine-bit 0x032. Nothing left the top, so no reduction is needed and the result is 0x32, x⁵+x⁴+x. Ordinary mod-256 doubling gives the same 0x32 here.
  3. Step 3 of 10. 0x32 doubled. Every bit shifts left one place, giving the nine-bit 0x064. Nothing left the top, so no reduction is needed and the result is 0x64, x⁶+x⁵+x². Ordinary mod-256 doubling gives the same 0x64 here.
  4. Step 4 of 10. 0x64 doubled. Every bit shifts left one place, giving the nine-bit 0x0c8. Nothing left the top, so no reduction is needed and the result is 0xc8, x⁷+x⁶+x³. Ordinary mod-256 doubling gives the same 0xc8 here.
  5. Step 5 of 10. 0xc8 doubled. Every bit shifts left one place, giving the nine-bit 0x190. Bit 7 was set, so that bit lands in the x⁸ place, and a byte has no room for it: x⁸ is congruent to x⁴+x³+x+1, which is 0x1b, the low eight bits of the modulus 0x11b. Exclusive-oring it back in gives 0x8b, x⁷+x³+x+1. Ordinary mod-256 doubling gives 0x90 instead: the same shift with the overflow thrown away rather than folded back.
  6. Step 6 of 10. 0x8b doubled. Every bit shifts left one place, giving the nine-bit 0x116. Bit 7 was set, so that bit lands in the x⁸ place, and a byte has no room for it: x⁸ is congruent to x⁴+x³+x+1, which is 0x1b, the low eight bits of the modulus 0x11b. Exclusive-oring it back in gives 0x0d, x³+x²+1. Ordinary mod-256 doubling gives 0x16 instead: the same shift with the overflow thrown away rather than folded back.
  7. Step 7 of 10. 0x0d doubled. Every bit shifts left one place, giving the nine-bit 0x01a. Nothing left the top, so no reduction is needed and the result is 0x1a, x⁴+x³+x. Ordinary mod-256 doubling gives the same 0x1a here.
  8. Step 8 of 10. 0x1a doubled. Every bit shifts left one place, giving the nine-bit 0x034. Nothing left the top, so no reduction is needed and the result is 0x34, x⁵+x⁴+x². Ordinary mod-256 doubling gives the same 0x34 here.
  9. Step 9 of 10. 0x34 doubled. Every bit shifts left one place, giving the nine-bit 0x068. Nothing left the top, so no reduction is needed and the result is 0x68, x⁶+x⁵+x³. Ordinary mod-256 doubling gives the same 0x68 here.
  10. Step 10 of 10. 0x68 doubled. Every bit shifts left one place, giving the nine-bit 0x0d0. Nothing left the top, so no reduction is needed and the result is 0xd0, x⁷+x⁶+x⁴. Ordinary mod-256 doubling gives the same 0xd0 here.

Multiplying by two is a shift left, and a shift left runs a byte out of room. The bit that leaves position 7 is the x⁸ term, and a byte has no x⁸ place. So every product is reduced modulo a fixed polynomial, x⁸+x⁴+x³+x+1, which is 0x11B written nine bits wide. The reduction says x⁸ is congruent to x⁴+x³+x+1, and that is 0x1B. Nobody picked the constant: it is the modulus with the term that does not fit taken off the front.

Everything else is built out of that one doubling. Multiplying by 3 is the byte doubled and then exclusive-ored with the original. Multiplying by 0x0E, an InvMixColumns coefficient, takes three doublings — four coefficients per output byte, sixteen bytes per round, which is the honest reason decryption is slower than encryption in software. Leave the bench doubling from 0x01 and it produces 01 02 04 08 10 20 40 80 1B 36. Those are Rcon, the key expansion’s round constants in Chapter 9, generated rather than chosen.

Which brings us back to the table. Every one of its 256 entries is two lines of arithmetic on the byte that indexes it.

Figure 5 · The forge

The byte going in

  1. input

    0x19

  2. inverse

    ··

  3. affine

    ··

  4. output

    ··

your block’s byte 0, entering SubBytes

0x19

x to the 4 plus x cubed plus one

Eight bits, and every rule in this chapter follows from reading them as the coefficients of a polynomial. The + written between those terms and the ⊕ written between bytes are the same operation.

your block’s byte 0, entering SubBytes

Eight bits, read as the coefficients of a polynomial. That reading is the whole trick.
4 steps · the derivation as text
  1. Stage 1 of four. The byte going in is 0x19, your block’s byte 0, entering SubBytes. Read as a polynomial its bits are the coefficients of x⁴+x³+1.
  2. Stage 2 of four. The multiplicative inverse of 0x19 is 0x3f: the byte that multiplies with it to give 0x01 in the field. It is found by trying every non-zero byte until one does, and the check is computed on screen rather than asserted.
  3. Stage 3 of four. The inverse 0x3f goes through an eight by eight bit matrix over GF(2), written least significant bit first, and then exclusive-ored with the constant 0x63. Output bit i is the exclusive-or of input bits i, i+4, i+5, i+6 and i+7 counted modulo eight, plus bit i of the constant. The result is 0xd4.
  4. Stage 4 of four. 0x19 maps to 0xd4. That is the S-box entry, built from the field in two steps and not looked up anywhere. The same construction run over all 256 bytes reproduces the table the cipher upstairs is using.
8 steps · the affine map, one row per output bit
  1. Output bit 0 taps input bits 0, 4, 5, 6 and 7 — 1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 — which exclusive-or to 1. Bit 0 of the constant 0x63 is 1, so output bit 0 is 0.
  2. Output bit 1 taps input bits 0, 1, 5, 6 and 7 — 1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 — which exclusive-or to 1. Bit 1 of the constant 0x63 is 1, so output bit 1 is 0.
  3. Output bit 2 taps input bits 0, 1, 2, 6 and 7 — 1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 — which exclusive-or to 1. Bit 2 of the constant 0x63 is 0, so output bit 2 is 1.
  4. Output bit 3 taps input bits 0, 1, 2, 3 and 7 — 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 0 — which exclusive-or to 0. Bit 3 of the constant 0x63 is 0, so output bit 3 is 0.
  5. Output bit 4 taps input bits 0, 1, 2, 3 and 4 — 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 — which exclusive-or to 1. Bit 4 of the constant 0x63 is 0, so output bit 4 is 1.
  6. Output bit 5 taps input bits 1, 2, 3, 4 and 5 — 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 — which exclusive-or to 1. Bit 5 of the constant 0x63 is 1, so output bit 5 is 0.
  7. Output bit 6 taps input bits 2, 3, 4, 5 and 6 — 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 0 — which exclusive-or to 0. Bit 6 of the constant 0x63 is 1, so output bit 6 is 1.
  8. Output bit 7 taps input bits 3, 4, 5, 6 and 7 — 1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 — which exclusive-or to 1. Bit 7 of the constant 0x63 is 0, so output bit 7 is 1.

The multiplicative inverse is the first step and the reason the S-box resists anything. Inversion in a field is about as far from linear as a function of one byte gets: it scatters differences in a way no arrangement of shifts and exclusive-ors comes close to approximating, and differential and linear cryptanalysis — the two attacks that flattened earlier ciphers — both measure exactly that. Zero is the exception: it has no inverse, so AES maps it to itself by decision.

An inverse on its own is too tidy. Written out, x to x⁻¹ is a short algebraic expression, and short algebraic expressions are what algebraic attacks feed on. So an affine transformation follows it: eight output bits, each the exclusive-or of five input bits, plus the constant 0x63. The bare inverse has two fixed points, at 0x00 and 0x01; the affine map is what clears them, and the finished table leaves no byte mapping to itself or to its own complement. Turn the constant off and two come straight back.

Where this stops, and why. The modulus is one of thirty irreducible polynomials of degree eight over GF(2) and Rijndael took the numerically smallest; nothing here depends on which one it is. Real implementations find inverses with log and antilog tables rather than by the search above, which is a speed argument and computes the same 255 values. And GF(2¹²⁸), the field GCM’s authenticator uses in Chapter 15, is a different field with a bit-reversed convention; it is not opened here, and that chapter says so on its diagram rather than quietly leaving it out.

Part I · The parts

05 The shift

Three operations in, and nothing has spread. AddRoundKey combines each byte with one key byte. SubBytes replaces each byte using only itself. A byte in the top-left cell has been through both and has still touched nothing else, so what we have built so far is sixteen independent one-byte ciphers standing side by side. Change one byte of the plaintext and exactly one byte of the output changes. That is not a block cipher.

Figure 6 · ShiftRows, round 1

Rows at rest

Nothing has moved yet. Row 0 is fixed — ×0 in the gutter, written rather than left blank — and rows 1, 2 and 3 rotate left by one, two and three.
5 steps · the shift as text
  1. Nothing has moved yet. Row 0 is fixed — ×0 in the gutter, written rather than left blank — and rows 1, 2 and 3 rotate left by one, two and three.
  2. Row 1 rotates left by one and now reads bf b4 41 27. One byte ran off the left end and came back at the right: 27.
  3. Row 2 rotates left by two and now reads 5d 52 11 98. Two bytes ran off the left end and came back at the right: 11 98.
  4. Row 3 rotates left by three and now reads 30 ae f1 e5. Three bytes ran off the left end and came back at the right: ae f1 e5. Row 0 never moved.
  5. Column 0 now holds bytes 0, 5, 10, 15: one from each of the four original columns, and every other column the same. Those four are what MixColumns takes next.
16 moves · one line per destination cell

Round 1 of 10, step 3 of 40: row shift (ShiftRows). Row 0 stands still while rows 1, 2 and 3 rotate left by one, two and three bytes. Twelve of the sixteen cells now hold a different byte, in rows 1, 2 and 3; row 0 is untouched. Byte 1 (row 1, column 0) went 27 to bf and byte 2 (row 2, column 0) went 11 to 5d, and so on.

  1. Row 0, column 0 keeps byte 0, value d4.
  2. Row 1, column 0 takes byte 5 from column 1, value bf.
  3. Row 2, column 0 takes byte 10 from column 2, value 5d.
  4. Row 3, column 0 takes byte 15 from column 3, value 30.
  5. Row 0, column 1 keeps byte 4, value e0.
  6. Row 1, column 1 takes byte 9 from column 2, value b4.
  7. Row 2, column 1 takes byte 14 from column 3, value 52.
  8. Row 3, column 1 takes byte 3 from column 0, value ae, which came round the end.
  9. Row 0, column 2 keeps byte 8, value b8.
  10. Row 1, column 2 takes byte 13 from column 3, value 41.
  11. Row 2, column 2 takes byte 2 from column 0, value 11, which came round the end.
  12. Row 3, column 2 takes byte 7 from column 1, value f1, which came round the end.
  13. Row 0, column 3 keeps byte 12, value 1e.
  14. Row 1, column 3 takes byte 1 from column 0, value 27, which came round the end.
  15. Row 2, column 3 takes byte 6 from column 1, value 98, which came round the end.
  16. Row 3, column 3 takes byte 11 from column 2, value e5, which came round the end.

ShiftRows is the cheapest possible answer and it is barely an operation at all. Row 0 is left alone. Row 1 rotates one place to the left, row 2 two places, row 3 three. No byte changes value: whatever a cell held before the shift, some cell holds afterwards. It is the only step in AES that moves bytes without touching them, and the gutter prints ×0 beside row 0 so that the row which does nothing reads as a decision rather than as an omission.

It works on rows because the block was folded into columns. A row holds one byte from each of the four columns — row 1 is bytes 1, 5, 9 and 13 — so rotating the rows by different amounts is the cheapest way to make every new column draw from every old one. Rotate all four rows by one place and you have merely renamed the columns. Rotate them by nought, one, two and three and column 0 ends up holding bytes 0, 5, 10 and 15: four bytes that were four columns apart. Turn on the array view and the same move reads as the gather 0, 5, 10, 15, 4, 9, 14, 3, and so on, which is the identical fact and looks nothing like it.

On its own, though, this still spreads nothing. Every byte holds the value it held a moment ago; all that has changed is which cell it sits in. Run SubBytes, ShiftRows and AddRoundKey ten times over and you would have sixteen independent one-byte ciphers with their bytes shuffled between rounds — better disguised, no more mixed. What the shift has done is put four unrelated bytes side by side in a column, and the next chapter is the operation that makes something of them.

Part I · The parts

06 The mix

The shift put four unrelated bytes side by side in a column and changed none of them. MixColumns is the step that makes one byte out of four.

Figure 7 · MixColumns, one column

Column 0 · in focus

d4your byte
Column 0 on its own: d4 bf 5d 30. MixColumns works down a column and never across one, so the other three are set aside while this one is mixed.
20 steps · every column, step by step
  1. Column 0 on its own: d4 bf 5d 30. MixColumns works down a column and never across one, so the other three are set aside while this one is mixed.
  2. Output row 0: 02 · d4 = b3, 03 · bf = da, 01 · 5d = 5d, 01 · 30 = 30. Exclusive-or the four products and byte 0 becomes 04.
  3. Output row 1: 01 · d4 = d4, 02 · bf = 65, 03 · 5d = e7, 01 · 30 = 30. Exclusive-or the four products and byte 1 becomes 66.
  4. Output row 2: 01 · d4 = d4, 01 · bf = bf, 02 · 5d = ba, 03 · 30 = 50. Exclusive-or the four products and byte 2 becomes 81.
  5. Output row 3: 03 · d4 = 67, 01 · bf = bf, 01 · 5d = 5d, 02 · 30 = 60. Exclusive-or the four products and byte 3 becomes e5. The column is now 04 66 81 e5.
  6. Column 1 on its own: e0 b4 52 ae. MixColumns works down a column and never across one, so the other three are set aside while this one is mixed.
  7. Output row 0: 02 · e0 = db, 03 · b4 = c7, 01 · 52 = 52, 01 · ae = ae. Exclusive-or the four products and byte 4 becomes e0.
  8. Output row 1: 01 · e0 = e0, 02 · b4 = 73, 03 · 52 = f6, 01 · ae = ae. Exclusive-or the four products and byte 5 becomes cb.
  9. Output row 2: 01 · e0 = e0, 01 · b4 = b4, 02 · 52 = a4, 03 · ae = e9. Exclusive-or the four products and byte 6 becomes 19.
  10. Output row 3: 03 · e0 = 3b, 01 · b4 = b4, 01 · 52 = 52, 02 · ae = 47. Exclusive-or the four products and byte 7 becomes 9a. The column is now e0 cb 19 9a.
  11. Column 2 on its own: b8 41 11 f1. MixColumns works down a column and never across one, so the other three are set aside while this one is mixed.
  12. Output row 0: 02 · b8 = 6b, 03 · 41 = c3, 01 · 11 = 11, 01 · f1 = f1. Exclusive-or the four products and byte 8 becomes 48.
  13. Output row 1: 01 · b8 = b8, 02 · 41 = 82, 03 · 11 = 33, 01 · f1 = f1. Exclusive-or the four products and byte 9 becomes f8.
  14. Output row 2: 01 · b8 = b8, 01 · 41 = 41, 02 · 11 = 22, 03 · f1 = 08. Exclusive-or the four products and byte 10 becomes d3.
  15. Output row 3: 03 · b8 = d3, 01 · 41 = 41, 01 · 11 = 11, 02 · f1 = f9. Exclusive-or the four products and byte 11 becomes 7a. The column is now 48 f8 d3 7a.
  16. Column 3 on its own: 1e 27 98 e5. MixColumns works down a column and never across one, so the other three are set aside while this one is mixed.
  17. Output row 0: 02 · 1e = 3c, 03 · 27 = 69, 01 · 98 = 98, 01 · e5 = e5. Exclusive-or the four products and byte 12 becomes 28.
  18. Output row 1: 01 · 1e = 1e, 02 · 27 = 4e, 03 · 98 = b3, 01 · e5 = e5. Exclusive-or the four products and byte 13 becomes 06.
  19. Output row 2: 01 · 1e = 1e, 01 · 27 = 27, 02 · 98 = 2b, 03 · e5 = 34. Exclusive-or the four products and byte 14 becomes 26.
  20. Output row 3: 03 · 1e = 22, 01 · 27 = 27, 01 · 98 = 98, 02 · e5 = d1. Exclusive-or the four products and byte 15 becomes 4c. The column is now 28 06 26 4c.
4 output bytes · every product in this column

Round 1 of 10, step 4 of 40: column mixing (MixColumns). Each column is multiplied by a fixed matrix in the byte field, so every byte of the new column depends on all four bytes of the old one. Fifteen of the sixteen cells now hold a different byte. Byte 0 (row 0, column 0) went d4 to 04 and byte 1 (row 1, column 0) went bf to 66, and so on.

  1. Byte 0 = 02·d4 ⊕ 03·bf ⊕ 01·5d ⊕ 01·30 = b3 ⊕ da ⊕ 5d ⊕ 30 = 04.
  2. Byte 1 = 01·d4 ⊕ 02·bf ⊕ 03·5d ⊕ 01·30 = d4 ⊕ 65 ⊕ e7 ⊕ 30 = 66.
  3. Byte 2 = 01·d4 ⊕ 01·bf ⊕ 02·5d ⊕ 03·30 = d4 ⊕ bf ⊕ ba ⊕ 50 = 81.
  4. Byte 3 = 03·d4 ⊕ 01·bf ⊕ 01·5d ⊕ 02·30 = 67 ⊕ bf ⊕ 5d ⊕ 60 = e5.

A column is four bytes, and MixColumns replaces it with four new ones. Each new byte is built from all four of the old: multiply every one of them by a fixed coefficient and add the four results together. The multiplication is Chapter 4’s — the GF(2⁸), where 02 is a doubling that folds back when it overflows — and addition is exclusive-or, as it is everywhere in this cipher. Set out as a matrix the coefficients are 02, 03, 01, 01, and each row is the row above it moved one place along, which is why the same four numbers walk down the picture.

They are small on purpose. 01 is a copy, 02 is one doubling, 03 is a doubling exclusive-ored with the byte itself, so a whole column costs a handful of shifts and XORs and not one table lookup. Small is not the same as weak. None of the sixteen is zero, so every input byte reaches every output byte: nudge one of the four inputs with the stepper and all four answers move, every time, whatever the value. Counting both ends, changing one input byte changes at least five of the eight bytes involved. That is the matrix’s branch number, and five is the most a four-byte map can have.

And MixColumns on its own spreads nothing either. It never reaches outside its own column, so a cipher of SubBytes, MixColumns and AddRoundKey would be four independent 32-bit ciphers sharing a square, and a change in byte 0 would never once reach byte 4. Neither operation diffuses. The alternation does: MixColumns takes one byte to four within a column, the shift scatters those four into four different columns, and the next MixColumns takes each of them to four more. One byte reaches all sixteen in two rounds. That is a claim, and the next chapter is where we turn the shift off and watch it fail.

Part I · The parts

07 Why both

Chapters 5 and 6 ended with the same admission. The shift moves bytes between columns and changes none of them; the mix changes bytes and never leaves its column. Neither spreads anything on its own. Put them one after the other and, the claim goes, one flipped bit reaches all sixteen bytes within two rounds. That is a claim about a mechanism, and the way to test a mechanism is to take half of it away.

So: your sixteen bytes, and the same sixteen with a single bit turned over. Run both pairs through all 10 rounds — once through AES exactly as published, once through a machine identical in every respect except that ShiftRows has been deleted — and count, round by round, how many bytes of each column have come out different.

Figure 8 · One bit, every round, with and without the shift

Key addition · one bit flipped in column 1

flip in
The key addition before round 1. Bit 0 of byte 4 is flipped: row 0, column 1. Both machines are still doing the same thing: the difference is in column 1 alone — 0, 1, 0 and 0 bytes, 1 of 128 bits.
11 steps · every round as text
  1. The key addition before round 1. Bit 0 of byte 4 is flipped: row 0, column 1. Both machines are still doing the same thing: the difference is in column 1 alone — 0, 1, 0 and 0 bytes, 1 of 128 bits.
  2. Round 1 of 10. Both machines are still doing the same thing: the difference is in column 1 alone — 0, 4, 0 and 0 bytes, 20 of 128 bits.
  3. Round 2 of 10. AES as published: in all four columns — 4, 4, 4 and 4 bytes, 53 of 128 bits. With ShiftRows deleted: in column 1 alone — 0, 4, 0 and 0 bytes, 16 of 128 bits. Columns 0, 2 and 3 are untouched.
  4. Round 3 of 10. AES as published: in all four columns — 4, 4, 4 and 4 bytes, 63 of 128 bits. With ShiftRows deleted: in column 1 alone — 0, 4, 0 and 0 bytes, 21 of 128 bits. Columns 0, 2 and 3 are untouched.
  5. Round 4 of 10. AES as published: in all four columns — 4, 4, 4 and 4 bytes, 60 of 128 bits. With ShiftRows deleted: in column 1 alone — 0, 4, 0 and 0 bytes, 11 of 128 bits. Columns 0, 2 and 3 are untouched.
  6. Round 5 of 10. AES as published: in all four columns — 4, 4, 4 and 4 bytes, 62 of 128 bits. With ShiftRows deleted: in column 1 alone — 0, 4, 0 and 0 bytes, 17 of 128 bits. Columns 0, 2 and 3 are untouched.
  7. Round 6 of 10. AES as published: in all four columns — 4, 4, 4 and 4 bytes, 65 of 128 bits. With ShiftRows deleted: in column 1 alone — 0, 4, 0 and 0 bytes, 15 of 128 bits. Columns 0, 2 and 3 are untouched.
  8. Round 7 of 10. AES as published: in all four columns — 4, 4, 4 and 4 bytes, 59 of 128 bits. With ShiftRows deleted: in column 1 alone — 0, 4, 0 and 0 bytes, 16 of 128 bits. Columns 0, 2 and 3 are untouched.
  9. Round 8 of 10. AES as published: in all four columns — 4, 4, 4 and 4 bytes, 62 of 128 bits. With ShiftRows deleted: in column 1 alone — 0, 4, 0 and 0 bytes, 16 of 128 bits. Columns 0, 2 and 3 are untouched.
  10. Round 9 of 10. AES as published: in all four columns — 4, 4, 4 and 4 bytes, 58 of 128 bits. With ShiftRows deleted: in column 1 alone — 0, 4, 0 and 0 bytes, 12 of 128 bits. Columns 0, 2 and 3 are untouched.
  11. Round 10 of 10. AES as published: in all four columns — 4, 4, 4 and 4 bytes, 62 of 128 bits. With ShiftRows deleted: in column 1 alone — 0, 4, 0 and 0 bytes, 15 of 128 bits. Columns 0, 2 and 3 are untouched.

On the left the difference does what the design intends. One bit becomes one byte, the mix takes that byte to four inside its column, the shift scatters those four into four different columns, and by the end of round 2 every column is carrying part of it. On the right it never leaves. One lane stays lit for all 10 rounds and the other three read ·· the whole way down — not nearly identical, identical, byte for byte, after 10 rounds of substitution, mixing and key addition.

The consequence is worth saying plainly. Without the shift, AES is not a 128-bit cipher with a weakness in it. It is four independent 32-bit ciphers that happen to share a square and a key schedule: each column is enciphered by its own lookups, its own matrix and its own quarter of every round key, and nothing that happens in one of them is observable in any other. A 32-bit block is not a block size anybody would ship — the entire codebook fits in a table.

So the mix is the operation with reach and no travel, the shift is the operation with travel and no reach, and diffusion belongs to neither of them. It belongs to the alternation, and it needs both.

Everything up to here you have had to take on trust once: that these figures show AES and not a convenient simplification of it. The switches below are how you check. Each one removes a real piece of the cipher and the whole document recomputes around it — every figure, every value in every sentence, the sixteen bytes at the foot of this paragraph. The arithmetic stays exactly as published; only the machine changes. While any switch is thrown a NOT AES chip rides on every figure and the verification badge is struck through, because a broken cipher that still looked trustworthy would be worse than no demonstration at all.

The lab

Break it, and the document breaks with it

Off, nothing in the cipher moves a byte between columns, and the block becomes four 32-bit ciphers that never meet.
Off, nothing combines one byte with another, and a difference stays exactly one byte wide however long you run it.
How the block is loaded

The block folds in down the columns, so byte 4 is the top of column 1 — the convention the standard uses.

Rounds
10standard

Fewer rounds is this cipher stopped early, which is how you watch structure survive all the way into the ciphertext.

The key schedule

The expansion exactly as published: one round key per round, all of them derived from your key.

On, the first and last round keys go through InvMixColumns along with the rest, which they must not: encryption is untouched and the rearranged decryption stops recovering the plaintext.

Your block, through the machine as it now stands: 3925841d 02dc09fb dc118597 196a0b32.

All four operations are now on the table, each with the reason it is there: a mask that puts the key in, a table that makes the whole thing nonlinear, a shift that travels and a mix that reaches. What is left is the order they go in, how many times round they go, and why the last round is one step short. That is the next chapter.

Part II · The machine

08 The round, ten times

Four operations, learnt one at a time. A round is all four of them, in one fixed order, applied to the whole block: substitute every byte, shift the rows, mix the columns, add the round key. That is the entire machine. Everything left in this chapter is arithmetic about how many times it runs and what happens at the ends.

Figure 9 · One round, five states

Round 1 of 10

in
out

in193de3be a0f4e22b 9ac68d2a e9f84808

outd42711ae e0bf98f1 b8b45de5 1e415230

The last round runs one operation fewer than the others. Which one is missing?
4 steps · this round, step by step
  1. Round 1 of 10, step 2 of 40: byte substitution (SubBytes). Every byte is replaced by its entry in the S-box, independently of where it sits. All sixteen bytes changed, as they always do: the table maps no byte to itself. Byte 0 (row 0, column 0) went 19 to d4 and byte 1 (row 1, column 0) went 3d to 27, and so on.
  2. Round 1 of 10, step 3 of 40: row shift (ShiftRows). Row 0 stands still while rows 1, 2 and 3 rotate left by one, two and three bytes. Twelve of the sixteen cells now hold a different byte, in rows 1, 2 and 3; row 0 is untouched. Byte 1 (row 1, column 0) went 27 to bf and byte 2 (row 2, column 0) went 11 to 5d, and so on.
  3. Round 1 of 10, step 4 of 40: column mixing (MixColumns). Each column is multiplied by a fixed matrix in the byte field, so every byte of the new column depends on all four bytes of the old one. Fifteen of the sixteen cells now hold a different byte. Byte 0 (row 0, column 0) went d4 to 04 and byte 1 (row 1, column 0) went bf to 66, and so on.
  4. Round 1 of 10, step 5 of 40: adding the round key (AddRoundKey). Every byte of the state is exclusive-ored with the matching byte of the round key. The key added here is the one for round 1. All sixteen bytes changed. Byte 0 (row 0, column 0) went 04 to a4 and byte 1 (row 1, column 0) went 66 to 9c, and so on.
5 states · every plate in this round
  1. going in 193de3be a0f4e22b 9ac68d2a e9f84808
  2. after SubBytes d42711ae e0bf98f1 b8b45de5 1e415230
  3. after ShiftRows d4bf5d30 e0b452ae b84111f1 1e2798e5
  4. after MixColumns 046681e5 e0cb199a 48f8d37a 2806264c
  5. after AddRoundKey a49c7ff2 689f352b 6b5bea43 026a5049

The order is not arbitrary and none of it is decoration. SubBytes is the only step that is not linear, so it has to be there or the whole cipher would collapse into one big matrix that anyone could invert. ShiftRows moves bytes between columns and changes none of them; MixColumns changes bytes and never leaves its column. Neither spreads a difference on its own, and alternating them does — that was Chapter 6’s claim and Chapter 7’s experiment. AddRoundKey comes last, so every round ends on sixteen bytes the attacker cannot predict.

One round is nothing: a single change to the plaintext would reach four bytes and stop. AES-128 runs 10 of them. Before the first there is a lone key addition — the initial round key addition — because without it the opening SubBytes and ShiftRows would not depend on the key at all, and anyone could simply run them backwards. 10 rounds of four operations, less one, plus that first addition, is 40 steps, and every one of them is a tick on the strip below.

The last round has no MixColumns, and the reason is worth having exactly right. The mix is linear and entirely public. Put one in the final round and it lands directly before the last key addition, so anybody holding the ciphertext can undo it: what comes back is the state before the mix, exclusive-ored with the round key run through the same inverse. That is just a different unknown sixteen bytes, and an attacker who did not know the round key does not know that one either. So the mix would buy nothing while costing the most expensive operation in the cipher, once per block, in both directions. It is left out, and the gap it leaves is drawn above and counted below.

Figure 10 · The whole encryption, 40 ticks

Before round 1 · AddRoundKey

key size

AES-128 runs 10 rounds over 40 ticks.

40 steps · every step as text
  1. Before round 1, step 1 of 40: adding the round key (AddRoundKey). Every byte of the state is exclusive-ored with the matching byte of the round key. The key added here is the one for round 0. All sixteen bytes changed. Byte 0 (row 0, column 0) went 32 to 19 and byte 1 (row 1, column 0) went 43 to 3d, and so on.
  2. Round 1 of 10, step 2 of 40: byte substitution (SubBytes). Every byte is replaced by its entry in the S-box, independently of where it sits. All sixteen bytes changed, as they always do: the table maps no byte to itself. Byte 0 (row 0, column 0) went 19 to d4 and byte 1 (row 1, column 0) went 3d to 27, and so on.
  3. Round 1 of 10, step 3 of 40: row shift (ShiftRows). Row 0 stands still while rows 1, 2 and 3 rotate left by one, two and three bytes. Twelve of the sixteen cells now hold a different byte, in rows 1, 2 and 3; row 0 is untouched. Byte 1 (row 1, column 0) went 27 to bf and byte 2 (row 2, column 0) went 11 to 5d, and so on.
  4. Round 1 of 10, step 4 of 40: column mixing (MixColumns). Each column is multiplied by a fixed matrix in the byte field, so every byte of the new column depends on all four bytes of the old one. Fifteen of the sixteen cells now hold a different byte. Byte 0 (row 0, column 0) went d4 to 04 and byte 1 (row 1, column 0) went bf to 66, and so on.
  5. Round 1 of 10, step 5 of 40: adding the round key (AddRoundKey). Every byte of the state is exclusive-ored with the matching byte of the round key. The key added here is the one for round 1. All sixteen bytes changed. Byte 0 (row 0, column 0) went 04 to a4 and byte 1 (row 1, column 0) went 66 to 9c, and so on.
  6. Round 2 of 10, step 6 of 40: byte substitution (SubBytes). Every byte is replaced by its entry in the S-box, independently of where it sits. All sixteen bytes changed, as they always do: the table maps no byte to itself. Byte 0 (row 0, column 0) went a4 to 49 and byte 1 (row 1, column 0) went 9c to de, and so on.
  7. Round 2 of 10, step 7 of 40: row shift (ShiftRows). Row 0 stands still while rows 1, 2 and 3 rotate left by one, two and three bytes. Twelve of the sixteen cells now hold a different byte, in rows 1, 2 and 3; row 0 is untouched. Byte 1 (row 1, column 0) went de to db and byte 2 (row 2, column 0) went d2 to 87, and so on.
  8. Round 2 of 10, step 8 of 40: column mixing (MixColumns). Each column is multiplied by a fixed matrix in the byte field, so every byte of the new column depends on all four bytes of the old one. All sixteen cells now hold a different byte. Byte 0 (row 0, column 0) went 49 to 58 and byte 1 (row 1, column 0) went db to 4d, and so on.
  9. Round 2 of 10, step 9 of 40: adding the round key (AddRoundKey). Every byte of the state is exclusive-ored with the matching byte of the round key. The key added here is the one for round 2. All sixteen bytes changed. Byte 0 (row 0, column 0) went 58 to aa and byte 1 (row 1, column 0) went 4d to 8f, and so on.
  10. Round 3 of 10, step 10 of 40: byte substitution (SubBytes). Every byte is replaced by its entry in the S-box, independently of where it sits. All sixteen bytes changed, as they always do: the table maps no byte to itself. Byte 0 (row 0, column 0) went aa to ac and byte 1 (row 1, column 0) went 8f to 73, and so on.
  11. Round 3 of 10, step 11 of 40: row shift (ShiftRows). Row 0 stands still while rows 1, 2 and 3 rotate left by one, two and three bytes. Twelve of the sixteen cells now hold a different byte, in rows 1, 2 and 3; row 0 is untouched. Byte 1 (row 1, column 0) went 73 to c1 and byte 2 (row 2, column 0) went cf to d6, and so on.
  12. Round 3 of 10, step 12 of 40: column mixing (MixColumns). Each column is multiplied by a fixed matrix in the byte field, so every byte of the new column depends on all four bytes of the old one. Fifteen of the sixteen cells now hold a different byte. Byte 0 (row 0, column 0) went ac to 75 and byte 1 (row 1, column 0) went c1 to ec, and so on.
  13. Round 3 of 10, step 13 of 40: adding the round key (AddRoundKey). Every byte of the state is exclusive-ored with the matching byte of the round key. The key added here is the one for round 3. All sixteen bytes changed. Byte 0 (row 0, column 0) went 75 to 48 and byte 1 (row 1, column 0) went ec to 6c, and so on.
  14. Round 4 of 10, step 14 of 40: byte substitution (SubBytes). Every byte is replaced by its entry in the S-box, independently of where it sits. All sixteen bytes changed, as they always do: the table maps no byte to itself. Byte 0 (row 0, column 0) went 48 to 52 and byte 1 (row 1, column 0) went 6c to 50, and so on.
  15. Round 4 of 10, step 15 of 40: row shift (ShiftRows). Row 0 stands still while rows 1, 2 and 3 rotate left by one, two and three bytes. Twelve of the sixteen cells now hold a different byte, in rows 1, 2 and 3; row 0 is untouched. Byte 1 (row 1, column 0) went 50 to a4 and byte 2 (row 2, column 0) went 2f to c8, and so on.
  16. Round 4 of 10, step 16 of 40: column mixing (MixColumns). Each column is multiplied by a fixed matrix in the byte field, so every byte of the new column depends on all four bytes of the old one. All sixteen cells now hold a different byte. Byte 0 (row 0, column 0) went 52 to 0f and byte 1 (row 1, column 0) went a4 to d6, and so on.
  17. Round 4 of 10, step 17 of 40: adding the round key (AddRoundKey). Every byte of the state is exclusive-ored with the matching byte of the round key. The key added here is the one for round 4. Fifteen of the sixteen bytes changed; a byte is left alone wherever its key byte is zero. Byte 0 (row 0, column 0) went 0f to e0 and byte 1 (row 1, column 0) went d6 to 92, and so on.
  18. Round 5 of 10, step 18 of 40: byte substitution (SubBytes). Every byte is replaced by its entry in the S-box, independently of where it sits. All sixteen bytes changed, as they always do: the table maps no byte to itself. Byte 0 (row 0, column 0) went e0 to e1 and byte 1 (row 1, column 0) went 92 to 4f, and so on.
  19. Round 5 of 10, step 19 of 40: row shift (ShiftRows). Row 0 stands still while rows 1, 2 and 3 rotate left by one, two and three bytes. Twelve of the sixteen cells now hold a different byte, in rows 1, 2 and 3; row 0 is untouched. Byte 1 (row 1, column 0) went 4f to fb and byte 2 (row 2, column 0) went d2 to 96, and so on.
  20. Round 5 of 10, step 20 of 40: column mixing (MixColumns). Each column is multiplied by a fixed matrix in the byte field, so every byte of the new column depends on all four bytes of the old one. All sixteen cells now hold a different byte. Byte 0 (row 0, column 0) went e1 to 25 and byte 1 (row 1, column 0) went fb to d1, and so on.
  21. Round 5 of 10, step 21 of 40: adding the round key (AddRoundKey). Every byte of the state is exclusive-ored with the matching byte of the round key. The key added here is the one for round 5. All sixteen bytes changed. Byte 0 (row 0, column 0) went 25 to f1 and byte 1 (row 1, column 0) went d1 to 00, and so on.
  22. Round 6 of 10, step 22 of 40: byte substitution (SubBytes). Every byte is replaced by its entry in the S-box, independently of where it sits. All sixteen bytes changed, as they always do: the table maps no byte to itself. Byte 0 (row 0, column 0) went f1 to a1 and byte 1 (row 1, column 0) went 00 to 63, and so on.
  23. Round 6 of 10, step 23 of 40: row shift (ShiftRows). Row 0 stands still while rows 1, 2 and 3 rotate left by one, two and three bytes. Twelve of the sixteen cells now hold a different byte, in rows 1, 2 and 3; row 0 is untouched. Byte 1 (row 1, column 0) went 63 to 4f and byte 2 (row 2, column 0) went a8 to 3d, and so on.
  24. Round 6 of 10, step 24 of 40: column mixing (MixColumns). Each column is multiplied by a fixed matrix in the byte field, so every byte of the new column depends on all four bytes of the old one. All sixteen cells now hold a different byte. Byte 0 (row 0, column 0) went a1 to 4b and byte 1 (row 1, column 0) went 4f to 86, and so on.
  25. Round 6 of 10, step 25 of 40: adding the round key (AddRoundKey). Every byte of the state is exclusive-ored with the matching byte of the round key. The key added here is the one for round 6. Fifteen of the sixteen bytes changed; a byte is left alone wherever its key byte is zero. Byte 0 (row 0, column 0) went 4b to 26 and byte 1 (row 1, column 0) went 86 to 0e, and so on.
  26. Round 7 of 10, step 26 of 40: byte substitution (SubBytes). Every byte is replaced by its entry in the S-box, independently of where it sits. All sixteen bytes changed, as they always do: the table maps no byte to itself. Byte 0 (row 0, column 0) went 26 to f7 and byte 1 (row 1, column 0) went 0e to ab, and so on.
  27. Round 7 of 10, step 27 of 40: row shift (ShiftRows). Row 0 stands still while rows 1, 2 and 3 rotate left by one, two and three bytes. Twelve of the sixteen cells now hold a different byte, in rows 1, 2 and 3; row 0 is untouched. Byte 1 (row 1, column 0) went ab to 83 and byte 2 (row 2, column 0) went 31 to 40, and so on.
  28. Round 7 of 10, step 28 of 40: column mixing (MixColumns). Each column is multiplied by a fixed matrix in the byte field, so every byte of the new column depends on all four bytes of the old one. All sixteen cells now hold a different byte. Byte 0 (row 0, column 0) went f7 to 14 and byte 1 (row 1, column 0) went 83 to 15, and so on.
  29. Round 7 of 10, step 29 of 40: adding the round key (AddRoundKey). Every byte of the state is exclusive-ored with the matching byte of the round key. The key added here is the one for round 7. All sixteen bytes changed. Byte 0 (row 0, column 0) went 14 to 5a and byte 1 (row 1, column 0) went 15 to 41, and so on.
  30. Round 8 of 10, step 30 of 40: byte substitution (SubBytes). Every byte is replaced by its entry in the S-box, independently of where it sits. All sixteen bytes changed, as they always do: the table maps no byte to itself. Byte 0 (row 0, column 0) went 5a to be and byte 1 (row 1, column 0) went 41 to 83, and so on.
  31. Round 8 of 10, step 31 of 40: row shift (ShiftRows). Row 0 stands still while rows 1, 2 and 3 rotate left by one, two and three bytes. Twelve of the sixteen cells now hold a different byte, in rows 1, 2 and 3; row 0 is untouched. Byte 1 (row 1, column 0) went 83 to 3b and byte 2 (row 2, column 0) went 2c to d4, and so on.
  32. Round 8 of 10, step 32 of 40: column mixing (MixColumns). Each column is multiplied by a fixed matrix in the byte field, so every byte of the new column depends on all four bytes of the old one. All sixteen cells now hold a different byte. Byte 0 (row 0, column 0) went be to 00 and byte 1 (row 1, column 0) went 3b to 51, and so on.
  33. Round 8 of 10, step 33 of 40: adding the round key (AddRoundKey). Every byte of the state is exclusive-ored with the matching byte of the round key. The key added here is the one for round 8. All sixteen bytes changed. Byte 0 (row 0, column 0) went 00 to ea and byte 1 (row 1, column 0) went 51 to 83, and so on.
  34. Round 9 of 10, step 34 of 40: byte substitution (SubBytes). Every byte is replaced by its entry in the S-box, independently of where it sits. All sixteen bytes changed, as they always do: the table maps no byte to itself. Byte 0 (row 0, column 0) went ea to 87 and byte 1 (row 1, column 0) went 83 to ec, and so on.
  35. Round 9 of 10, step 35 of 40: row shift (ShiftRows). Row 0 stands still while rows 1, 2 and 3 rotate left by one, two and three bytes. Twelve of the sixteen cells now hold a different byte, in rows 1, 2 and 3; row 0 is untouched. Byte 1 (row 1, column 0) went ec to 6e and byte 2 (row 2, column 0) went 4a to 46, and so on.
  36. Round 9 of 10, step 36 of 40: column mixing (MixColumns). Each column is multiplied by a fixed matrix in the byte field, so every byte of the new column depends on all four bytes of the old one. All sixteen cells now hold a different byte. Byte 0 (row 0, column 0) went 87 to 47 and byte 1 (row 1, column 0) went 6e to 37, and so on.
  37. Round 9 of 10, step 37 of 40: adding the round key (AddRoundKey). Every byte of the state is exclusive-ored with the matching byte of the round key. The key added here is the one for round 9. Fifteen of the sixteen bytes changed; a byte is left alone wherever its key byte is zero. Byte 0 (row 0, column 0) went 47 to eb and byte 1 (row 1, column 0) went 37 to 40, and so on.
  38. Round 10 of 10, the final round, step 38 of 40: byte substitution (SubBytes). Every byte is replaced by its entry in the S-box, independently of where it sits. All sixteen bytes changed, as they always do: the table maps no byte to itself. Byte 0 (row 0, column 0) went eb to e9 and byte 1 (row 1, column 0) went 40 to 09, and so on.
  39. Round 10 of 10, the final round, step 39 of 40: row shift (ShiftRows). Row 0 stands still while rows 1, 2 and 3 rotate left by one, two and three bytes. Twelve of the sixteen cells now hold a different byte, in rows 1, 2 and 3; row 0 is untouched. Byte 1 (row 1, column 0) went 09 to 31 and byte 2 (row 2, column 0) went 89 to 7d, and so on.
  40. Round 10 of 10, the final round, step 40 of 40: adding the round key (AddRoundKey). Every byte of the state is exclusive-ored with the matching byte of the round key. The key added here is the one for round 10. All sixteen bytes changed. Byte 0 (row 0, column 0) went e9 to 39 and byte 1 (row 1, column 0) went 31 to 25, and so on.

Change the key size and the strip grows at the tail. AES-192 adds two rounds and AES-256 adds four; not one thing about the round itself changes, and the last one is still a tick short. Then the state unfolds back into sixteen bytes in the order it was folded, and those bytes are the ciphertext. Two other parties are asked whether they agree with them.

Two answers to the same question

AES-128 · 40 steps

Asking the browser

this article’s enginecomputed here

3925841d 02dc09fb dc118597 196a0b32

the published answermatches

3925841d 02dc09fb dc118597 196a0b32

FIPS 197 (upd1, 2023), Appendix B

the browser’s own AESstill running

Asking crypto.subtle…

One thing has been taken on trust since Chapter 2. The round keys arrived from somewhere — one for every round and one more before the first, 11 in all — and this chapter has used every one of them without saying where they came from. That is the next chapter, and it is the last piece of AES that is still a promise.

Part II · The machine

09 Where the round keys came from

AES-128 has 10 rounds and 11 round keys — one for every round and one more before the first — and you typed 16 bytes. The key expansion is where the other 160 come from. It is half of AES by weight — 44 words of derivation against 40 steps of cipher — and the half that gets left as a table at the back.

Figure 11 · The key expansion, word by word

w4 · rk1 c0 · the G-box fires

The two combs are one pattern: a round key and an Nk group are the same four words.

Rcon · indexed by i / Nk

w4 takes rc1 = 01 · rk1 c0

w4 fires the G-box: w3 is rotated one byte left, all four bytes go through the S-box, and rc1 = 01 is added to byte 0. Then exclusive-or w0.
44 steps · every word of the AES-128 expansion
  1. Word 0 is column 0 of round key 0, taken straight from the cipher key: 2b7e1516. The first 4 words are the key itself, copied in unchanged.
  2. Word 1 is column 1 of round key 0, taken straight from the cipher key: 28aed2a6. The first 4 words are the key itself, copied in unchanged.
  3. Word 2 is column 2 of round key 0, taken straight from the cipher key: abf71588. The first 4 words are the key itself, copied in unchanged.
  4. Word 3 is column 3 of round key 0, taken straight from the cipher key: 09cf4f3c. The first 4 words are the key itself, copied in unchanged.
  5. Word 4 is column 0 of round key 1, and it is the one that does the work. w3 (09cf4f3c) is rotated left by one byte to cf4f3c09, put through the S-box to 8a84eb01, then exclusive-ored with round constant 01 in its first byte, giving 8b84eb01. That is exclusive-ored with w0 (2b7e1516) to give a0fafe17. The constant is chosen by step of the expansion — this is step 1 — and never by round number, which is the mistake that still passes every AES-128 test and then fails at 192.
  6. Word 5 is column 1 of round key 1. It is w4 (a0fafe17) exclusive-ored with w1 (28aed2a6), giving 88542cb1.
  7. Word 6 is column 2 of round key 1. It is w5 (88542cb1) exclusive-ored with w2 (abf71588), giving 23a33939.
  8. Word 7 is column 3 of round key 1. It is w6 (23a33939) exclusive-ored with w3 (09cf4f3c), giving 2a6c7605.
  9. Word 8 is column 0 of round key 2, and it is the one that does the work. w7 (2a6c7605) is rotated left by one byte to 6c76052a, put through the S-box to 50386be5, then exclusive-ored with round constant 02 in its first byte, giving 52386be5. That is exclusive-ored with w4 (a0fafe17) to give f2c295f2. The constant is chosen by step of the expansion — this is step 2 — and never by round number, which is the mistake that still passes every AES-128 test and then fails at 192.
  10. Word 9 is column 1 of round key 2. It is w8 (f2c295f2) exclusive-ored with w5 (88542cb1), giving 7a96b943.
  11. Word 10 is column 2 of round key 2. It is w9 (7a96b943) exclusive-ored with w6 (23a33939), giving 5935807a.
  12. Word 11 is column 3 of round key 2. It is w10 (5935807a) exclusive-ored with w7 (2a6c7605), giving 7359f67f.
  13. Word 12 is column 0 of round key 3, and it is the one that does the work. w11 (7359f67f) is rotated left by one byte to 59f67f73, put through the S-box to cb42d28f, then exclusive-ored with round constant 04 in its first byte, giving cf42d28f. That is exclusive-ored with w8 (f2c295f2) to give 3d80477d. The constant is chosen by step of the expansion — this is step 3 — and never by round number, which is the mistake that still passes every AES-128 test and then fails at 192.
  14. Word 13 is column 1 of round key 3. It is w12 (3d80477d) exclusive-ored with w9 (7a96b943), giving 4716fe3e.
  15. Word 14 is column 2 of round key 3. It is w13 (4716fe3e) exclusive-ored with w10 (5935807a), giving 1e237e44.
  16. Word 15 is column 3 of round key 3. It is w14 (1e237e44) exclusive-ored with w11 (7359f67f), giving 6d7a883b.
  17. Word 16 is column 0 of round key 4, and it is the one that does the work. w15 (6d7a883b) is rotated left by one byte to 7a883b6d, put through the S-box to dac4e23c, then exclusive-ored with round constant 08 in its first byte, giving d2c4e23c. That is exclusive-ored with w12 (3d80477d) to give ef44a541. The constant is chosen by step of the expansion — this is step 4 — and never by round number, which is the mistake that still passes every AES-128 test and then fails at 192.
  18. Word 17 is column 1 of round key 4. It is w16 (ef44a541) exclusive-ored with w13 (4716fe3e), giving a8525b7f.
  19. Word 18 is column 2 of round key 4. It is w17 (a8525b7f) exclusive-ored with w14 (1e237e44), giving b671253b.
  20. Word 19 is column 3 of round key 4. It is w18 (b671253b) exclusive-ored with w15 (6d7a883b), giving db0bad00.
  21. Word 20 is column 0 of round key 5, and it is the one that does the work. w19 (db0bad00) is rotated left by one byte to 0bad00db, put through the S-box to 2b9563b9, then exclusive-ored with round constant 10 in its first byte, giving 3b9563b9. That is exclusive-ored with w16 (ef44a541) to give d4d1c6f8. The constant is chosen by step of the expansion — this is step 5 — and never by round number, which is the mistake that still passes every AES-128 test and then fails at 192.
  22. Word 21 is column 1 of round key 5. It is w20 (d4d1c6f8) exclusive-ored with w17 (a8525b7f), giving 7c839d87.
  23. Word 22 is column 2 of round key 5. It is w21 (7c839d87) exclusive-ored with w18 (b671253b), giving caf2b8bc.
  24. Word 23 is column 3 of round key 5. It is w22 (caf2b8bc) exclusive-ored with w19 (db0bad00), giving 11f915bc.
  25. Word 24 is column 0 of round key 6, and it is the one that does the work. w23 (11f915bc) is rotated left by one byte to f915bc11, put through the S-box to 99596582, then exclusive-ored with round constant 20 in its first byte, giving b9596582. That is exclusive-ored with w20 (d4d1c6f8) to give 6d88a37a. The constant is chosen by step of the expansion — this is step 6 — and never by round number, which is the mistake that still passes every AES-128 test and then fails at 192.
  26. Word 25 is column 1 of round key 6. It is w24 (6d88a37a) exclusive-ored with w21 (7c839d87), giving 110b3efd.
  27. Word 26 is column 2 of round key 6. It is w25 (110b3efd) exclusive-ored with w22 (caf2b8bc), giving dbf98641.
  28. Word 27 is column 3 of round key 6. It is w26 (dbf98641) exclusive-ored with w23 (11f915bc), giving ca0093fd.
  29. Word 28 is column 0 of round key 7, and it is the one that does the work. w27 (ca0093fd) is rotated left by one byte to 0093fdca, put through the S-box to 63dc5474, then exclusive-ored with round constant 40 in its first byte, giving 23dc5474. That is exclusive-ored with w24 (6d88a37a) to give 4e54f70e. The constant is chosen by step of the expansion — this is step 7 — and never by round number, which is the mistake that still passes every AES-128 test and then fails at 192.
  30. Word 29 is column 1 of round key 7. It is w28 (4e54f70e) exclusive-ored with w25 (110b3efd), giving 5f5fc9f3.
  31. Word 30 is column 2 of round key 7. It is w29 (5f5fc9f3) exclusive-ored with w26 (dbf98641), giving 84a64fb2.
  32. Word 31 is column 3 of round key 7. It is w30 (84a64fb2) exclusive-ored with w27 (ca0093fd), giving 4ea6dc4f.
  33. Word 32 is column 0 of round key 8, and it is the one that does the work. w31 (4ea6dc4f) is rotated left by one byte to a6dc4f4e, put through the S-box to 2486842f, then exclusive-ored with round constant 80 in its first byte, giving a486842f. That is exclusive-ored with w28 (4e54f70e) to give ead27321. The constant is chosen by step of the expansion — this is step 8 — and never by round number, which is the mistake that still passes every AES-128 test and then fails at 192.
  34. Word 33 is column 1 of round key 8. It is w32 (ead27321) exclusive-ored with w29 (5f5fc9f3), giving b58dbad2.
  35. Word 34 is column 2 of round key 8. It is w33 (b58dbad2) exclusive-ored with w30 (84a64fb2), giving 312bf560.
  36. Word 35 is column 3 of round key 8. It is w34 (312bf560) exclusive-ored with w31 (4ea6dc4f), giving 7f8d292f.
  37. Word 36 is column 0 of round key 9, and it is the one that does the work. w35 (7f8d292f) is rotated left by one byte to 8d292f7f, put through the S-box to 5da515d2, then exclusive-ored with round constant 1b in its first byte, giving 46a515d2. That is exclusive-ored with w32 (ead27321) to give ac7766f3. The constant is chosen by step of the expansion — this is step 9 — and never by round number, which is the mistake that still passes every AES-128 test and then fails at 192.
  38. Word 37 is column 1 of round key 9. It is w36 (ac7766f3) exclusive-ored with w33 (b58dbad2), giving 19fadc21.
  39. Word 38 is column 2 of round key 9. It is w37 (19fadc21) exclusive-ored with w34 (312bf560), giving 28d12941.
  40. Word 39 is column 3 of round key 9. It is w38 (28d12941) exclusive-ored with w35 (7f8d292f), giving 575c006e.
  41. Word 40 is column 0 of round key 10, and it is the one that does the work. w39 (575c006e) is rotated left by one byte to 5c006e57, put through the S-box to 4a639f5b, then exclusive-ored with round constant 36 in its first byte, giving 7c639f5b. That is exclusive-ored with w36 (ac7766f3) to give d014f9a8. The constant is chosen by step of the expansion — this is step 10 — and never by round number, which is the mistake that still passes every AES-128 test and then fails at 192.
  42. Word 41 is column 1 of round key 10. It is w40 (d014f9a8) exclusive-ored with w37 (19fadc21), giving c9ee2589.
  43. Word 42 is column 2 of round key 10. It is w41 (c9ee2589) exclusive-ored with w38 (28d12941), giving e13f0cc8.
  44. Word 43 is column 3 of round key 10. It is w42 (e13f0cc8) exclusive-ored with w39 (575c006e), giving b6630ca6.
12 steps · the two combs and the round constants
  1. At AES-128 a round key and a group of Nk words are the same four words, so the two combs are one pattern: every boundary coincides, and round key 0 is the cipher key itself.
  2. Ten round constants exist and AES-128 consumes 10 of them. Each is chosen by the step of the expansion, i divided by Nk, and never by the round number. The last one this variant reaches is rc10 = 36, at word 40.
  3. rc1 is 01. Word 4 takes it, which is column 0 of round key 1.
  4. rc2 is 02. Word 8 takes it, which is column 0 of round key 2.
  5. rc3 is 04. Word 12 takes it, which is column 0 of round key 3.
  6. rc4 is 08. Word 16 takes it, which is column 0 of round key 4.
  7. rc5 is 10. Word 20 takes it, which is column 0 of round key 5.
  8. rc6 is 20. Word 24 takes it, which is column 0 of round key 6.
  9. rc7 is 40. Word 28 takes it, which is column 0 of round key 7.
  10. rc8 is 80. Word 32 takes it, which is column 0 of round key 8.
  11. rc9 is 1b. Word 36 takes it, which is column 0 of round key 9.
  12. rc10 is 36. Word 40 takes it, which is column 0 of round key 10.
11 round keys · all of them, grouped
11 round keys
Round key 0 IS the cipher key. It is not derived from it, or a function of it: the sixteen bytes added before round 1 are the sixteen bytes you typed.

a0fafe17 88542cb1 23a33939 2a6c7605

The rule is three lines long. The first Nk words are the cipher key, copied in unchanged. After that, each word is the word Nk places back exclusive-ored with the word immediately before it — and one word in every Nk, that second operand goes through the G-box first: RotWord turns it one byte to the left, SubWord puts all four bytes through the same table SubBytes uses, and a round constant is added to byte 0.

The Rcon is chosen by the step of the expansion — i divided by Nk — and never by the round number. At AES-128 those two numbers are equal, which is why rcon[round] passes every AES-128 test vector and then produces a silently wrong schedule at 192. The strip prints both; change the key size and watch them come apart. Ten constants exist and they are generated, not tabulated: 01 doubled in GF(2⁸) nine times, which is where the 1b at rc9 comes from. AES-128 uses all ten, AES-192 eight, AES-256 seven.

AES-256 has a second, weaker G-box that exists in no other variant: at i mod 8 = 4 the word takes SubWord alone, with no rotation and no round constant. The figure draws it with those two boxes present and empty, because what AES-256 does not do there is the thing implementers get wrong. Round keys are blocks of four words at every key size; the recurrence keeps blocks of Nk; at 128 those are one rhythm and every boundary coincides. At 192 they slip, and round key 1 is caught straddling two of them — w4 and w5 still raw cipher key, w6 and w7 derived.

Figure 12 · The schedule inverter

Hand a round key back

Any one of the eleven, and the bytes are yours to edit: four words are exactly an AES-128 key, so every sixteen bytes are this round key of some key.
Commit to an answer first, then run it and see.
Somebody leaks one round key of your AES-128 schedule. What have they given away?
2 steps · what the inverter is asking for and why
  1. An AES-128 cipher key is four words and a round key is four, so this figure asks for one round key. One round key is four words and an AES-128 key is four words, so one is enough — and it works from any round, because the recurrence runs backwards as easily as forwards.
  2. Nothing has been handed back yet: the rows above hold this schedule’s own bytes.

Every stage of that recurrence is reversible. A rotation, a permutation of 256 values, an exclusive-or: knowing any two of w[i], w[i−1] and w[i−Nk] gives you the third, in either direction. So the 11 round keys are not that many independent secrets. At AES-128 any one of them recovers the cipher key and therefore all the others — round key 7 is your key written in another coordinate system, and round key 0, 2b7e1516 28aed2a6 abf71588 09cf4f3c, is your key unchanged.

Above 128 bits one round key is not enough: a round key is 128 bits, and 128 bits cannot pin 192 or 256. But not enough is a long way from nothing. The recurrence runs backwards three words at a time from any four consecutive ones, so a leaked round key gives up words that were never in it: at AES-192, round key 2 alone determines w3, w4 and w5 — half the key. AES-256’s round keys 0 and 1 simply are the two halves of the cipher key. Two adjacent round keys are eight consecutive words, which is enough everywhere, so above 128 the figure asks for a second row and tells you why.

None of this breaks AES. Inverting the schedule needs a round key, and round keys never leave the process that computed them. What it does say is sharp enough: every one of those buffers is exactly as sensitive as the key, which is why constant-time implementations scrub them and why treating a leaked round key as a partial compromise is a mistake.

Part II · The machine

10 Avalanche

Chapter 7 made its case by taking half the machine away. This chapter keeps the machine whole and measures what it does. Take your sixteen bytes, turn a single bit over — one bit of one byte, out of 128 — and encrypt both blocks under the same key. Then read the two runs against each other, step by step, as one exclusive-or.

That difference is the whole of the picture below. A cell shows what differs between the two runs rather than what either of them holds, so a cell reading ·· is a byte the runs still agree on exactly, and a filled one is a byte they do not — the taller the fill, the more of its eight bits have parted. Hold any byte for a moment, or press Shift and Enter on it, and its eight bits open as pips you can turn over one at a time.

Figure 13 · One flipped bit, every step of the run

Step 1 of 40 · the key addition before round 1

One flipped input bit leaves 1 of 128 bits differing after the first step. By the end of the run 68 of the 128 ciphertext bits differ. Every one of the sixteen bytes is carrying part of it from step 8, round 2 MixColumns.
Step 1 of 40, the key addition before round 1: 1 of 16 bytes and 1 of 128 bits differ. Nothing new joined in at this step.
40 steps · the difference at every step
  1. Step 1 of 40, the key addition before round 1: 1 of 16 bytes and 1 of 128 bits differ. Nothing new joined in at this step.
  2. Step 2 of 40, round 1 SubBytes: 1 of 16 bytes and 5 of 128 bits differ. Nothing new joined in at this step.
  3. Step 3 of 40, round 1 ShiftRows: 1 of 16 bytes and 5 of 128 bits differ. Nothing new joined in at this step.
  4. Step 4 of 40, round 1 MixColumns: 4 of 16 bytes and 19 of 128 bits differ. 3 cells have just joined in.
  5. Step 5 of 40, round 1 AddRoundKey: 4 of 16 bytes and 19 of 128 bits differ. Nothing new joined in at this step.
  6. Step 6 of 40, round 2 SubBytes: 4 of 16 bytes and 20 of 128 bits differ. Nothing new joined in at this step.
  7. Step 7 of 40, round 2 ShiftRows: 4 of 16 bytes and 20 of 128 bits differ. 3 cells have just joined in.
  8. Step 8 of 40, round 2 MixColumns: 16 of 16 bytes and 70 of 128 bits differ. Every byte of the state is now carrying part of that one flipped bit.
  9. Step 9 of 40, round 2 AddRoundKey: 16 of 16 bytes and 70 of 128 bits differ. Nothing new joined in at this step.
  10. Step 10 of 40, round 3 SubBytes: 16 of 16 bytes and 68 of 128 bits differ. Nothing new joined in at this step.
  11. Step 11 of 40, round 3 ShiftRows: 16 of 16 bytes and 68 of 128 bits differ. Nothing new joined in at this step.
  12. Step 12 of 40, round 3 MixColumns: 16 of 16 bytes and 62 of 128 bits differ. Nothing new joined in at this step.
  13. Step 13 of 40, round 3 AddRoundKey: 16 of 16 bytes and 62 of 128 bits differ. Nothing new joined in at this step.
  14. Step 14 of 40, round 4 SubBytes: 16 of 16 bytes and 70 of 128 bits differ. Nothing new joined in at this step.
  15. Step 15 of 40, round 4 ShiftRows: 16 of 16 bytes and 70 of 128 bits differ. Nothing new joined in at this step.
  16. Step 16 of 40, round 4 MixColumns: 16 of 16 bytes and 68 of 128 bits differ. Nothing new joined in at this step.
  17. Step 17 of 40, round 4 AddRoundKey: 16 of 16 bytes and 68 of 128 bits differ. Nothing new joined in at this step.
  18. Step 18 of 40, round 5 SubBytes: 16 of 16 bytes and 64 of 128 bits differ. Nothing new joined in at this step.
  19. Step 19 of 40, round 5 ShiftRows: 16 of 16 bytes and 64 of 128 bits differ. Nothing new joined in at this step.
  20. Step 20 of 40, round 5 MixColumns: 16 of 16 bytes and 68 of 128 bits differ. Nothing new joined in at this step.
  21. Step 21 of 40, round 5 AddRoundKey: 16 of 16 bytes and 68 of 128 bits differ. Nothing new joined in at this step.
  22. Step 22 of 40, round 6 SubBytes: 16 of 16 bytes and 61 of 128 bits differ. Nothing new joined in at this step.
  23. Step 23 of 40, round 6 ShiftRows: 16 of 16 bytes and 61 of 128 bits differ. Nothing new joined in at this step.
  24. Step 24 of 40, round 6 MixColumns: 16 of 16 bytes and 61 of 128 bits differ. Nothing new joined in at this step.
  25. Step 25 of 40, round 6 AddRoundKey: 16 of 16 bytes and 61 of 128 bits differ. Nothing new joined in at this step.
  26. Step 26 of 40, round 7 SubBytes: 16 of 16 bytes and 65 of 128 bits differ. Nothing new joined in at this step.
  27. Step 27 of 40, round 7 ShiftRows: 16 of 16 bytes and 65 of 128 bits differ. Nothing new joined in at this step.
  28. Step 28 of 40, round 7 MixColumns: 16 of 16 bytes and 67 of 128 bits differ. Nothing new joined in at this step.
  29. Step 29 of 40, round 7 AddRoundKey: 16 of 16 bytes and 67 of 128 bits differ. Nothing new joined in at this step.
  30. Step 30 of 40, round 8 SubBytes: 16 of 16 bytes and 65 of 128 bits differ. Nothing new joined in at this step.
  31. Step 31 of 40, round 8 ShiftRows: 16 of 16 bytes and 65 of 128 bits differ. Nothing new joined in at this step.
  32. Step 32 of 40, round 8 MixColumns: 16 of 16 bytes and 65 of 128 bits differ. Nothing new joined in at this step.
  33. Step 33 of 40, round 8 AddRoundKey: 16 of 16 bytes and 65 of 128 bits differ. Nothing new joined in at this step.
  34. Step 34 of 40, round 9 SubBytes: 16 of 16 bytes and 69 of 128 bits differ. Nothing new joined in at this step.
  35. Step 35 of 40, round 9 ShiftRows: 16 of 16 bytes and 69 of 128 bits differ. Nothing new joined in at this step.
  36. Step 36 of 40, round 9 MixColumns: 16 of 16 bytes and 75 of 128 bits differ. Nothing new joined in at this step.
  37. Step 37 of 40, round 9 AddRoundKey: 16 of 16 bytes and 75 of 128 bits differ. Nothing new joined in at this step.
  38. Step 38 of 40, round 10 SubBytes: 16 of 16 bytes and 68 of 128 bits differ. Nothing new joined in at this step.
  39. Step 39 of 40, round 10 ShiftRows: 16 of 16 bytes and 68 of 128 bits differ. Nothing new joined in at this step.
  40. Step 40 of 40, round 10 AddRoundKey: 16 of 16 bytes and 68 of 128 bits differ. Nothing new joined in at this step.

The shape is the same wherever you put the difference. The key addition carries that one bit straight through, because the same round key goes into both runs and cancels; the first substitution turns it into 5 differing bits, because the table maps a one-bit change to a change of usually several bits, and never to none at all. The first MixColumns turns that one byte into four, since every byte of a mixed column depends on all four bytes of the old one. Then ShiftRows scatters those four into four different columns, and the next mixing reaches every byte of every one of them. Two rounds, and it is everywhere: from step 8, round 2 MixColumns, all sixteen bytes differ.

After that it stops spreading, because there is nowhere left to spread to. What the remaining rounds do is not widen the difference but keep stirring which bits carry it, so that no trace of the original flip survives in its position. By the ciphertext, 68 of the 128 bits differ — between 3925841d 02dc09fb dc118597 196a0b32 and a block encrypted from a plaintext one bit away from yours.

One pair of runs is an anecdote. Below is the measurement: a thousand runs, each a fresh random key and a fresh random block with a randomly chosen bit turned over, stacked into buckets of eight bits. It runs in your browser as you read, fifty trials to an animation frame so that nothing on the page stops moving.

A thousand runs

One flipped input bit, counted at the output

0 of 1,000 runs…

16 buckets · the measurement as text
  1. 0 to 7 bits changed: 0 runs.
  2. 8 to 15 bits changed: 0 runs.
  3. 16 to 23 bits changed: 0 runs.
  4. 24 to 31 bits changed: 0 runs.
  5. 32 to 39 bits changed: 0 runs.
  6. 40 to 47 bits changed: 0 runs.
  7. 48 to 55 bits changed: 0 runs.
  8. 56 to 63 bits changed: 0 runs.
  9. 64 to 71 bits changed: 0 runs.
  10. 72 to 79 bits changed: 0 runs.
  11. 80 to 87 bits changed: 0 runs.
  12. 88 to 95 bits changed: 0 runs.
  13. 96 to 103 bits changed: 0 runs.
  14. 104 to 111 bits changed: 0 runs.
  15. 112 to 119 bits changed: 0 runs.
  16. 120 to 128 bits changed: 0 runs.

The distribution sits on 64, which is half of 128, and it is about as wide as coin-tossing says it should be. That is the property called avalanche, and the reason it matters is what it denies an attacker: there is no warm and no cold. A key that is wrong in a single bit does not produce a ciphertext nearly right — it produces one wrong in about half its bits, exactly like a key that is wrong in every bit. Nothing about a near miss is nearer than any other guess, so there is nothing to hill-climb towards and no shortcut through the 2128 of them.

This is a measurement and not a theorem, which is why the panel prints its sample size. Run it again and the mean will land somewhere slightly else.

Part II · The machine

11 Backwards

Everything so far has run one way. It did not have to: every operation in the round is invertible on its own. The substitution is a table with an inverse table, the shift is a permutation, the mix is an invertible matrix, and the key addition undoes itself — which you already made it do in Chapter 2, before decryption had been mentioned. Run each inverse in the opposite order and your sixteen bytes come back. Decryption is not a second cipher.

Two consequences first. InvShiftRows and InvSubBytes can be done in either order, because one changes where bytes are and the other changes what they are. And the round keys are consumed backwards, last to first, so decryption cannot begin until the whole expansion has been computed: encryption can make each round key as it reaches it, and decryption cannot.

The third consequence is a problem, and it is the one nobody draws. Put the two round brackets side by side. Encryption ends its round with the key addition. The plain inverse has to put it third of four — after the two unmixings of position and value, before the column unmixing — because that is the order the encryption left. The two combs are out of phase by exactly one operation, all the way down the run.

Figure 14 · The mirror rail

Round 1 · AddRoundKey undone by AddRoundKey

1 operation
lower rail

Out of phase by one operation: this lane adds the round key in the middle of its round, and the encryption adds it at the end.

both lanes, between the paired stepsa49c7ff2 689f352b 6b5bea43 026a5049
40 steps · every pairing as text
  1. Encryption step 1 of 40, round 0 — AddRoundKey — is undone by inverse step 40 of 40, round 0, AddRoundKey. Both lanes hold the same sixteen bytes at that boundary: 193de3be a0f4e22b 9ac68d2a e9f84808.
  2. Encryption step 2 of 40, round 1 — SubBytes — is undone by inverse step 39 of 40, round 0, InvSubBytes. Both lanes hold the same sixteen bytes at that boundary: d42711ae e0bf98f1 b8b45de5 1e415230.
  3. Encryption step 3 of 40, round 1 — ShiftRows — is undone by inverse step 38 of 40, round 0, InvShiftRows. Both lanes hold the same sixteen bytes at that boundary: d4bf5d30 e0b452ae b84111f1 1e2798e5.
  4. Encryption step 4 of 40, round 1 — MixColumns — is undone by inverse step 37 of 40, round 1, InvMixColumns. Both lanes hold the same sixteen bytes at that boundary: 046681e5 e0cb199a 48f8d37a 2806264c.
  5. Encryption step 5 of 40, round 1 — AddRoundKey — is undone by inverse step 36 of 40, round 1, AddRoundKey. Both lanes hold the same sixteen bytes at that boundary: a49c7ff2 689f352b 6b5bea43 026a5049.
  6. Encryption step 6 of 40, round 2 — SubBytes — is undone by inverse step 35 of 40, round 1, InvSubBytes. Both lanes hold the same sixteen bytes at that boundary: 49ded289 45db96f1 7f39871a 7702533b.
  7. Encryption step 7 of 40, round 2 — ShiftRows — is undone by inverse step 34 of 40, round 1, InvShiftRows. Both lanes hold the same sixteen bytes at that boundary: 49db873b 45395389 7f02d2f1 77de961a.
  8. Encryption step 8 of 40, round 2 — MixColumns — is undone by inverse step 33 of 40, round 2, InvMixColumns. Both lanes hold the same sixteen bytes at that boundary: 584dcaf1 1b4b5aac dbe7caa8 1b6bb0e5.
  9. Encryption step 9 of 40, round 2 — AddRoundKey — is undone by inverse step 32 of 40, round 2, AddRoundKey. Both lanes hold the same sixteen bytes at that boundary: aa8f5f03 61dde3ef 82d24ad2 6832469a.
  10. Encryption step 10 of 40, round 3 — SubBytes — is undone by inverse step 31 of 40, round 2, InvSubBytes. Both lanes hold the same sixteen bytes at that boundary: ac73cf7b efc111df 13b5d6b5 45235ab8.
  11. Encryption step 11 of 40, round 3 — ShiftRows — is undone by inverse step 30 of 40, round 2, InvShiftRows. Both lanes hold the same sixteen bytes at that boundary: acc1d6b8 efb55a7b 1323cfdf 457311b5.
  12. Encryption step 12 of 40, round 3 — MixColumns — is undone by inverse step 29 of 40, round 3, InvMixColumns. Both lanes hold the same sixteen bytes at that boundary: 75ec0993 200b6333 53c0cf7c bb25d0dc.
  13. Encryption step 13 of 40, round 3 — AddRoundKey — is undone by inverse step 28 of 40, round 3, AddRoundKey. Both lanes hold the same sixteen bytes at that boundary: 486c4eee 671d9d0d 4de3b138 d65f58e7.
  14. Encryption step 14 of 40, round 4 — SubBytes — is undone by inverse step 27 of 40, round 3, InvSubBytes. Both lanes hold the same sixteen bytes at that boundary: 52502f28 85a45ed7 e311c807 f6cf6a94.
  15. Encryption step 15 of 40, round 4 — ShiftRows — is undone by inverse step 26 of 40, round 3, InvShiftRows. Both lanes hold the same sixteen bytes at that boundary: 52a4c894 85116a28 e3cf2fd7 f6505e07.
  16. Encryption step 16 of 40, round 4 — MixColumns — is undone by inverse step 25 of 40, round 4, InvMixColumns. Both lanes hold the same sixteen bytes at that boundary: 0fd6daa9 603138bf 6fc0106b 5eb31301.
  17. Encryption step 17 of 40, round 4 — AddRoundKey — is undone by inverse step 24 of 40, round 4, AddRoundKey. Both lanes hold the same sixteen bytes at that boundary: e0927fe8 c86363c0 d9b13550 85b8be01.
  18. Encryption step 18 of 40, round 5 — SubBytes — is undone by inverse step 23 of 40, round 4, InvSubBytes. Both lanes hold the same sixteen bytes at that boundary: e14fd29b e8fbfbba 35c89653 976cae7c.
  19. Encryption step 19 of 40, round 5 — ShiftRows — is undone by inverse step 22 of 40, round 4, InvShiftRows. Both lanes hold the same sixteen bytes at that boundary: e1fb967c e8c8ae9b 356cd2ba 974ffb53.
  20. Encryption step 20 of 40, round 5 — MixColumns — is undone by inverse step 21 of 40, round 5, InvMixColumns. Both lanes hold the same sixteen bytes at that boundary: 25d1a9ad bd11d168 b63a338e 4c4cc0b0.
  21. Encryption step 21 of 40, round 5 — AddRoundKey — is undone by inverse step 20 of 40, round 5, AddRoundKey. Both lanes hold the same sixteen bytes at that boundary: f1006f55 c1924cef 7cc88b32 5db5d50c.
  22. Encryption step 22 of 40, round 6 — SubBytes — is undone by inverse step 19 of 40, round 5, InvSubBytes. Both lanes hold the same sixteen bytes at that boundary: a163a8fc 784f29df 10e83d23 4cd503fe.
  23. Encryption step 23 of 40, round 6 — ShiftRows — is undone by inverse step 18 of 40, round 5, InvShiftRows. Both lanes hold the same sixteen bytes at that boundary: a14f3dfe 78e803fc 10d5a8df 4c632923.
  24. Encryption step 24 of 40, round 6 — MixColumns — is undone by inverse step 17 of 40, round 6, InvMixColumns. Both lanes hold the same sixteen bytes at that boundary: 4b868d6d 2c4a8980 339df4e8 37d218d8.
  25. Encryption step 25 of 40, round 6 — AddRoundKey — is undone by inverse step 16 of 40, round 6, AddRoundKey. Both lanes hold the same sixteen bytes at that boundary: 260e2e17 3d41b77d e86472a9 fdd28b25.
  26. Encryption step 26 of 40, round 7 — SubBytes — is undone by inverse step 15 of 40, round 6, InvSubBytes. Both lanes hold the same sixteen bytes at that boundary: f7ab31f0 2783a9ff 9b4340d3 54b53d3f.
  27. Encryption step 27 of 40, round 7 — ShiftRows — is undone by inverse step 14 of 40, round 6, InvShiftRows. Both lanes hold the same sixteen bytes at that boundary: f783403f 27433df0 9bb531ff 54aba9d3.
  28. Encryption step 28 of 40, round 7 — MixColumns — is undone by inverse step 13 of 40, round 7, InvMixColumns. Both lanes hold the same sixteen bytes at that boundary: 1415b5bf 461615ec 274656d7 342ad843.
  29. Encryption step 29 of 40, round 7 — AddRoundKey — is undone by inverse step 12 of 40, round 7, AddRoundKey. Both lanes hold the same sixteen bytes at that boundary: 5a4142b1 1949dc1f a3e01965 7a8c040c.
  30. Encryption step 30 of 40, round 8 — SubBytes — is undone by inverse step 11 of 40, round 7, InvSubBytes. Both lanes hold the same sixteen bytes at that boundary: be832cc8 d43b86c0 0ae1d44d da64f2fe.
  31. Encryption step 31 of 40, round 8 — ShiftRows — is undone by inverse step 10 of 40, round 7, InvShiftRows. Both lanes hold the same sixteen bytes at that boundary: be3bd4fe d4e1f2c8 0a642cc0 da83864d.
  32. Encryption step 32 of 40, round 8 — MixColumns — is undone by inverse step 9 of 40, round 8, InvMixColumns. Both lanes hold the same sixteen bytes at that boundary: 00512fd1 b1c889ff 54766dcd fa1b99ea.
  33. Encryption step 33 of 40, round 8 — AddRoundKey — is undone by inverse step 8 of 40, round 8, AddRoundKey. Both lanes hold the same sixteen bytes at that boundary: ea835cf0 0445332d 655d98ad 8596b0c5.
  34. Encryption step 34 of 40, round 9 — SubBytes — is undone by inverse step 7 of 40, round 8, InvSubBytes. Both lanes hold the same sixteen bytes at that boundary: 87ec4a8c f26ec3d8 4d4c4695 9790e7a6.
  35. Encryption step 35 of 40, round 9 — ShiftRows — is undone by inverse step 6 of 40, round 8, InvShiftRows. Both lanes hold the same sixteen bytes at that boundary: 876e46a6 f24ce78c 4d904ad8 97ecc395.
  36. Encryption step 36 of 40, round 9 — MixColumns — is undone by inverse step 5 of 40, round 9, InvMixColumns. Both lanes hold the same sixteen bytes at that boundary: 473794ed 40d4e4a5 a3703aa6 4c9f42bc.
  37. Encryption step 37 of 40, round 9 — AddRoundKey — is undone by inverse step 4 of 40, round 9, AddRoundKey. Both lanes hold the same sixteen bytes at that boundary: eb40f21e 592e3884 8ba113e7 1bc342d2.
  38. Encryption step 38 of 40, round 10 — SubBytes — is undone by inverse step 3 of 40, round 9, InvSubBytes. Both lanes hold the same sixteen bytes at that boundary: e9098972 cb31075f 3d327d94 af2e2cb5.
  39. Encryption step 39 of 40, round 10 — ShiftRows — is undone by inverse step 2 of 40, round 9, InvShiftRows. Both lanes hold the same sixteen bytes at that boundary: e9317db5 cb322c72 3d2e895f af090794.
  40. Encryption step 40 of 40, round 10 — AddRoundKey — is undone by inverse step 1 of 40, round 10, AddRoundKey. Both lanes hold the same sixteen bytes at that boundary: 3925841d 02dc09fb dc118597 196a0b32.

The encryption adds its round key as operation 4 of the round; this lane adds it as operation 3. Every key addition on the lower rail therefore sits one operation to the left of the one it answers, all the way down the run — the two combs are out of phase by one operation.

That offset is why a decryption written this way needs a round loop of its own rather than the encryption’s with different tables in it. Which raises the question the next figure asks. InvMixColumns is a matrix over the field, so unmixing a sum is the sum of the unmixings: IMC(state ⊕ rk) is IMC(state) ⊕ IMC(rk). If that is true, the key addition can be done after the unmixing instead of before it — and the round goes back into the encryption’s shape.

Figure 15 · The equivalent inverse cipher

Round key 1 · put through InvMixColumns

dk1 — rk put through InvMixColumns2b3708a7 f262d405 bc3ebdbf 4b617d62
InvMixColumns(state ⊕ rk1)d4bf5d30 e0b452ae b84111f1 1e2798e5
InvMixColumns(state) ⊕ dk1d4bf5d30 e0b452ae b84111f1 1e2798e5

the same sixteen bytes

InvMixColumns is linear, and the plain inverse computes InvMixColumns(state ⊕ rk). Can that exclusive-or be done afterwards instead?

The message came back:3243f6a8 885a308d 313198a2 e0370734

11 steps · every round key as text
  1. Round key 0 feeds the last key addition of the decryption: rk0 is 2b7e1516 28aed2a6 abf71588 09cf4f3c, and dk0 is the same sixteen bytes. It sits outside the mixing, so there is nothing to move the key across and nothing to transform.
  2. Round key 1 feeds round 1: rk1 is a0fafe17 88542cb1 23a33939 2a6c7605, and dk1 is that put through InvMixColumns, 2b3708a7 f262d405 bc3ebdbf 4b617d62.
  3. Round key 2 feeds round 2: rk2 is f2c295f2 7a96b943 5935807a 7359f67f, and dk2 is that put through InvMixColumns, cc7505eb 3e17d1ee 82296c51 c9481133.
  4. Round key 3 feeds round 3: rk3 is 3d80477d 4716fe3e 1e237e44 6d7a883b, and dk3 is that put through InvMixColumns, 7c1f13f7 4208c219 c021ae48 0969bf7b.
  5. Round key 4 feeds round 4: rk4 is ef44a541 a8525b7f b671253b db0bad00, and dk4 is that put through InvMixColumns, 90884413 d280860a 12a12842 1bc89739.
  6. Round key 5 feeds round 5: rk5 is d4d1c6f8 7c839d87 caf2b8bc 11f915bc, and dk5 is that put through InvMixColumns, 6ea30afc bc238cf6 ae82a4b4 b54a338d.
  7. Round key 6 feeds round 6: rk6 is 6d88a37a 110b3efd dbf98641 ca0093fd, and dk6 is that put through InvMixColumns, 6efcd876 d2df5480 7c5df034 c917c3b9.
  8. Round key 7 feeds round 7: rk7 is 4e54f70e 5f5fc9f3 84a64fb2 4ea6dc4f, and dk7 is that put through InvMixColumns, 12c07647 c01f22c7 bc42d2f3 7555114a.
  9. Round key 8 feeds round 8: rk8 is ead27321 b58dbad2 312bf560 7f8d292f, and dk8 is that put through InvMixColumns, df7d925a 1f62b09d a320626e d6757324.
  10. Round key 9 feeds round 9: rk9 is ac7766f3 19fadc21 28d12941 575c006e, and dk9 is that put through InvMixColumns, 0c7b5a63 1319eafe b0398890 664cfbb4.
  11. Round key 10 feeds the first key addition of the decryption: rk10 is d014f9a8 c9ee2589 e13f0cc8 b6630ca6, and dk10 is the same sixteen bytes. It sits outside the mixing, so there is nothing to move the key across and nothing to transform.

The cost has moved, and that is the whole of the trick. Unmixing the state happens once per block per round; unmixing a round key happens once per schedule, and one schedule serves as many blocks as you like. That is what makes the equivalent inverse cipher the version real implementations ship: both directions, one round loop, one set of tables.

Two of those keys must be left exactly as they are. The first key addition of the decryption and the last one sit outside the mixing altogether — there is no InvMixColumns for them to move across — so transforming them corrects for an operation that never happens. That is the wire routed round the outside of the block above, and the switch under the figure is the classic bug: throw it and the encryption is untouched, the plain inverse still returns your message, and the rearranged one stops.

And here is the debt from Chapter 8. The final round has no MixColumns, and both rails above carry the gap: the encryption’s empty slot and the rearranged inverse’s fall in the same place, while the plain inverse’s sits at the far end of the run. Had the last round mixed, the inverse would have opened with an unmixing that answered nothing and the two loops would never have had the same shape. The omission that looked like a saving is what lets one implementation run both ways.

Decryption is also the slower direction. The inverse matrix’s coefficients are 0E, 0B, 0D and 09 against the forward 02, 03, 01 and 01 — three doublings apiece where the encryption needs one. Chapter 4’s bench has them.

Part III · In the world

12 One block is not a message

Here is the thing this document has not said yet. AES encrypts exactly one block: sixteen bytes in, sixteen bytes out, and that is the entire function. Nothing you have ever encrypted was sixteen bytes long. Every file, every message, every disk sector had to be cut up and fed through in pieces, and the arrangement that does the cutting is a separate design decision with a separate name. It is called a mode of operation, and almost every real failure of AES in the field has been a failure of something around the cipher rather than of the cipher — the mode first and largest, the way the program leaks after it.

The obvious arrangement is the one everybody invents on the first try: chop the message into sixteen-byte blocks and put each one through the cipher. That is Electronic Codebook, ECB, and it is a real mode in a real standard. Below is a small uncompressed bitmap — 49,152 bytes, which is 3,072 blocks exactly — encrypted that way with your own key by the same code the last eleven chapters have been building.

Figure 16 · The penguin, and what actually leaks

The bytes, as a picture

not startedtap the picture to open a block
This bitmap is about to be cut into 3,072 blocks and every block encrypted with AES under your key. What will the result look like?
4 steps · the four readings as text
  1. A 128 by 128 bitmap, uncompressed: 16,384 pixels of three bytes each, which is 49,152 bytes, which is exactly 3,072 blocks of sixteen. Nothing here has been encrypted yet.
  2. Every one of those 3,072 blocks, put through AES under your own key, independently. not started.
  3. Counting how many of the ciphertext blocks are equal to each other.
  4. The same image again, with each block exclusive-ored with the one before it before encryption.

What ECB gives away, counted

The block-equality relation, and nothing else

—counting the blocks as they come out

0 to 3,071. Every block in the image is reachable here, which is what makes tapping the picture a shortcut rather than the only way in.

The usual telling of this picture is wrong, and the wrong version does damage. ECB does not leak patterns and it does not leak images. It leaks one thing: which of your blocks were equal to which. Two blocks come out identical exactly when they went in identical, and that relation survives untouched. Everything else — the colours, the shapes, the edges — is reconstructed by your eye from that relation alone, because a drawing of flat colour is mostly repeated blocks.

Which is why the counter matters more than the bird. Run the same mode over a photograph, or over anything compressed, and no two blocks are ever equal; the counter reads all 3,072 distinct and the output is noise. People conclude from that that ECB is fine for their data. It is not: the leak did not go away, there was simply nothing in that file to leak. Any repeated block — a repeated database field, a repeated header, the same answer sent twice — is still visible, in the clear, to anyone holding the ciphertext.

Tap any square of the picture, or reach it from the counter below, and you land inside that block’s own encryption: the 40 steps, the 10 rounds, the same state grid as Chapter 8, on sixteen bytes of a penguin. Nothing about the image is special. It is 3,072 runs of the machine you have already read, and the breadcrumb walks back out.

So: do not use ECB. Not for files, not for fields in a database, not for anything that might ever contain the same sixteen bytes twice. It survives in the standards for two honest reasons — it is the primitive every other mode is written in terms of, so a document that specifies CBC has to name it first; and it is exactly right in the one case where the message is a single block that never repeats, such as encrypting a key under another key. Outside that, it is a mode whose only property is the one you do not want.

The fix is not a stronger cipher. The cipher is doing precisely what it promised. The fix is to make the blocks stop being independent, so that two identical blocks cannot produce the same output — and the cheapest way to do that is to feed each block something from the block before it.

Part III · In the world

13 Chaining

The diagnosis at the end of the last chapter was precise, so the fix can be too. The blocks are independent; make them depend on each other. Before a block goes into the cipher, exclusive-or it with the ciphertext of the block before it. That is CBC — one wire, drawn below as a wire — and it is enough, because two identical plaintext blocks now arrive at the cipher carrying different bytes.

Block 1 has no block before it, so something has to fill the slot: the IV. It is not a second key and it is not secret — it is sent in the clear, alongside the ciphertext, because the receiver needs it to undo the first XOR. What it must be is different every time — and unguessable before it is sent. Reuse one and the first block of every message under that key is back to ECB; use a counter, which is fresh every time and still predictable, and an attacker who knows the next IV chooses what the cipher sees.

Figure 17 · The chain, and the slot before block 1

The initialisation vector

IV
00000000 00000000 00000000 00000000
role
the ciphertext block before block 1, which does not exist
The initialisation vector, 00000000…, sitting in the slot before block 1. It is not secret and it is not a key; it is there so that the first block has something to be exclusive-ored with, and so that encrypting the same message twice gives different ciphertext.
5 steps · the chain as text
  1. The initialisation vector, 00000000…, sitting in the slot before block 1. It is not secret and it is not a key; it is there so that the first block has something to be exclusive-ored with, and so that encrypting the same message twice gives different ciphertext.
  2. Block 1 of 4. Its plaintext 3243f6a8… is exclusive-ored with the IV 00000000…, giving 3243f6a8…, and it is THAT which goes through the cipher — never the plaintext itself. Out comes 3925841d…. ECB, on the same block, would have produced 3925841d….
  3. Block 2 of 4. Its plaintext 3243f6a8… is exclusive-ored with block 1's ciphertext 3925841d…, giving 0b6672b5…, and it is THAT which goes through the cipher — never the plaintext itself. Out comes ebbb47f6…. ECB, on the same block, would have produced 3925841d….
  4. Block 3 of 4. Its plaintext 3243f6a8… is exclusive-ored with block 2's ciphertext ebbb47f6…, giving d9f8b15e…, and it is THAT which goes through the cipher — never the plaintext itself. Out comes b3a31631…. ECB, on the same block, would have produced 3925841d….
  5. Block 4 of 4. Its plaintext 3243f6a8… is exclusive-ored with block 3's ciphertext b3a31631…, giving 81e0e099…, and it is THAT which goes through the cipher — never the plaintext itself. Out comes ead15bc0…. ECB, on the same block, would have produced 3925841d….

The same four blocks, both ways

One key, one plaintext, two arrangements

IV

CBC: 4 different ciphertext blocks. ECB, over the same message and the same key: 1. Every block of it comes out as 3925841d…, 4 times over, which is a fact about your plaintext printed in the clear.

With it off, the second send uses an IV one byte different from the first.
send 1
3925841d 02dc09fb dc118597 196a0b32
send 2
3925841d 02dc09fb dc118597 196a0b32

Byte for byte identical. Anyone watching the wire now knows you sent the same thing twice, without holding the key — which is the exact leak the whole of Chapter 12 was about, reintroduced by reusing sixteen public bytes.

Turn on the edit and watch which links move. Changing one bit of block 3 changes block 3’s ciphertext, and therefore block 4’s input, and therefore everything downstream — while blocks 1 and 2 do not move at all. Damage runs forwards along the chain and never backwards, which is the same fact as the one that makes encryption serial: block n cannot start until block n − 1 has finished. Decryption has no such constraint. Every block needs only its own ciphertext block and the one before it, so a receiver can decrypt the whole message at once.

That asymmetry has a sharp edge. Corrupt one ciphertext block and exactly two plaintext blocks are harmed: the one that was hit comes back as noise, and the one after it comes back with precisely the corresponding bit flipped and its other 127 bits untouched. An attacker who cannot read your message can still choose which bits of it change.

One flipped ciphertext bit

What CBC's receiver does about it: nothing

blocks harmed
2 and 3
block 2
71 of 128 bits changed — noise
block 3
1 of 128 bits changed — bit 6 of byte 2, the one that was flipped
One bit of ciphertext block 2 is turned over. Block 2 comes back as 71 changed bits of noise. Block 3 comes back with exactly one bit changed — bit 6 of byte 2, the very bit that was flipped — and every one of its other 127 bits intact. Nothing objects. Nothing else in the message is touched.

And nothing objects. CBC decrypts what it is given, hands back sixteen bytes and offers no opinion about whether they are the sixteen bytes that were sent. That gap is the subject of Chapter 15.

One obligation remains. The cipher takes whole blocks, and messages are not whole blocks, so the last one has to be filled. PKCS#7 padding is the usual answer and its rule is one line: add between one and sixteen bytes, every one of them carrying the count of how many were added. The receiver reads the last byte and removes that many.

Figure 18 · PKCS#7, nought to thirty-two bytes

A message of 13 bytes

jump to
bytes of message
13 bytes in, 16 out: 3 bytes of 0x03, every one of them carrying the count, so the reader at the other end removes exactly 3 and gets your message back to the byte.
33 steps · every length from 0 to 32 as text
  1. 0 bytes in, 16 out. An empty message still gets a block: sixteen 0x10 bytes and nothing else. There is no message here at all, and the padding rule does not care.
  2. 1 byte in, 16 out: 15 bytes of 0x0f, every one of them carrying the count, so the reader at the other end removes exactly 15 and gets your message back to the byte.
  3. 2 bytes in, 16 out: 14 bytes of 0x0e, every one of them carrying the count, so the reader at the other end removes exactly 14 and gets your message back to the byte.
  4. 3 bytes in, 16 out: 13 bytes of 0x0d, every one of them carrying the count, so the reader at the other end removes exactly 13 and gets your message back to the byte.
  5. 4 bytes in, 16 out: 12 bytes of 0x0c, every one of them carrying the count, so the reader at the other end removes exactly 12 and gets your message back to the byte.
  6. 5 bytes in, 16 out: 11 bytes of 0x0b, every one of them carrying the count, so the reader at the other end removes exactly 11 and gets your message back to the byte.
  7. 6 bytes in, 16 out: 10 bytes of 0x0a, every one of them carrying the count, so the reader at the other end removes exactly 10 and gets your message back to the byte.
  8. 7 bytes in, 16 out: 9 bytes of 0x09, every one of them carrying the count, so the reader at the other end removes exactly 9 and gets your message back to the byte.
  9. 8 bytes in, 16 out: 8 bytes of 0x08, every one of them carrying the count, so the reader at the other end removes exactly 8 and gets your message back to the byte.
  10. 9 bytes in, 16 out: 7 bytes of 0x07, every one of them carrying the count, so the reader at the other end removes exactly 7 and gets your message back to the byte.
  11. 10 bytes in, 16 out: 6 bytes of 0x06, every one of them carrying the count, so the reader at the other end removes exactly 6 and gets your message back to the byte.
  12. 11 bytes in, 16 out: 5 bytes of 0x05, every one of them carrying the count, so the reader at the other end removes exactly 5 and gets your message back to the byte.
  13. 12 bytes in, 16 out: 4 bytes of 0x04, every one of them carrying the count, so the reader at the other end removes exactly 4 and gets your message back to the byte.
  14. 13 bytes in, 16 out: 3 bytes of 0x03, every one of them carrying the count, so the reader at the other end removes exactly 3 and gets your message back to the byte.
  15. 14 bytes in, 16 out: 2 bytes of 0x02, every one of them carrying the count, so the reader at the other end removes exactly 2 and gets your message back to the byte.
  16. 15 bytes in, 16 out: 1 byte of 0x01, every one of them carrying the count, so the reader at the other end removes exactly 1 and gets your message back to the byte.
  17. 16 bytes in, 32 out, and this is the row nobody believes. The message already fills its blocks exactly, so PKCS#7 adds a WHOLE EXTRA BLOCK of 0x10. It has to: the rule is that the last byte always says how many bytes to remove, so a message ending in 0x10 by accident and one padded with 16 bytes of 0x10 must be told apart, and only an unconditional pad can do it.
  18. 17 bytes in, 32 out: 15 bytes of 0x0f, every one of them carrying the count, so the reader at the other end removes exactly 15 and gets your message back to the byte.
  19. 18 bytes in, 32 out: 14 bytes of 0x0e, every one of them carrying the count, so the reader at the other end removes exactly 14 and gets your message back to the byte.
  20. 19 bytes in, 32 out: 13 bytes of 0x0d, every one of them carrying the count, so the reader at the other end removes exactly 13 and gets your message back to the byte.
  21. 20 bytes in, 32 out: 12 bytes of 0x0c, every one of them carrying the count, so the reader at the other end removes exactly 12 and gets your message back to the byte.
  22. 21 bytes in, 32 out: 11 bytes of 0x0b, every one of them carrying the count, so the reader at the other end removes exactly 11 and gets your message back to the byte.
  23. 22 bytes in, 32 out: 10 bytes of 0x0a, every one of them carrying the count, so the reader at the other end removes exactly 10 and gets your message back to the byte.
  24. 23 bytes in, 32 out: 9 bytes of 0x09, every one of them carrying the count, so the reader at the other end removes exactly 9 and gets your message back to the byte.
  25. 24 bytes in, 32 out: 8 bytes of 0x08, every one of them carrying the count, so the reader at the other end removes exactly 8 and gets your message back to the byte.
  26. 25 bytes in, 32 out: 7 bytes of 0x07, every one of them carrying the count, so the reader at the other end removes exactly 7 and gets your message back to the byte.
  27. 26 bytes in, 32 out: 6 bytes of 0x06, every one of them carrying the count, so the reader at the other end removes exactly 6 and gets your message back to the byte.
  28. 27 bytes in, 32 out: 5 bytes of 0x05, every one of them carrying the count, so the reader at the other end removes exactly 5 and gets your message back to the byte.
  29. 28 bytes in, 32 out: 4 bytes of 0x04, every one of them carrying the count, so the reader at the other end removes exactly 4 and gets your message back to the byte.
  30. 29 bytes in, 32 out: 3 bytes of 0x03, every one of them carrying the count, so the reader at the other end removes exactly 3 and gets your message back to the byte.
  31. 30 bytes in, 32 out: 2 bytes of 0x02, every one of them carrying the count, so the reader at the other end removes exactly 2 and gets your message back to the byte.
  32. 31 bytes in, 32 out: 1 byte of 0x01, every one of them carrying the count, so the reader at the other end removes exactly 1 and gets your message back to the byte.
  33. 32 bytes in, 48 out, and this is the row nobody believes. The message already fills its blocks exactly, so PKCS#7 adds a WHOLE EXTRA BLOCK of 0x10. It has to: the rule is that the last byte always says how many bytes to remove, so a message ending in 0x10 by accident and one padded with 16 bytes of 0x10 must be told apart, and only an unconditional pad can do it.

Step it to sixteen. A message that already fills its block exactly comes out a block longer, sixteen bytes of 10 and nothing else. If an exact fit were left alone, a message ending in 01 could not be told apart from one padded with a single 01, and unpadding would be guesswork. Unconditional padding is what makes it arithmetic.

And the receiver must not say which check failed. Somebody who can tell bad padding from a bad message — by the error, or by how long the refusal took — reads the message back a byte at a time without ever holding the key.

So chaining costs three obligations — an IV that is fresh and unguessable, a padding scheme applied without exception, and a receiver that never says why it refused — and buys the end of the block-equality leak. It is a real improvement and it is still not enough. The next chapter asks whether the cipher needs to touch the message at all.

Part III · In the world

14 A keystream

Chaining fixed the leak and left a bill: encryption that cannot start block two until block one is finished, a padding scheme that adds a whole block to a message that already fits, and an inverse cipher to write, test and keep constant-time. Counter mode pays none of it, by declining to put the message into the cipher at all.

Figure 19 · Counter mode, and the wire that moves

CBC · the message goes into the cipher

the message goes in · decryption needs the inverse

Nothing has been encrypted yet. The wiring first: which register the cipher’s input port is plugged into is the whole difference between the two modes, and it is the only thing that changes when the wire moves.

In counter mode, what goes into the AES box?
3 steps · every block of this run, as text
  1. Block 1: the counter block goes through AES, which gives sixteen bytes of keystream, and the plaintext is exclusive-ored with it to give the ciphertext. The cipher runs forwards, and the message never enters it.
  2. Block 2: the counter block goes through AES, which gives sixteen bytes of keystream, and the plaintext is exclusive-ored with it to give the ciphertext. The cipher runs forwards, and the message never enters it.
  3. Block 3: the counter block goes through AES, which gives sixteen bytes of keystream, and the plaintext is exclusive-ored with it to give the ciphertext. The cipher runs forwards, and the message never enters it. This block is 4 bytes, not sixteen, so only the first 4 bytes of the keystream are used and the rest is thrown away. Nothing is padded.
7 steps · both wirings in words — three lines of CBC, then four of CTR
  1. Chaining: the previous ciphertext block is exclusive-ored into this plaintext block first.
  2. That sum goes INTO the cipher. The message itself is what AES encrypts, so decryption has to run AES backwards.
  3. What comes out is the ciphertext, and it is also the chain value the next block will use — which is why the blocks cannot be encrypted in parallel.
  4. Counter mode: a counter block goes into the cipher. It is public, it is not the message, and it is drawn heavier because it is the input.
  5. What comes out is keystream — sixteen bytes that depend on the key and the counter and on nothing in the message.
  6. The message goes round the outside of the cipher and is exclusive-ored with the keystream on the far side. It never enters AES at all.
  7. So decryption is the same operation with the same wiring: encrypt the same counter, exclusive-or again. AES-Decrypt is never invoked, and every block can be done at once.

The cipher encrypts a counter block: a public, predictable value that counts up by one for each block. Here it starts at the sixteen bytes you typed — 3243f6a8 885a308d 313198a2 e0370734 — which have been the message since Chapter 1 and are not the message now. What comes out is keystream, sixteen bytes that depend on the key and the counter and on nothing else, and the message is exclusive-ored with it on the way past.

Four things follow, and none of them is a new cryptographic idea. Blocks no longer wait for each other, so a long message encrypts and decrypts in parallel. A short final block uses a short prefix of its keystream and throws the rest away, so there is no padding and the ciphertext is exactly as long as the message. Decryption is the same operation — encrypt the same counter, exclusive-or again — so AES-Decrypt is never invoked, and the whole inverse cipher of Chapter 11 can be left out of an implementation that only ever runs counter mode. Toggle the direction on the figure and only the in and out markers swap. That is the point, and it is why the figure has one trace rather than two.

If that seems too easy, open a counter block. The descent under Figure 19 loads the Chapter 8 machine with the block the cipher actually encrypted, and you can walk all 40 steps of it: 10 rounds, the same S-box, the same round keys. The input state is the counter. The output is the keystream. Your message is in none of it — not as an input, not as an intermediate state, nowhere. The navigation is the proof.

The bill counter mode does present is the nonce, and it is due in full. The keystream depends on the key and the counter alone, so two messages sent under one key with one starting counter are encrypted with the same keystream. Exclusive-or the two ciphertexts together and the keystream — identical in both — cancels exactly, leaving the two plaintexts exclusive-ored with each other. No key is involved in that subtraction and nothing about it gets harder with a longer one.

Figure 19b · One counter, two messages

Two messages

message onecounter A

Meet me at the pier at nine.

message twocounter A, again

Send the money on Wednesday.

The control case: the same two messages, one thing changed.
Two messages go out under the same key and the same counter block. Nothing else has gone wrong: the cipher is correct, the key is secret, and the counter has simply been used twice.
4 steps · the whole recovery, as text
  1. Two messages go out under the same key and the same counter block. Nothing else has gone wrong: the cipher is correct, the key is secret, and the counter has simply been used twice.
  2. Both ciphertexts are 28 bytes and neither reads as anything. Printed as text they are middle dots, because almost nothing in a random byte prints.
  3. Exclusive-oring the two ciphertexts cancels the keystream: it was identical in both, so it subtracts out exactly, and what is left is the two plaintexts exclusive-ored together. No key was used to get here.
  4. Guess the first message — a greeting, an address, a fixed header — and exclusive-or it in, and the second message comes out in full: Send the money on Wednesday.. That is exactly what was typed above.

Guess one message and the other falls out in full. A greeting, a header, a fixed first line — a guess is usually free, and where it is not, the two plaintexts exclusive-ored together are already enough to read both by eye, because English is redundant and noise is not. That is why the counter must never repeat under one key, why a random 96-bit value is the usual answer, and why counter reuse is a real break rather than a weakening.

There is one more thing missing, and the figure above has already shown it without naming it. Turn over a single bit of a counter-mode ciphertext and exactly that bit turns over in the plaintext: no noise, no boundary, nothing broken — an attacker who knows what the message says can edit it without holding the key. Counter mode has no opinion about who wrote the ciphertext it decrypts. Neither does CBC. That is the next chapter.

Part III · In the world

15 And a tag

Every mode so far decrypts whatever it is handed. Change a byte of the ciphertext in transit and CBC returns one block of rubbish and one block you chose the contents of; counter mode returns the message with exactly the bits you picked turned over and nothing else disturbed. Neither has any opinion about who wrote the ciphertext, because neither was given anything to check. GCM is counter mode with something to check.

Figure 20 · GCM's two tracks

Absorb A1 · 1 of 5

the counter track · confidentiality

  • J03243f6a8 885a308d 313198a2 00000001spent on the tag mask, never on data
  • counter 13243f6a8 885a308d 313198a2 0000000207a3263e 52bd7a0e d2260465 0b9a5169
  • counter 23243f6a8 885a308d 313198a2 000000035be353e7 62ed7349 06e4ba44 f4553cf7
  • counter 33243f6a8 885a308d 313198a2 00000004f0b201d7 ae29f408 11ef73d8 db2fa7ad

The data starts at J0 + 1. Only the last four bytes are counted, so the nonce in front of them never moves.

the hash track · authenticity

GF(2^128) · x^128 + x^7 + x^2 + x + 1a different field from Chapter 4’s, and not opened here: the multiplication is real, it is 128 bits wide, and it teaches nothing the first field did not.

  • A1
  • C1
  • C2
  • C3
  • len

Absorption 1 of 5, A1: a block of the extra data goes into the running total. It is authenticated and it is not encrypted — it travels in the clear and the tag still covers it. Recomputed on this page from the block and the running total: it agrees.

the two tracks meet

  • E(J0)9f921d2c 83e4a0d2 04d0806f cf4a5285
  • tag3cf0e90e 13243440 ccbc98eb 4746de56

The running total is exclusive-ored with the encryption of J0 — the counter that was reserved rather than spent on data — and that is the tag. Nothing has been checked against it yet.

Absorption 1 of 5, A1: a block of the extra data goes into the running total. It is authenticated and it is not encrypted — it travels in the clear and the tag still covers it.
6 steps · every absorption and the tag, as text
  1. Absorption 1 of 5, A1: a block of the extra data goes into the running total. It is authenticated and it is not encrypted — it travels in the clear and the tag still covers it.
  2. Absorption 2 of 5, C1: a block of the CIPHERTEXT goes in, not the plaintext. That is what lets a recipient throw a forgery away before decrypting anything.
  3. Absorption 3 of 5, C2: a block of the CIPHERTEXT goes in, not the plaintext. That is what lets a recipient throw a forgery away before decrypting anything.
  4. Absorption 4 of 5, C3: a block of the CIPHERTEXT goes in, not the plaintext. That is what lets a recipient throw a forgery away before decrypting anything.
  5. Absorption 5 of 5, len: one block holding both lengths — the extra data's and the ciphertext's, each as a 64-bit count of bits. Without it, a message and a shorter message with trailing zeros would hash alike.
  6. The running total is exclusive-ored with the encryption of J0 — the counter that was reserved rather than spent on data — and that is the tag. Nothing has been checked against it yet.

There are two tracks and they meet once. The first is counter mode exactly as you left it in Chapter 14, with one addition: the first counter, J0, is reserved. The message starts at J0 + 1, and J0 itself is encrypted to make the mask the tag is finished with. That one-step offset is the detail implementations get wrong, and it is drawn as a struck rung for that reason.

The second track is an accumulator called GHASH. It swallows the associated data, then the ciphertext, then a single block holding both lengths, and each swallow is an exclusive-or followed by a multiplication. Two things about it are worth more than its internals. It hashes the ciphertext, not the plaintext, which is what lets a recipient throw a forgery away before decrypting anything. And the length block is there so that a message and a shorter message with trailing zeros cannot hash alike.

The multiplication happens in a second finite field — 128 bits wide, modulo x^128 + x^7 + x^2 + x + 1 — and this document does not open it. The field rung on Figure 20 is drawn struck for that reason: something real happens there, it is not the field of Chapter 4, and it would cost a chapter to teach and repay nothing. The values on the page are the real ones and the figure recomputes each of them as you step.

AAD is the part people skip. Headers, routing, a message id — anything that has to travel readable but must not be alterable — goes in at the front of the hash and nowhere near the keystream. Here it is from: alice, in the clear on the page and still covered by the tag: change one letter of it and the check fails exactly as if the ciphertext had been edited.

What comes out is sixteen bytes — 3cf0e90e 13243440 ccbc98eb 4746de56 — and they are not secret. They are a claim: this ciphertext and this associated data, under this key and this nonce, are what the sender produced. Verifying is recomputing the claim and comparing, and the comparison has to happen before the plaintext is used for anything at all.

Figure 21 · One flipped bit, put to two modes

As sent

flip

CBC

no check exists
  1. 1Transfer 500 pou·· intact
  2. 2nds to account 1·· intact
  3. 32345678 at noon.·· intact

As sent, and as it arrives when nothing has touched it.

GCM

the tag is checked first
  • sent3cf0e90e 13243440 ccbc98eb 4746de56
  • computed3cf0e90e 13243440 ccbc98eb 4746de56✓ match

Verified: true — the tag recomputed over this ciphertext and this extra data is the tag that was sent.

As sent: three blocks of English, encrypted twice — once with CBC and once with GCM, under the same key.
3 steps · the whole comparison, as text
  1. As sent: three blocks of English, encrypted twice — once with CBC and once with GCM, under the same key.
  2. One bit is turned over in transit: block 1, byte 15, bit 1. Neither the message nor the key has been seen by whoever did it.
  3. block 1 comes back as sixteen bytes of noise, and block 2 comes back with byte 15, bit 1 turned over and nothing else changed. Every other block is untouched, and nothing objects. The tag no longer matches, so GCM refuses the message and returns nothing. Had it decrypted anyway it would have handed back block 1 with byte 15, bit 1 turned over and every other byte intact — a changed message that reads as if it were the one that was sent, which is exactly what the tag is for.

That is the whole argument for authenticated encryption on one screen. CBC hands back a message it has no way of doubting; GCM refuses. And notice what CBC hands back in the block after the damage: not garbage, but a plausible sentence with one character changed, chosen by somebody who never saw the message and does not have the key. Confidentiality without integrity is not most of the job. For anything that arrives from somewhere else, it is a hazard: it produces bytes that look like a message, and something downstream will act on them.

So the rule the last four chapters were building towards is short. Encrypt with an authenticated mode. Never reuse a nonce under one key. Check the tag before you look at the plaintext, and reject rather than repair. Everything else in this part — the penguin, the chain, the keystream — was the demonstration that each of those is a mode failure rather than a cipher failure, and that the cipher in the middle was doing exactly what Part I said it does, the whole time.

Part IV · Limits

16 What actually breaks AES

AES was standardised in 2001 and has been the most heavily analysed block cipher in the world ever since. It is not broken. The best published attack on the full cipher, a biclique attack, recovers an AES-128 key in about 2126.1 encryptions rather than 2128. Whether that is alarming depends on what 2128 is, and thirty-nine digits will not tell you.

So: one axis, in bits, with the cipher’s own 128 drawn through it as a rule. Each rung is an attacker or an energy budget, and each is arithmetic over one stated assumption — a rate, a joule figure, a density — chosen to be generous to whoever is attacking you. This ladder is drawn for AES-128; at 192 or 256 the rule would sit right of everything below it and no rate or energy bar would move, because what an attacker can reach does not depend on how much there is to search.

Figure 22 · Two to the 128, in bits

The key space

  1. The key space2 to the power 128
  2. One core, since the Big Bang2 to the power 88.5
  3. An exascale machine, since then2 to the power 118.4
  4. The largest machine ever built2 to the power 128.4
  5. A year of sunlight on Earth2 to the power 118.7
  6. The thermodynamic floor2 to the power 137.3
  7. One atom per key2 to the power 128
  8. The best known attack2 to the power 126.1
An AES-128 key is one of 340,282,366,920,938,463,463,374,607,431,768,211,456. Thirty-nine digits tell you almost nothing, so everything below is measured in bits instead, against the rule drawn at the cipher.
8 steps · the whole ladder as text
  1. An AES-128 key is one of 340,282,366,920,938,463,463,374,607,431,768,211,456. Thirty-nine digits tell you almost nothing, so everything below is measured in bits instead, against the rule drawn at the cipher.
  2. A single core testing a billion keys a second, started at the Big Bang and still running, would have reached one key in every 781 billion. Pointed forwards it finishes in 1.1 times ten to the power 22 years.
  3. A billion billion encryptions a second — an exascale machine with every transistor spent on this one job — covers one key in 781 over the same run. A billion times the machine bought thirty bits.
  4. The Bitcoin network computes a thousand billion billion hashes a second, and is the largest sustained computation ever assembled. An AES engine that size, started at the Big Bang, would have finished with billions of years to spare: 11 billion years, one key.
  5. Then the power bill. At ten picojoules an encryption — better than any AES engine built — a year of all the sunlight falling on the Earth buys one key in 623, so the search wants 623 years of every photon. A year of human energy production buys one in 5.5 million.
  6. Erasing one bit costs at least kT ln 2, about 2.9 zeptojoules at room temperature. Stated honestly, that floor is not the wall at 128 bits: a year of world energy pays for the whole key space in bit erasures 635 times over. It is the wall at 256.
  7. Counting is not the barrier either. One iron atom per key is a cube 1.6 kilometres on a side, and the observable universe holds 2 to the power 266 atoms. This is a large number next to what can be done, not next to what exists.
  8. Biclique cryptanalysis, 2011, recovers an AES-128 key in about 2 to the power 126.1 encryptions, and wants 5 billion exabytes of chosen plaintext to do it. At this scale the saving is a hair’s breadth: a factor of 3.7.

2128 is not beyond machines: an engine the size of the largest computation humanity has assembled, started at the Big Bang, would have finished, with three billion years to spare. What it is beyond is time — and buying time back multiplies the power bill by exactly what it divides the years by. That is why the honest bound is energy rather than counting, and why the thermodynamic argument, airtight at 256 bits, does not carry at 128.

Against a number like that, the biclique result is a factor of 3.7 — a real advance in cryptanalysis and of no consequence to anybody using AES.

None of which is how AES gets broken in practice, because in practice nobody attacks the cipher. They attack the program running it.

Chapter 3’s lookup table is the classic hole. A software implementation reads S[a ⊕ k] — an address that depends on the key — and the cache remembers which lines it fetched. A process sharing the machine can measure that; so, in Bernstein’s 2005 result, can a client timing a server across a network. Either recovers the key without touching a round. The answer was to stop looking things up: AES-NI and the ARMv8 cryptographic extensions, shipping since 2010 and 2013, do a whole round in one instruction, with no table and no key-dependent address, and where there is no such instruction, bitsliced code computes the S-box from Chapter 4’s field arithmetic instead. Constant time is not an optimisation here; it is the requirement.

The rest of the list this document has already shown you. A round key is not a hint about the key — at AES-128 it is the key, and Chapter 9’s inverter runs the schedule backwards from any single round, so a round key in memory is a key in memory. A counter used twice under one key hands over the difference between two messages in the clear: Chapter 14. Encrypting without authenticating lets somebody who never learns your key rewrite your plaintext: Chapters 13 and 15. And the mode you reach for without thinking decides whether your ciphertext is noise or a picture of a penguin: Chapter 12.

That is the honest close. The mechanism you have assembled does what it was built to do: one flipped bit reaches all sixteen bytes in two rounds, and twenty-five years of public cryptanalysis have taken two bits off a search of 1038. Everything that has actually gone wrong went wrong around it — a table lookup, a repeated counter, a missing tag, a key left where it could be read. AES is the part you do not have to worry about.