Block ciphers

The one-time pad is perfectly secret, but needs a key as long as everything it encrypts. Most encryption today instead uses a short key, 128 or 256 bits, and a block cipher: a function that encrypts a fixed-size chunk of data, a block, at a time. This page builds up what a block cipher is, the two ideas every good one is made of, and then the one almost everything uses: AES.

1 · A shuffle of every block

A block cipher with 4-bit blocks would have 16 possible blocks, 0000 to 1111. Encrypting must turn each into a different block, or two messages would encrypt the same and decryption couldn’t tell them apart. So encrypting just shuffles the 16 blocks, and the key says which shuffle. Decrypting is the shuffle run backwards.

A 4-bit block cipher drawn in full: each block on the left joined to the block it encrypts to. The key (0 to 255) picks the shuffle; change it and every line moves. The message is split into 4-bit blocks (each character is 8 bits, so two blocks), and the lines it uses are highlighted. Its 256 keys give 256 different shuffles (checked in the tests), out of the 20,922,789,888,000 ways there are to shuffle 16 things (16!).

A cipher like this one is easy to break: it’s a substitution cipher on an alphabet of 16, and with 256 keys it can simply be tried every way. Bigger blocks fix both. A real block cipher works on 128-bit blocks, so it shuffles 2¹²⁸ possible blocks, and a table of its shuffle would need 2¹²⁸ rows, about 3.4 × 10³⁸: far more than could ever be stored. So a real cipher doesn’t store its shuffle: it computes it, a block at a time, from the key. Its 128-bit key can pick only 2¹²⁸ of the possible shuffles, a vanishingly small share of them, and the whole art is that the ones it picks look just like shuffles chosen at random.

2 · Confusion and diffusion

In 1949, Claude Shannon named the two things a cipher has to do. Confusion: the link between the key and the ciphertext should be as tangled as possible. Diffusion: every bit of the input should affect every bit of the output, so that patterns in the message are spread out of sight. Modern block ciphers get both by repeating two simple steps many times: substitution, swapping small pieces for others through a table (an S-box), and permutation, moving bits or bytes around so that the next round’s substitutions mix them together.

Why a table, rather than some neat formula? Because the neat formulas are linear: each output bit is just an XOR of some input bits. A linear map has a giveaway: if you know what it does to a and to b, you know what it does to a ⊕ b. Encrypting would then be a set of linear equations in the key’s bits, and a few known blocks give enough equations to solve for the key, the way Berlekamp–Massey solves a linear register on the randomness page.

rows a, columns b: filled where S(a ⊕ b) = S(a) ⊕ S(b) ⊕ S(0)

A 4-bit map (its table above), tested on every pair of inputs a and b: does S(a ⊕ b) = S(a) ⊕ S(b) ⊕ S(0)? (The S(0) allows for a constant added on.) For a linear map the answer is always yes: all 256 squares filled. For an S-box, here the one from the lightweight cipher PRESENT, it holds for only 58 of the 256 pairs, and 46 of those are the top row, left column and diagonal, where it holds for any map at all (a or b is 0, or a = b). That leaves 12 pairs, scattered (both counts pinned in the tests): all an attacker gets.

The S-box is the only part of a cipher like AES that isn’t linear, and it’s where all the confusion comes from. Choosing one is a careful job: how far its table is from every linear map, in exactly this sense, decides how well it resists the attacks on breaking a block cipher.

3 · A Feistel network

Before AES, the standard block cipher was DES (1977), built on an idea of Horst Feistel’s at IBM. A Feistel network splits the block into a left half L and a right half R, and each round does this:

Mix R with the round’s key in a round function F.
XOR the result into L.
Swap the halves.

The trick is that F never has to be undone. Each round leaves R as it was (it only moves to the left), so whoever decrypts can work out F(R) again, XOR it into the other half again, and the XOR undoes itself. So decrypting is the very same rounds, with the round keys in reverse order.

A toy Feistel network on a 16-bit block (two characters, one per half) with four rounds, each using one byte of the 32-bit key. Its F looks R ⊕ key up in AES’s S-box, squares the result and keeps the last 8 bits; its 256 inputs give only 44 different outputs (checked in the tests), so F can’t possibly be undone. The first ladder encrypts. The second puts the ciphertext through the same network with the keys in reverse order: out comes the block again.

