Lecture 20: What is a Block Cipher? A Look Inside AES (Advanced Encryption Standard)

Sequentia Explores: The Mathematics of Crypto

Part III: Historical Ciphers & the Dawn of Cryptanalysis

Lecture 20: What is a Block Cipher? A Look Inside AES (Advanced Encryption Standard)

In our last lecture, we learned about the two fundamental actions of modern symmetric encryption: substitution (swapping data) and permutation (shuffling data). We saw that when combined in multiple “rounds,” these simple operations can create immense complexity and security.

Today, we’re going to see how these principles are applied in the real world by looking at the reigning champion of symmetric encryption: the Advanced Encryption Standard (AES). To understand AES, we first need to understand the category of ciphers it belongs to: block ciphers.

Stream Ciphers vs. Block Ciphers

Historically, many ciphers were stream ciphers. They encrypt data one unit at a time (e.g., one letter or one bit) as it comes. Think of a continuous stream of data flowing through an encryption machine.

Block ciphers, on the other hand, operate differently. They chop the plaintext up into fixed-size chunks, called blocks, and encrypt each block as a single unit.

• If your message is “THIS IS A SECRET MESSAGE,” a block cipher might break it into 16-byte blocks.
• Block 1: “THIS IS A SECRET”
• Block 2: ” MESSAGE” (with padding added to fill the block)
• The encryption algorithm is then applied to Block 1, and separately to Block 2, and so on.

AES is the most famous and widely used block cipher in the world. It was selected by the U.S. National Institute of Standards and Technology (NIST) in 2001 after a multi-year public competition to find a secure and efficient replacement for the older Data Encryption Standard (DES). Today, AES is used to secure everything from your Wi-Fi (WPA2/3) and secure websites (HTTPS/TLS) to encrypted files and government communications.

A High-Level Look Inside AES

The goal here is not to memorize every technical detail of AES, but to build a conceptual model of how a modern, secure block cipher works.

AES operates on blocks of 128 bits (16 bytes). It can use keys of different sizes: 128, 192, or 256 bits. The key size determines the number of rounds the algorithm will perform:

• AES-128: 10 rounds
• AES-192: 12 rounds
• AES-256: 14 rounds

Let’s imagine our 128-bit (16-byte) block of plaintext arranged in a 4×4 grid of bytes, which cryptographers call the State.

The encryption process for one block looks roughly like this:

1. Initial Key Addition: The first step is to simply mix our plaintext block with a part of the secret key. This is done using a simple bitwise operation (XOR). This prevents an attacker from knowing the input to the first round, even if they know the plaintext.
2. The Main Rounds (Repeated 9 times for AES-128): Now, the block enters the main loop, where it is thoroughly scrambled through a series of four distinct transformations, each designed to provide substitution or permutation.
   • a) SubBytes (Substitution): Each of the 16 bytes in our State grid is swapped for a different byte according to a predefined lookup table called the S-box. This is the primary substitution step, providing confusion. The S-box is carefully designed with complex mathematical properties to be highly non-linear and resistant to analysis.
   • b) ShiftRows (Permutation): The rows of our 4×4 State grid are cyclically shifted. The first row isn’t shifted, the second row shifts one byte to the left, the third shifts two bytes, and the fourth shifts three bytes. This is a permutation step that shuffles the data vertically, providing diffusion.
   • c) MixColumns (Permutation): The columns of our State grid are then mixed. Each column is treated as a polynomial and multiplied by a fixed polynomial in a finite field (specifically GF(2^8)). Don’t worry about the deep math here! The important takeaway is that this is another, more complex permutation step that mixes the data within each column. This provides powerful diffusion.
   • d) AddRoundKey: The block is then mixed with a different part of the secret key (a unique “round key” is generated from the main key for each round).
3. The Final Round (Slightly Different): The final round is the same as a main round, but it omits the MixColumns step. This is for mathematical reasons that ensure the decryption process can work as a clean inverse.

After 10 rounds of these substitution, permutation, and key-mixing operations, the initial plaintext block has been transformed into a block of ciphertext that has no discernible statistical relationship to the original. This is the avalanche effect in action—a change of a single bit in the input results in a completely different output.

Why This Structure Works: The S-P Network

This design, where layers of Substitution are followed by layers of Permutation, is a classic cryptographic structure known as a Substitution-Permutation Network (S-P Network). It was one of Claude Shannon’s foundational ideas.

• Substitution (S-boxes) provides the non-linear confusion, breaking the statistical links between plaintext and ciphertext.
• Permutation (ShiftRows, MixColumns) provides the diffusion, spreading the influence of each bit across the entire block.

By repeatedly applying these two simple-in-principle but complex-in-practice actions over multiple rounds, AES builds a level of security that is, with current and foreseeable technology, unbreakable by brute-force or known cryptanalytic attacks.

We have come a long way from the Caesar cipher’s simple shift. The AES algorithm is a testament to decades of cryptographic research, a public, well-scrutinized system that relies on the simple principles of substitution and permutation, layered to create immense complexity, all guided by a single secret key. It is the perfect embodiment of Kerckhoffs’s Principle in action.