AES

AES backgroundSearch on YouTubeBookmarkSaved

OriginsSearch on YouTubeBookmarkSaved

It was clear that DES needed a replacement:

• There are theoretical attacks that can break DES.
• Exhaustive key search attacks on DES have been demonstrated.
• Triple DES is possible, but it is slow and has small blocks.

The timeline of the selection:

• US NIST issued a call for ciphers in 1997.
• 15 candidates were accepted in June 1998.
• 5 were shortlisted in August 1999.
• Rijndael was selected as the AES in October 2000.
• AES was issued as the FIPS PUB 197 standard in November 2001.

RijndaelSearch on YouTubeBookmarkSaved

Rijmen and Daemen designed Rijndael in Belgium. It has 128/192/256-bit keys and a 128-bit data block.

AES is an iterative cipher, not a Feistel cipher:

• It processes data as a block of 4 columns of 4 bytes.
• It operates on the whole data block in every round.

The design goals:

• resistance against known attacks
• speed and code compactness on many CPUs
• design simplicity

Comments on AESSearch on YouTubeBookmarkSaved

The deck lists these points about AES:

1. It is an iterative cipher, not a Feistel cipher.
2. The key expands into an array of 32-bit words. Four words make the round key for each round.
3. It uses 4 different stages.
4. It has a simple structure.
5. Only AddRoundKey uses the key.
6. AddRoundKey is a form of Vernam cipher.
7. Each stage is easy to reverse.
8. Decryption uses the keys in reverse order.
9. Decryption recovers the plaintext.
10. The final round has only 3 stages.

AES structureSearch on YouTubeBookmarkSaved

Encryption processSearch on YouTubeBookmarkSaved

The state is the data block of 4 columns of 4 bytes (16 bytes). The key expands into an array of words. The encryption process:

1. The 16-byte plaintext becomes the input state.
2. The initial transformation XORs the state with the round 0 key (AddRoundKey).
3. Rounds 1 to $N-1$ each apply 4 transformations.
4. Round $N$ applies only 3 transformations (it has no MixColumns).
5. The final state is the 16-byte ciphertext.

Each round key has 16 bytes. The number of rounds depends on the key length:

The deck says "9/11/13 rounds": these are the full rounds. The initial key XOR and the incomplete last round come in addition.

Round stagesSearch on YouTubeBookmarkSaved

In each full round, the state goes through:

1. Substitute bytes: byte substitution, with 1 S-box for every byte.
2. Shift rows: a permutation of bytes between groups (columns).
3. Mix columns: a substitution that uses matrix multiplication of groups.
4. Add round key: an XOR of the state with key material.

You can see AES as two alternating steps: XOR with the key, then scramble the data bytes. The design gives fast implementations with XOR and table lookup.

The AES roundSearch on YouTubeBookmarkSaved

The AES round figure shows the 16 state bytes going through the stages:

• SubBytes: 16 S-boxes, one for each byte.
• ShiftRows: bytes move to other columns.
• MixColumns: four $M$ blocks, one for each 4-byte column.
• AddRoundKey: each byte XORs with one round-key byte $r_0 \dots r_{15}$.

The four stagesSearch on YouTubeBookmarkSaved

Substitute bytesSearch on YouTubeBookmarkSaved

Substitute bytes is a simple substitution of each byte:

• It uses one table of 16 x 16 bytes. The table holds a permutation of all 256 8-bit values.
• Each byte of the state is replaced by the byte at row (left 4 bits) and column (right 4 bits).
• Example: byte $\{95\}$ is replaced by the byte in row 9, column 5, which has the value $\{2A\}$.
• The S-box is built with a defined transformation of values in $GF(2^8)$.
• The S-box is designed to resist all known attacks.

Deck example of SubBytes on a full state:

Shift rowsSearch on YouTubeBookmarkSaved

Shift rows is a circular byte shift:

• The 1st row does not change.
• The 2nd row does a 1-byte circular shift to the left.
• The 3rd row does a 2-byte circular shift to the left.
• The 4th row does a 3-byte circular shift to the left.

Decryption inverts this step with shifts to the right. The state is processed by columns, so this step moves bytes between the columns.

Deck example (input is the SubBytes output above):

Mix columnsSearch on YouTubeBookmarkSaved

Mix columns processes each column separately. Each byte is replaced by a value that depends on all 4 bytes in the column. The step is a matrix multiplication in $GF(2^8)$ with the prime (irreducible) polynomial:

$$m(x) = x^8 + x^4 + x^3 + x + 1$$

Each column of the state is multiplied by this fixed matrix:

$$\begin{bmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{bmatrix}$$

Deck example (input is the ShiftRows output above):

The four equations for the first column:

$$\begin{aligned} (\{02\} \cdot \{87\}) \oplus (\{03\} \cdot \{6E\}) \oplus \{46\} \oplus \{A6\} &= \{47\} \\ \{87\} \oplus (\{02\} \cdot \{6E\}) \oplus (\{03\} \cdot \{46\}) \oplus \{A6\} &= \{37\} \\ \{87\} \oplus \{6E\} \oplus (\{02\} \cdot \{46\}) \oplus (\{03\} \cdot \{A6\}) &= \{94\} \\ (\{03\} \cdot \{87\}) \oplus \{6E\} \oplus \{46\} \oplus (\{02\} \cdot \{A6\}) &= \{ED\} \end{aligned}$$

More facts about mix columns:

• You can write each column as 4 equations, one for each new byte in the column.
• Decryption uses the inverse matrix. Its coefficients are larger, so decryption is a little harder.
• An alternative view: each column is a 4-term polynomial with coefficients in $GF(2^8)$. The polynomials are multiplied modulo $(x^4+1)$.
• The coefficients are based on a linear code with maximal distance between codewords.

Add round keySearch on YouTubeBookmarkSaved

Add round key XORs the state with 128 bits of the round key:

• The step works column by column: the four state columns XOR with the four key words $w_i, w_{i+1}, w_{i+2}, w_{i+3}$. In effect, it is a series of byte operations.
• The inverse for decryption is the same step, because XOR is its own inverse. Decryption uses the round keys in reverse order.
• The step is designed to be as simple as possible. It is a form of Vernam cipher on the expanded key.
• The other stages give the complexity and security.

AES arithmeticSearch on YouTubeBookmarkSaved

Finite fieldsSearch on YouTubeBookmarkSaved

• A finite field is a field with a finite number of elements. It is also known as a Galois field.
• The number of elements is always a power of a prime number, written $GF(p^n)$.
• $GF(p)$ is the set of integers $\{0, 1, \dots, p-1\}$ with arithmetic modulo the prime $p$.
• Addition, subtraction, multiplication and division stay inside the field $GF(p)$.
• Example: $GF(2)$ is mod 2 arithmetic.

An irreducible polynomial cannot be factored into polynomials of lower degree over the same field. Thus it is not a product of two non-constant polynomials of smaller degree.

Multiplication in GF(2^8)Search on YouTubeBookmarkSaved

AES uses arithmetic in $GF(2^8)$. Each element is an 8-bit byte. Each bit of the byte is a coefficient of a polynomial of degree 7 or less. Multiplication is done modulo the irreducible polynomial:

$$m(x) = x^8 + x^4 + x^3 + x + 1 = (1\,0001\,1011) = \{11B\}$$

Example 1. $\{02\} \cdot \{87\} \bmod \{11B\}$:

$$x(x^7+x^2+x+1) = x^8+x^3+x^2+x$$ $$(1\,0000\,1110) \oplus (1\,0001\,1011) = (0001\,0101) = x^4+x^2+1 = \{15\}$$

Example 2. $\{03\} \cdot \{6E\} \bmod \{11B\}$:

$$(x+1)(x^6+x^5+x^3+x^2+x) = x^7+x^6+x^4+x^3+x^2+x^6+x^5+x^3+x^2+x$$

The equal terms cancel in pairs ($x^6$, $x^3$, $x^2$), so the result is:

$$x^7+x^5+x^4+x = (1011\,0010) = \{B2\}$$

The degree is less than 8, so no reduction is necessary.

Galois field rolesSearch on YouTubeBookmarkSaved

The deck lists where AES uses Galois field operations:

• SubBytes (substitution layer): the S-box uses algebraic operations in the Galois field. This step adds non-linearity and confusion.
• ShiftRows (permutation layer): a change in one byte affects many bytes in the output. This increases diffusion.
• MixColumns (permutation layer): this step increases diffusion and makes the relation between bytes more complex.
• Key expansion: the key schedule uses modular addition, bitwise XOR and circular shifts on the key bytes.
• Round key addition: in each round, the round key XORs with the data block. XOR is a bitwise operation in the Galois field.

The Galois field operations give AES the confusion and diffusion that a strong cipher needs.

Key expansionSearch on YouTubeBookmarkSaved

Expansion stepsSearch on YouTubeBookmarkSaved

Key expansion takes the 128-bit (16-byte) key and expands it into an array of 44/52/60 32-bit words (for 128/192/256-bit keys).

1. Copy the key into the first 4 words $w_0 \dots w_3$.
2. Make each new word from the previous word and the word 4 places back.
3. In 3 of 4 cases, XOR these two words.
4. For the first word in each group of 4, apply the function $g$ to the previous word first. Then XOR the result with the word 4 places back.

The function $g$ does a 1-byte rotate (RotWord), an S-box substitution of each byte (SubWord) and an XOR with a round constant (Rcon).

Round constantsSearch on YouTubeBookmarkSaved

The round constant is the 32-bit word $\text{Rcon}(j) = [rc_j, 00, 00, 00]$. The byte $rc_j$ doubles in $GF(2^8)$ each time: $rc_1 = 01$ and $rc_j = 02 \cdot rc_{j-1}$, so $rc_j = x^{j-1}$.

After $80$, the doubling needs a reduction: $02 \cdot 80 = 100 \oplus 11B = 1B$. AES-128 uses up to $\text{Rcon}(10)$, because it needs 11 round keys.

Key expansion rationaleSearch on YouTubeBookmarkSaved

The key expansion is designed to resist known attacks. The design criteria:

• knowledge of part of the key is not sufficient to find many more key bits
• an invertible transformation
• fast on a wide range of CPUs
• round constants to break symmetry
• diffusion of key bits into the round keys
• enough non-linearity to hinder analysis
• simplicity of description

Worked exampleSearch on YouTubeBookmarkSaved

The deck expands the key $0f1571c9 \; 47d9e859 \; 0cb7add6 \; af7f6798$. The first step makes $w_4$:

The last round key is $w_{40} \dots w_{43}$ = b48ef352, ba98134e, 7f4d5920, 86261876.

With this key, the plaintext $0123456789abcdeffedcba9876543210$ encrypts to the ciphertext $ff0b844a0853bf7c6934ab4364148fb9$.

Decryption and analysisSearch on YouTubeBookmarkSaved

AES decryptionSearch on YouTubeBookmarkSaved

AES decryption is not identical to encryption, because the steps are done in reverse order. But you can define an equivalent inverse cipher with the same step order as encryption:

• It uses the inverse of each step.
• It uses a different key schedule.

This works because the result does not change when you:

• swap byte substitution and shift rows
• swap mix columns and add (tweaked) round key

In the deck figure, the decryption rounds are: inverse sub bytes, inverse shift rows, inverse mix columns, add round key. The middle round keys ($w[4,7]$ to $w[36,39]$) first go through inverse mix columns. Decryption starts with $w[40,43]$ and ends with $w[0,3]$.

Avalanche exampleSearch on YouTubeBookmarkSaved

The deck encrypts two plaintexts that differ in 1 bit, with the same key as above:

After round 2, about half of the 128 bits differ. The two ciphertexts are $ff0b844a\dots8fb9$ and $612b8939\dots33f0$.

Confusion and diffusionSearch on YouTubeBookmarkSaved

• Confusion makes the relation between the key and the ciphertext as complex as possible. The ciphertext gives no clue about the plaintext.
• The goal of confusion: it must be very hard to find the key, even with many plaintext-ciphertext pairs from the same key. Each ciphertext bit must depend on the whole key. A change of one key bit must change the ciphertext completely.
• Diffusion spreads the statistical structure of the plaintext over the statistics of the ciphertext. If one plaintext bit changes, the ciphertext must change completely, in a pseudorandom way.

ImplementationSearch on YouTubeBookmarkSaved

8-bit CPUSearch on YouTubeBookmarkSaved

AES is efficient on an 8-bit CPU:

• Byte substitution works on bytes with a table of 256 entries.
• Shift rows is a simple byte shift.
• Add round key works with byte XORs.
• Mix columns needs a matrix multiplication in $GF(2^8)$ on byte values. You can simplify it to table lookups and byte XORs.

32-bit CPUSearch on YouTubeBookmarkSaved

AES is also efficient on a 32-bit CPU:

• Redefine the steps to use 32-bit words.
• Precompute 4 tables of 256 words.
• Then each column in each round needs 4 table lookups and 4 XORs.
• The tables need 4 KB of storage.

The designers believe that this efficient implementation was a key factor in the selection of Rijndael as AES.

Quick self-testSearch on YouTubeBookmarkSaved

Why did NIST need a replacement for DES?

There are theoretical attacks on DES, and exhaustive key search attacks were demonstrated. Triple DES fixed the key length, but it is slow and has small blocks.

How many rounds does AES use for each key size, and what is special about the last round?

10/12/14 rounds for 128/192/256-bit keys (9/11/13 full rounds and one last round). There is an initial AddRoundKey before round 1. The last round has only 3 stages: it has no MixColumns.

Which stage uses the key material?

Only AddRoundKey. It is a Vernam-style XOR, and XOR is its own inverse.

SubBytes: what does $\{95\}$ become, and how is the S-box built?

Row 9, column 5 gives $\{2A\}$. The table is a permutation of all 256 byte values. It is built with a defined transformation of values in $GF(2^8)$.

Calculate $\{02\}\cdot\{87\} \bmod \{11B\}$.

The shift gives $1\,0000\,1110$. XOR with $1\,0001\,1011$ gives $0001\,0101 = \{15\}$.

What does ShiftRows do to each row?

Row 0 does not change. Row 1 rotates 1 byte left, row 2 rotates 2 bytes, and row 3 rotates 3 bytes. Decryption rotates to the right.

Why is MixColumns harder for decryption?

Decryption needs the inverse matrix over $GF(2^8)$, and its coefficients are larger.

Key expansion: how many words for each key size, and how is the first word of each group made?

44/52/60 words for 128/192/256-bit keys. The first word of each group of 4 is $w_{i-4} \oplus g(w_{i-1})$. The function $g$ does RotWord, SubWord and an XOR with the round constant.

Give the difference between confusion and diffusion.

Confusion makes the relation between the key and the ciphertext complex, and substitution gives it. Diffusion spreads the plaintext statistics over the ciphertext, and transposition gives it.

How does the 32-bit implementation reduce the work in each round?

It uses 4 precomputed tables of 256 words. Each column in each round then needs 4 lookups and 4 XORs. The tables need 4 KB.