DES used 16 rounds like these on 64-bit blocks, with a 56-bit key. The design held up well; the key was its weakness, small enough to be found by trying every key once computers caught up.

4 · AES, step by step

In 1997 the US standards body NIST began a public competition for DES’s successor. The winner, announced in 2000, was Rijndael, by two Belgian cryptographers, Joan Daemen and Vincent Rijmen, and it became the Advanced Encryption Standard, AES, in 2001. It isn’t a Feistel network: every round transforms the whole block. It works on 16 bytes at a time, arranged in a 4 × 4 square called the state, filled column by column. With a 128-bit key there are 10 rounds, and each does four steps:

SubBytes: every byte goes through the S-box. (The S-box isn’t an arbitrary table: it’s the byte’s inverse in a finite field, then a fixed shuffle of its bits.)
ShiftRows: row 1 moves one place to the left, row 2 two places, row 3 three, wrapping round.
MixColumns: each column is mixed, so that every byte of the new column depends on all four of the old one.
AddRoundKey: a round key is XORed in.

Before the first round, a round key is XORed in too, and the last round leaves out MixColumns. The 11 round keys come from the key by the key schedule, which mixes it with the same S-box and a few constants.

AES-128 encrypting one block, a step at a time: the state before and after each step, with the bytes that changed highlighted, and the round key beside each AddRoundKey. It starts with the worked example in the standard, FIPS-197’s appendix B, so every state can be checked against it (after round 1, a4 9c 7f f2 …; the output, 39 25 84 1d …: both checked in the tests). Type in your own key and block, as 32 hex digits or 16 characters.

5 · The avalanche

Diffusion is easy to watch. Encrypt a block, then encrypt it again with one bit flipped, and compare the two after every round. A good cipher’s difference should spread until the two look unrelated: about half of the 128 bits different, as for two random blocks.

Top: how many of the 128 bits differ after every round, for this flip (of the FIPS-197 example’s key and block) and on average over 500 random keys, blocks and bits (measured as the figure starts). Below: the two encryptions after every round, byte by byte; the number in each square is how many of its 8 bits differ. A flipped bit of the block is in one byte after the first key is added; SubBytes keeps it in that byte, ShiftRows moves it, and MixColumns spreads it through a whole column: 4 bytes after round 1. Round 2 spreads those four columns into all 16 bytes: in 2,000 random flips it happened every time (pinned in the tests). From then on about half the bits differ, as for unrelated blocks. Flip a bit of the key instead: the key schedule spreads it too.

So after two rounds every bit of the output depends on every bit of the input. AES does ten, because the attacks on breaking a block cipher can see further than full diffusion: the attacks that beat trying every key by any useful amount reach only some of its rounds, and the rest are its safety margin.

6 · Using AES for real

The AES on this page is written to be read, not to be fast, and it isn’t safe to use: its running time can depend on the data, which is the kind of leak attackers measure. Real software uses a well-tested library, and browsers have one built in.

The same block encrypted by this page’s AES and by the browser’s own (the Web Crypto API’s AES-CBC, whose first block, with an IV of zeros, is plain AES of the block). The defaults are FIPS-197’s AES-128 example from its appendix C. Time them measures both on this machine: this page’s AES for half a second, the browser’s on 16 MB.

The difference in speed is partly that the browser’s code is carefully optimised, and mostly that most desktop and phone processors made in the last decade have AES instructions: one or two instructions do a whole round on the state, in hardware, taking the same time whatever the data.

One block is rarely enough, though. How to use a block cipher on a message of any length, without giving away which blocks repeat, is the subject of modes of operation.

Summary

A block cipher encrypts a block at a time: for each key, it’s a shuffle of every possible block.
Shannon’s confusion and diffusion: tangle the key in, and spread every input bit across the output. Ciphers repeat substitution (S-boxes) and permutation for both.
A linear cipher falls to solving equations; the S-box is what keeps a cipher from being linear.
A Feistel network (DES) decrypts by running the same rounds with the keys reversed, even though its round function can’t be undone.
AES does SubBytes, ShiftRows, MixColumns and AddRoundKey, 10 rounds for a 128-bit key. One flipped bit reaches every byte after two rounds.
Use the browser’s or a library’s AES, never your own.