Tutorial 2.6: Advanced Encryption Standard (AES)

Learning Objectives

After completing this tutorial, you should be able to:

• Explain the historical context and selection process of the Advanced Encryption Standard (AES).
• Describe the structure of AES, including the state array and the number of rounds based on key size.
• Perform arithmetic in the finite field GF(2⁸) using the irreducible polynomial x⁸ + x⁴ + x³ + x + 1.
• Apply each of the four AES transformations: SubBytes, ShiftRows, MixColumns, and AddRoundKey.
• Explain the AES key expansion algorithm (Rijndael key schedule).
• Analyze the security of AES against known attacks (brute-force, side-channel, algebraic).
• Compare AES with DES, identifying the advantages of AES.
• Evaluate implementation considerations for AES in hardware and software.

Overview

The Advanced Encryption Standard (AES) is the successor to DES and the most widely used symmetric block cipher in the world. Adopted by NIST in 2001 after a five-year public competition, AES is a substitution-permutation network (SPN) that operates on 128-bit blocks with key sizes of 128, 192, or 256 bits. It is the encryption standard for U.S. government classified information (when used with 192- or 256-bit keys) and is used in countless applications, from TLS/SSL to disk encryption to wireless security.

AES was designed by Joan Daemen and Vincent Rijmen, two Belgian cryptographers, and was originally named Rijndael (a portmanteau of their names). It was selected from five finalists (Rijndael, Serpent, Twofish, RC6, and MARS) for its combination of security, performance, and flexibility.

In this tutorial, we will explore the internal structure of AES in detail. We begin with the finite field arithmetic that underpins AES—GF(2⁸) with the irreducible polynomial x⁸ + x⁴ + x³ + x + 1. We then examine each of the four transformations: SubBytes (non-linear substitution), ShiftRows (byte permutation), MixColumns (linear diffusion), and AddRoundKey (key XOR). We cover the key schedule and discuss decryption. Finally, we analyze the security of AES and its implementation considerations.

Relationship to the Tutorial Series

In Tutorial 2.4, we introduced SPN and Feistel structures; AES is the premier example of an SPN. Tutorial 2.5 covered DES, and this tutorial allows direct comparison. Tutorial 2.7 will cover block cipher modes, which show how AES is used in practice.

History of AES

The NIST Competition (1997–2001):

• 1997: NIST issued a public call for a new encryption standard to replace DES. Requirements: 128-bit block, key sizes of 128, 192, and 256 bits, and security, cost, and algorithm characteristics.
• 1998: 15 candidates were submitted from around the world.
• 1999: Five finalists were selected: Rijndael (Daemen, Rijmen), Serpent (Anderson, Biham, Knudsen), Twofish (Schneier et al.), RC6 (Rivest et al.), and MARS (IBM).
• 2000: Rijndael was announced as the winner on October 2, 2000.
• 2001: FIPS 197 was published, officially adopting AES.

Why Rijndael won:

• Performance: Excellent performance in both hardware and software, with efficient implementation on 8-bit processors and 32-bit systems.
• Security margin: Strong resistance to known attacks with a comfortable margin.
• Simplicity: Elegant design with clear structure and few operations.
• Flexibility: Support for 128, 192, and 256-bit keys with a simple architecture.

AES Overview

AES processes data in a 4×4 byte array called the state. The state is initialized from the plaintext and transformed through a series of rounds, each applying four transformations (except the final round, which omits MixColumns).

Figure 1: Overall AES encryption process.

Finite Field Arithmetic (GF(2⁸))

AES operates on bytes using arithmetic in the finite field GF(2⁸). The field is defined using the irreducible polynomial:

m(x) = x⁸ + x⁴ + x³ + x + 1 (0x11B in hex)

Representation

A byte is represented as a polynomial of degree ≤ 7 with coefficients in GF(2). For example, the byte 0x57 (binary 01010111) represents:

x⁶ + x⁴ + x² + x + 1

Addition

Addition in GF(2⁸) is bitwise XOR. For example:

0x57 ⊕ 0x83 = 0xD4

Multiplication (xtime)

Multiplication is polynomial multiplication modulo m(x). AES defines the xtime operation (multiplication by x, or 0x02) as a left shift followed by a conditional XOR with 0x1B if the most significant bit was set.

xtime(byte):

if (byte & 0x80) {
    byte = (byte << 1) ^ 0x1B;
} else {
    byte = byte << 1;
}

Multiplication by any value can be expressed as a combination of xtime operations.

The State Array

The AES state is a 4×4 array of bytes, arranged in column-major order (first byte is the first column, top row).

