Block Ciphers and AES

A block cipher is a function that takes a fixed-size chunk of plaintext and a key, and produces a fixed-size chunk of ciphertext of the same length. The chunk is called a block. For AES the block size is always 128 bits (16 bytes), regardless of the key length.

Plaintext is rarely a tidy 16 bytes long. Real data, files, passwords, packet payloads, comes in arbitrary lengths. The block cipher does not care. The data gets cut into 16-byte chunks. Each chunk is encrypted separately. The chunks are then reassembled in order to form the ciphertext.

The block size never changes. Only the key length and the number of rounds scale up. AES-256 is the recommended default for new systems.

In the late 1990s, the U.S. government realized DES, the workhorse symmetric cipher of the previous quarter-century, was finished. Its 56-bit key was small enough that a custom $250,000 machine called Deep Crack could brute force it in days. NIST ran a five-year open competition. Cryptographers from around the world submitted candidate algorithms. Each candidate was published, attacked, and benchmarked in public.

In October 2000, NIST selected Rijndael, a cipher designed by Belgian cryptographers Vincent Rijmen and Joan Daemen. It was standardized as the Advanced Encryption Standard (AES) in November 2001 as FIPS Publication 197. It has been the dominant symmetric cipher ever since, embedded in TLS, BitLocker, FileVault, signal, WPA2/WPA3, IPSec, SSH, and on and on.

Two key takeaways from the AES selection process:

• The entire process was open. Every submission's specification, source code, and analysis was public.
• After more than two decades of additional public scrutiny, AES remains unbroken. No practical attack reduces it below brute force for the full algorithm.

Before AES operates on a block, it loads the 16 bytes into a 4-by-4 grid called the state. The state is the working canvas. Every operation in AES reads from the state, transforms it, and writes back to the state. After all the rounds complete, the state is read out as the ciphertext block.

The byte order is column-major: bytes 0, 1, 2, 3 fill the first column top to bottom, then bytes 4 through 7 fill the second column, and so on.

AES encrypts a block by running it through a sequence of identical rounds. Each round shuffles, substitutes, and mixes the bytes of the state, then XORs in a round-specific key. The number of rounds depends on the key size.

The first thing AES does to a fresh block is XOR it with the original key. That step is called the initial AddRoundKey. Then it runs Nr−1 main rounds, where Nr is 10, 12, or 14. Then it runs one final round that omits MixColumns (this asymmetry is mathematically necessary to make decryption invertible).

Each round operates on the entire state matrix simultaneously. The four operations are explained next.

SubBytes is a non-linear byte-by-byte substitution. Every one of the 16 bytes in the state is looked up in a fixed table called the S-box, and replaced with the corresponding output byte. The S-box is a 256-entry lookup: any input byte from 0x00 to 0xFF maps to exactly one output byte.

The S-box is designed to be highly non-linear. Small changes to the input byte produce wildly different output bytes. This is the source of AES's resistance to linear and differential cryptanalysis, which are the two most powerful general attacks against block ciphers.

ShiftRows is a positional shuffle. The bytes do not change value. They just move to new positions. The first row stays put. The second row shifts left by one position (with wraparound). The third row shifts left by two. The fourth row shifts left by three.

The point of ShiftRows is to spread the bytes of each column across other columns. SubBytes only operates on bytes in isolation. Without ShiftRows, a column would stay self-contained for the entire encryption. ShiftRows breaks that isolation and gives the next operation, MixColumns, fresh material to mix together.

MixColumns is the diffusion step. It takes each of the four columns and treats it as a four-byte vector. The vector is multiplied by a fixed 4-by-4 matrix in a finite field called GF(2⁸). The result replaces the original column.

The exact math is dense (it uses operations from finite-field arithmetic, not regular multiplication), but the effect is what matters: every byte of the output column depends on every byte of the input column. Change one byte before MixColumns, and all four bytes of that column change after. Combined with ShiftRows from the previous step, a single bit flip in the plaintext block propagates to every byte of the state within two rounds. That is the avalanche effect that makes the cipher strong.

AddRoundKey is where the key actually enters the picture. The current state is XORed byte-for-byte with the round key. XOR is its own inverse, which means the same operation undoes itself during decryption when the same key bytes are reapplied.

Each round uses a different round key, derived from the original key by the key schedule. The key schedule for AES-128 expands the 16-byte master key into 11 round keys (one for the initial AddRoundKey, plus one per round). For AES-256, it produces 15 round keys. Each round key is generated by a deterministic procedure that involves rotations, S-box substitutions, and XORs with round constants.

The four operations were chosen to satisfy two classical cryptographic design principles, identified by Claude Shannon in 1949:

• Confusion: the relationship between the key and the ciphertext should be as complex as possible. SubBytes provides this through its non-linear S-box.
• Diffusion: changing one bit of the plaintext should change roughly half of the ciphertext bits. ShiftRows and MixColumns provide this by spreading any local change across the entire state within a couple of rounds.

Run those four operations 10, 12, or 14 times with a properly derived key schedule, and the resulting ciphertext is, as far as decades of public analysis can tell, indistinguishable from random data without the key. The fastest known attack on AES-128 still requires roughly 2¹²⁶ operations, which is barely better than brute force, and the gap is purely theoretical. For all practical purposes, AES is not breakable by attacking the algorithm. Attackers who beat AES-encrypted systems do so by attacking the key (capturing it, guessing it, exfiltrating it from memory), not the cipher.

AES is a block cipher. It encrypts one 16-byte block at a time. It does not, by itself, tell you:

• How to handle messages that are not a multiple of 16 bytes (the answer is padding, covered next).
• How to chain multiple blocks together so that identical plaintext blocks do not produce identical ciphertext blocks (this is what a mode of operation does, also covered next).
• How to detect whether the ciphertext has been tampered with in transit (this is what authenticated encryption does, covered later).
• How to get the key into the hands of the other party in the first place (key management, also covered later).

A block cipher is one tool, not a complete cryptographic system. Treat AES as the engine. The chassis, transmission, and brakes that turn the engine into a working vehicle are everything else in this track.