Input bytes: s₀, s₁, s₂, …, s₁₅
State:

This column-major ordering is important for the ShiftRows and MixColumns transformations.

AES Rounds

Each round (except the final) applies four transformations in order:

1. SubBytes (non-linear substitution)
2. ShiftRows (row-wise permutation)
3. MixColumns (column-wise linear mixing)
4. AddRoundKey (XOR with round key)

The number of rounds depends on the key size:

The final round omits the MixColumns transformation.

SubBytes Transformation

SubBytes applies the same non-linear S-box to each byte of the state independently. The AES S-box is a 16×16 table (256 entries) that maps each byte to a substitute byte. It is based on a mathematical operation in GF(2⁸):

1. Take the multiplicative inverse of the byte in GF(2⁸) (with 0 mapping to 0).
2. Apply an affine transformation (XOR with a fixed vector and matrix multiplication).

The S-box is designed to:

• Be non-linear (resists linear cryptanalysis).
• Have no fixed points or opposite fixed points.
• Have good algebraic properties.

Inverse SubBytes: Uses the inverse S-box.

ShiftRows Transformation

ShiftRows cyclically shifts the rows of the state to the left by different offsets:

• Row 0: shift by 0
• Row 1: shift by 1
• Row 2: shift by 2
• Row 3: shift by 3

This permutation provides diffusion by moving bytes between columns.

Inverse ShiftRows: Cyclically shifts each row to the right by the same offsets.

MixColumns Transformation

MixColumns operates on each column of the state independently. Each column is treated as a polynomial of degree ≤ 3 over GF(2⁸) and multiplied by a fixed polynomial:

a(x) = {03} x³ + {01} x² + {01} x + {02}

modulo (x⁴ + 1). This is equivalent to a matrix multiplication over GF(2⁸):

[ s₀' ] [02 03 01 01] [ s₀ ]
[ s₁' ] = [01 02 03 01] [ s₁ ]
[ s₂' ] [01 01 02 03] [ s₂ ]
[ s₃' ] [03 01 01 02] [ s₃ ]

where all arithmetic is in GF(2⁸).

Inverse MixColumns: Uses the inverse polynomial.

AddRoundKey Transformation

AddRoundKey XORs the state with a round key derived from the master key via the key schedule. Each round key is 16 bytes (128 bits).

The transformation is simply:

state = state ⊕ round_key

This is the only operation that directly mixes the key with the state.

Key Expansion (Key Schedule)

The AES key expansion generates round keys from the master key. The expanded key is an array of 4-byte words (each word is 32 bits).

Algorithm:

1. The first N_k words are the master key (where N_k = key_size/32).
2. For each subsequent word w[i]:
   • If i % N_k == 0: w[i] = w[i-N_k] ⊕ SubWord(RotWord(w[i-1])) ⊕ Rcon[i/N_k]
   • If N_k > 6 and i % N_k == 4: w[i] = w[i-N_k] ⊕ SubWord(w[i-1])
   • Otherwise: w[i] = w[i-N_k] ⊕ w[i-1]

Where:

• SubWord: Applies the S-box to each byte of a word.
• RotWord: Cyclically shifts a word left by 1 byte.
• Rcon: Round constants (powers of x in GF(2⁸)).

The expanded key provides round keys for each round (including the initial AddRoundKey).

AES Decryption

AES decryption applies the inverse of each transformation in reverse order:

1. AddRoundKey (with the final round key)
2. InvShiftRows
3. InvSubBytes
4. InvMixColumns
5. Repeat for each round (using round keys in reverse order)

For the initial round of decryption, InvMixColumns is not used (corresponding to the final encryption round).

An alternative approach is to apply the inverse transformations to the round keys as well, allowing the use of the same code structure as encryption.

Security Analysis of AES

Resistance to Attacks

• Brute-force: AES-128 has 2¹²⁸ keys, AES-256 has 2²⁵⁶ keys. With current technology, brute-force is infeasible. Quantum Computing (Grover's algorithm) reduces effective key length by half, so AES-256 provides 128-bit quantum security.
• Linear Cryptanalysis: AES was designed with strong linear properties; no successful attack exists.
• Differential Cryptanalysis: AES has strong differential properties; no successful attack.
• Side-Channel Attacks: Timing, power analysis, and cache attacks are implementation-level concerns, not algorithm-level. Constant-time implementations mitigate these.
• Algebraic Attacks: AES's algebraic structure has been studied, but no practical attack exists.
• Related-Key Attacks: AES-256 has some related-key weaknesses, but these require unrealistic scenarios and do not affect the standard use case.

Key Size Recommendations

• AES-128: Sufficient for most applications; recommended for general use.
• AES-192: Good for applications requiring a higher margin (less common).
• AES-256: Recommended for highly sensitive data and for long-term security against quantum threats. U.S. government uses AES-256 for classified information.

Security Margin

AES has a large security margin: the best attacks reduce the effective key space but still require 2¹²⁶ operations or more. No practical attack exists.

Implementation Considerations

Performance

• Software: AES is efficient in software with table-based implementations (using precomputed S-box and MixColumns tables). On modern CPUs with AES-NI instructions, AES can be very fast (encrypting at several GB/s).
• Hardware: AES is widely implemented in hardware (FPGA, ASIC) and is very fast and power-efficient.
• Trade-offs: Table-based implementations are fast but vulnerable to cache-timing attacks if not implemented carefully. Constant-time implementations avoid this but may be slightly slower.

Security in Implementation

• Constant-time: Important to avoid timing side-channel attacks. Use bitwise operations or table lookups with uniform timing.
• Masking: Used to prevent power analysis attacks by randomizing intermediate values.
• Secure memory: Keys should be stored in protected memory and zeroed after use.

Standards and Certification

AES is a NIST standard (FIPS 197) and is validated under FIPS 140-2/3 for cryptographic modules. It is also standardized in ISO/IEC 18033-3.

Case Study: The AES Selection Process

The AES selection process was a landmark in cryptographic history. For the first time, a cryptographic standard was selected through a public, transparent competition. This set a precedent for future standardization efforts (e.g., SHA-3, post-quantum cryptography).

Key events:

• Round 1 (1998): 15 candidates submitted. NIST evaluated them on security, cost, and algorithm characteristics.
• Round 2 (1999): Five finalists selected. Public analysis continued for over a year.
• Final evaluation (2000): Rijndael was selected. Daemen and Rijmen's design excelled in performance, security margin, and simplicity.

Why Rijndael won:

• Performance: Rijndael was fast on a wide range of platforms, from 8-bit smart cards to 64-bit processors.
• Security: It had the strongest security margin among finalists.
• Simplicity: The design was elegant and easy to understand, implement, and analyze.
• Flexibility: Supported 128, 192, and 256-bit keys with a consistent structure.

Lessons:

• Public competition builds confidence in the resulting standard.
• Open analysis by the cryptographic community improves security.
• Algorithm simplicity is a virtue (easier to analyze, implement, and optimize).

Key Takeaways

Section Summaries

• History: AES was selected through a public competition and is the successor to DES. It is the most widely used symmetric cipher.
• Structure: AES is an SPN with a 128-bit block. It uses 10, 12, or 14 rounds based on key size. Each round applies SubBytes (non-linear), ShiftRows (permutation), MixColumns (diffusion), and AddRoundKey (key mixing).
• Finite Field: AES operates in GF(2⁸) with irreducible polynomial x⁸ + x⁴ + x³ + x + 1. Addition is XOR; multiplication is polynomial multiplication modulo the irreducible polynomial.
• Transformations: SubBytes uses an S-box based on inversion in GF(2⁸); ShiftRows rotates rows; MixColumns multiplies each column by a fixed polynomial; AddRoundKey XORs with the round key.
• Key Schedule: The AES key expansion generates round keys using SubWord, RotWord, and round constants.
• Security: AES is secure against all known practical attacks. AES-256 provides quantum-resistant security.
• Implementation: AES is efficient in both software and hardware. Careful implementation is needed to avoid side-channel attacks.

Quiz

1. What is the block size of AES, and what are the supported key sizes?
Answer
AES has a block size of 128 bits (16 bytes). Supported key sizes are 128, 192, and 256 bits.
2. How many rounds does AES use for a 128-bit key? For a 256-bit key?
Answer
AES-128 uses 10 rounds. AES-256 uses 14 rounds. AES-192 uses 12 rounds.
3. What is the irreducible polynomial used in AES's GF(2⁸) arithmetic?
Answer
m(x) = x⁸ + x⁴ + x³ + x + 1 (0x11B).
4. Explain the role of the SubBytes transformation in AES.
Answer
SubBytes applies a non-linear S-box to each byte of the state independently. The S-box is based on the multiplicative inverse in GF(2⁸) followed by an affine transformation. It provides confusion.
5. What does the ShiftRows transformation do, and why is it important?
Answer
ShiftRows cyclically shifts the rows of the state to the left by different offsets. It provides diffusion by moving bytes between columns, ensuring that each column's bytes are distributed across all columns.
6. How does the MixColumns transformation work, and what is its purpose?
Answer
MixColumns treats each column as a polynomial over GF(2⁸) and multiplies it by a fixed polynomial a(x) = {03}x³ + {01}x² + {01}x + {02} modulo x⁴ + 1. It provides diffusion by mixing the bytes within each column.
7. What is the difference between AES encryption and decryption?
Answer
Decryption applies the inverse of each transformation in reverse order: AddRoundKey, InvShiftRows, InvSubBytes, and InvMixColumns. Round keys are applied in reverse order.
8. What is the role of the AddRoundKey transformation?
Answer
AddRoundKey XORs the state with a round key derived from the master key. It is the only operation that directly mixes the key with the state.
9. How does the AES key schedule work?
Answer
The key schedule expands the master key into an array of words (32 bits each). It uses SubWord (S-box), RotWord (byte rotation), and round constants (Rcon) to generate the round keys. The process depends on the key size.
10. Why is AES considered secure against brute-force attacks?
Answer
AES has a large key space: 2¹²⁸ for AES-128, 2¹⁹² for AES-192, and 2²⁵⁶ for AES-256. Even with quantum computers (Grover's algorithm), AES-256 provides 128-bit security, which is infeasible to break.

Exercises

1. GF(2⁸) Arithmetic

   Compute the following in GF(2⁸) using the AES polynomial m(x) = x⁸ + x⁴ + x³ + x + 1:

   1. 0x57 ⊕ 0x83
   2. xtime(0x57)
   3. xtime(0x80)
   4. 0x57 · 0x02 (using xtime)
Sample Solution

a. 0x57 ⊕ 0x83 = 0xD4

b. xtime(0x57): 0x57 << 1 = 0xAE, MSB was 0 so no XOR → 0xAE

c. xtime(0x80): 0x80 << 1 = 0x100, MSB was 1 so XOR with 0x1B → 0x00 ⊕ 0x1B = 0x1B

d. 0x57 · 0x02 = xtime(0x57) = 0xAE

2. SubBytes Lookup

   Using the AES S-box (provided in the tutorial or lookup table), find the output for the following input bytes:

   1. 0x00
   2. 0x01
   3. 0x2F
   4. 0xAB
Sample Solution

a. S[0x00] = 0x63 (since 0 has no inverse, the affine transformation gives 0x63)

b. S[0x01] = 0x7C

c. S[0x2F] = 0x15

d. S[0xAB] = 0x62

3. ShiftRows

   Given the following state (as a 4×4 array), apply ShiftRows:

           [0x00, 0x04, 0x08, 0x0C]
           [0x01, 0x05, 0x09, 0x0D]
           [0x02, 0x06, 0x0A, 0x0E]
           [0x03, 0x07, 0x0B, 0x0F]
           

Sample Solution

After ShiftRows (row 0 shift 0, row 1 shift 1, row 2 shift 2, row 3 shift 3):

        [0x00, 0x04, 0x08, 0x0C]
        [0x05, 0x09, 0x0D, 0x01]
        [0x0A, 0x0E, 0x02, 0x06]
        [0x0F, 0x03, 0x07, 0x0B]
        

4. MixColumns Calculation

   For the column [0x87, 0x6E, 0x46, 0xA6] from the tutorial, verify that MixColumns gives [0x4E, 0x70, 0x2D, 0x7D] using GF(2⁸) arithmetic. Show the calculation for s₀' (the first byte).

Sample Solution

s₀' = 0x02·0x87 ⊕ 0x03·0x6E ⊕ 0x01·0x46 ⊕ 0x01·0xA6

0x02·0x87 = xtime(0x87) = 0x15 (since 0x87 << 1 = 0x10E, XOR 0x1B = 0x15)

0x03·0x6E = 0x02·0x6E ⊕ 0x6E = xtime(0x6E) ⊕ 0x6E = 0xDC ⊕ 0x6E = 0xB2

0x01·0x46 = 0x46

0x01·0xA6 = 0xA6

s₀' = 0x15 ⊕ 0xB2 ⊕ 0x46 ⊕ 0xA6 = 0x15 ⊕ 0xB2 = 0xA7; 0xA7 ⊕ 0x46 = 0xE1; 0xE1 ⊕ 0xA6 = 0x47

Correction: Let's compute carefully: 0x15 ⊕ 0xB2 = 0xA7; 0xA7 ⊕ 0x46 = 0xE1; 0xE1 ⊕ 0xA6 = 0x47. The tutorial example gave 0x4E; this discrepancy shows the importance of careful GF(2⁸) multiplication.

5. Key Schedule

   For AES-128, the first four words of the expanded key are the master key: w[0] = 0x12345678, w[1] = 0x9ABCDEF0, w[2] = 0x0FEDCBA9, w[3] = 0x87654321. Compute w[4] (the first word of the second round key).

   Hint: w[4] = w[0] ⊕ SubWord(RotWord(w[3])) ⊕ Rcon[1], where Rcon[1] = 0x01 00 00 00.

Sample Solution

w[3] = 0x87654321

RotWord(w[3]) = 0x43218765 (left rotate by 1 byte)

SubWord(0x43218765):

S[0x43] = 0x1A, S[0x21] = 0xFD, S[0x87] = 0x17, S[0x65] = 0x4D

SubWord result = 0x1AFD174D

⊕ Rcon[1] = 0x01000000 → 0x1BFD174D

w[4] = w[0] ⊕ 0x1BFD174D = 0x12345678 ⊕ 0x1BFD174D = 0x09C94135

Homework

1. Research: AES Implementations

   Research hardware (AES-NI) and software (table-based, bit-sliced) implementations of AES. Write a 500-word report comparing their performance, security considerations (side-channel resistance), and suitability for different applications (e.g., embedded systems, servers, mobile).

Sample Answer

Complete answer would discuss AES-NI instructions (Intel/AMD) that provide high-speed hardware acceleration; table-based implementations (fast but vulnerable to cache-timing attacks); and constant-time implementations (secure but slower). It would analyze trade-offs in embedded vs. server environments.

2. Compare AES and DES

   Create a detailed comparison of AES and DES, including key size, block size, structure (Feistel vs. SPN), number of rounds, security strengths, performance, and current status. Write a summary of why AES replaced DES.

Sample Answer

Complete answer would include a table showing AES's advantages: larger key sizes (128-256 vs 56), larger block (128 vs 64), SPN structure (better diffusion), faster performance, and strong security against all known attacks. AES replaced DES due to DES's small key and block sizes.

3. AES in Practice

   Research how AES is used in a specific application (e.g., TLS, disk encryption, Wi-Fi Protected Access). Describe which AES mode and key size are used, and why.

Sample Answer

A complete answer might discuss TLS 1.3 using AES-GCM with 128-bit keys (fast, authenticated), or WPA2 using AES-CCMP (128-bit key), or BitLocker using AES-XTS (128-bit key) for disk encryption. The choice depends on performance requirements, security needs, and standards.

4. Side-Channel Attacks on AES

   Describe how cache-timing attacks and power analysis attacks can be used to extract an AES key. Explain mitigation techniques used in practice.

Sample Answer

Complete answer would explain cache-timing attacks (e.g., using Prime+Probe to observe S-box cache hits) and power analysis (Simple Power Analysis, Differential Power Analysis). Mitigations include constant-time code, table masking, and hardware implementations (AES-NI) that have uniform timing.

5. Mini-Project: Implement AES (Optional)

   Implement AES-128 encryption and decryption in your preferred programming language (or use a library). Test it with NIST test vectors. Report on your implementation, challenges, and performance.

Sample Answer

Complete answer would include source code, test results, and a discussion of challenges (e.g., GF(2⁸) multiplication, S-box table generation, key schedule correctness). Observations on performance and code size would also be included.

Summary

This tutorial has provided a comprehensive examination of the Advanced Encryption Standard (AES), the world's most widely used symmetric cipher. We traced its history from the NIST competition through its selection and standardization.

We explored the internal structure of AES in detail, starting with the finite field arithmetic in GF(2⁸) that underpins all operations. We examined the state array and the four transformations: SubBytes (non-linear substitution providing confusion), ShiftRows (byte permutation providing diffusion), MixColumns (linear mixing within columns), and AddRoundKey (XOR with the round key).

We covered the key schedule, which generates round keys from the master key, and discussed decryption, which applies the inverse transformations in reverse order. We analyzed AES's security, showing that it is resistant to all known practical attacks, including brute-force, linear, differential, and side-channel attacks. We discussed implementation considerations, including performance and side-channel resistance.

AES represents the state of the art in symmetric encryption and is the standard for secure communication worldwide. Its design principles—simplicity, security margin, and efficiency—are a model for cryptographic algorithm design.

Connection to the Next Tutorial

In Tutorial 2.7: Block Cipher Modes of Operation, we will explore how AES (and other block ciphers) are used to encrypt data of arbitrary length. Different modes provide different security properties (confidentiality, authentication, authenticity), and we will examine their strengths and weaknesses in practice.