Definition

$C$ and $P$ denote the ciphertext and plaintext blocks, respectively.

Block sizes are typically 64 bits (e.g., DES) or 128 bits (e.g., AES).

Construction

Rounds

A typical block cipher iterates a sequence of rounds:

The round functions execute identical transformations parameterized by different round keys ($K_i$), which breaks symmetry to resist slide attacks.

Substitution-Permutation Networks (SPNs)

An SPN is an iterated cipher architecture that maps an input block through alternating rounds of substitution and permutation layers.

Substitution Layer (S-box) provides non-linear confusion by mapping an $m$-bit input to an $n$-bit output (typically 4-bit or 8-bit lookup tables). For example, given a 4-bit S-box mapping $\text{S} = [3, 8, \text{F}, 1, \text{A}, 6, 5, \text{B}, \text{E}, \text{D}, 4, 2, 7, 0, 9, \text{C}]$, input 0000 maps to 3 (0011), and input 0101 (5) maps to 6 (0110).

Permutation provides linear diffusion by dispersing the output bits across the input of subsequent S-boxes. In modern byte-oriented ciphers, this is implemented as a matrix multiplication over a finite field:

Feistel Schemes

1. Split the block into halves: $P = L_0 \mathbin{\Vert} R_0$.
2. For round $i = 1 \dots n$: $$L_i = R_{i-1}$$ R_i = L_{i-1} \oplus \mathbf{F}(R_{i-1}, K_i) 3. The final ciphertext is $C = R_n \mathbin{\Vert} L_n$.

The Advanced Encryption Standard (AES)

AES Internals

AES operates on a 128-bit block (structured as a $4 \times 4$ byte matrix) with key lengths of 128, 192, or 256 bits (corresponding to 10, 12, and 14 rounds, respectively).

Each standard round consists of four transformations:

1. AddRoundKey: XORs a round key $K_i$ to $s$.
2. SubBytes: Replaces each byte according to S-box.
3. ShiftRows: Cyclically shifts row $i$ to the left by $i$ bytes ($i \in \{0, 1, 2, 3\}$).
   
4. MixColumn: Multiplies each column by a fixed Maximum Distance Separable (MDS) matrix over $\text{GF}(2^8)$. $$\begin{bmatrix} s_0'\\ s_1'\\ s_2'\\ s_3' \end{bmatrix} = M\cdot \begin{bmatrix} s_0\\ s_1\\ s_2\\ s_3 \end{bmatrix} \quad \text{over } \text{GF}(2^8)$$

Notice that the final round omits MixColumns to ensure the decryption algorithm maintains structural symmetry with the encryption algorithm.

AES in Action

Following is an example in Python:

from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from os import urandom

BLOCK_SIZE = 16
KEY_SIZE = 16

# Pick a random 16-byte key using Python's crypto PRNG.
k = urandom(KEY_SIZE)
print(f"k = {k.hex()}")

# Create an instance of AES-128.
aes = Cipher(algorithms.AES(k), modes.ECB())
aes_ecb_encryptor = aes.encryptor()

# Set plaintext p to the all-zero string.
p = bytes([0x00] * BLOCK_SIZE)

# Encrypt plaintext p to ciphertext c.
c = aes_ecb_encryptor.update(p) + aes_ecb_encryptor.finalize()
print(f"enc({p.hex()}) = {c.hex()}")

# Decrypt ciphertext c to plaintext p.
aes_ecb_decryptor = aes.decryptor()
p = aes_ecb_decryptor.update(c) + aes_ecb_decryptor.finalize()
print(f"dec({c.hex()}) = {p.hex()}")

And the Go version:

package main

import (
	"crypto/aes"
	"crypto/rand"
	"encoding/hex"
	"fmt"
	"io"
)

const (
	BlockSize = 16
	KeySize   = 16
)

func main() {
	// Pick a random 16-byte key using Go's crypto PRNG.
	k := make([]byte, KeySize)
	if _, err := io.ReadFull(rand.Reader, k); err != nil {
		panic(err)
	}
	fmt.Printf("k = %s\n", hex.EncodeToString(k))

	// Create an instance of AES-128 (cipher.Block provides raw single-block ECB primitives).
	block, err := aes.NewCipher(k)
	if err != nil {
		panic(err)
	}

	// Set plaintext p to the all-zero byte slice.
	p := make([]byte, BlockSize)

	// Encrypt plaintext p to ciphertext c.
	c := make([]byte, BlockSize)
	block.Encrypt(c, p)
	fmt.Printf("enc(%s) = %s\n", hex.EncodeToString(p), hex.EncodeToString(c))

	// Decrypt ciphertext c to plaintext decryptedP.
	decryptedP := make([]byte, BlockSize)
	block.Decrypt(decryptedP, c)
	fmt.Printf("dec(%s) = %s\n", hex.EncodeToString(c), hex.EncodeToString(decryptedP))
}

Modes of Operation

Electronic Codebook Mode (ECB)

ECB encrypts multi-block data by splitting the plaintext $P$ into independent $b$-bit blocks $(P_1, P_2, \dots, P_m)$ and encrypting each block separately with the exact same secret key $K$:

ECB mode is insecure because identical plaintext blocks produce identical ciphertext blocks, leaking structural patterns.

Cipher Block Chaining Mode (CBC)

This initial value of ciphertext is random.

In CBC mode, decryption needs to know the IV used to encrypt, so the IV is sent along with the ciphertext.

With CBC, decryption can be much faster than encryption due to parallelism.

Message Encryption

Message Padding

We use padding to expand a message to fill a complete block by adding extra bytes to the plaintext. Here are the rules for padding 16-byte blocks:

• 1 byte remaining: append 0x0F repeated 15 times.
• 2 bytes remaining: append 0x0E repeated 14 times.
• …
• 15 bytes remaining: append 0x01 once.
• 0 bytes remaining (exact multiple): append a full block of 0x10 (16 in decimal) repeated 16 times.

The decryption steps are as following:

1. Decrypt all the blocks as with unpadded CBC.
2. Make sure that the last bytes of the last block conform to the padding rule: that they finish with at least one 01 byte, at least two 02 bytes, or at least three 03 bytes, and so on. If the padding isn’t valid—for example, if the last bytes are 01 02 03—the message is rejected. Otherwise, decryption strips the padding bytes and returns the plaintext bytes left.

Ciphertext Stealing

CTS “steals” ciphertext bytes from the second-to-last block to fill out the last block, then swaps the order of the final blocks so the total ciphertext length matches the exact length of the original plaintext.

Let the block size be $B = 16$ bytes, and suppose the message has $M$ full blocks plus one final partial block $P_3$ of length $L < 16$ bytes (for example, $L = 4$ bytes).

1. Encrypt and normally using standard CBC chaining to compute the intermediate block:

2. Construct a synthetic 16-byte plaintext block $P^*_3$ by concatenating the actual partial plaintext $P_3$ with the stolen tail bytes:

3. Encrypt $P^*_3$ using standard CBC chained with $C'_{\text{prev}}$:

4. The last ciphertext block $C_3$ takes the unused head bytes from step 2:

5. The output transmitted is $C_1 \mathbin{\Vert} C_2 \mathbin{\Vert} C_3$.

This trick is more complicated but offers a few benefits:

1. Plaintexts can be of any bit length not just bytes.
2. Ciphertexts are exactly the same length as plaintexts.
3. It’s not vulnerable to padding oracle attacks.

Counter Mode (CTR)

CTR encrypts a sequential series of counter blocks to produce a pseudorandom keystream, which is then XORed ($\oplus$) with the plaintext.

1. Each input block to the cipher function $E_K$ is constructed by concatenating a Nonce ($N$) and an incrementing Counter ($Ctr$):

2. Keystream Generation:

3. Encryption:

4. Decryption
   bitwise XOR is self-inverting ($(P \oplus S) \oplus S = P$), decryption uses the exact same keystream and the forward encryption function $E_K$:

CTR can be faster than any other mode.

Cryptanalysis & Attacks

Meet-in-the-Middle Attacks (MitM)

1. The attacker takes a known plaintext $P$.For every possible 56-bit candidate key $k \in \{0, 1\}^{56}$, compute the intermediate value:

   $$M_k = E(k, P)$$

   Store these computed values in a lookup table (hash map) where the key is the 64-bit intermediate state $M_k$ and the value is the candidate key $k$:

   $$\text{Table}[M_k] = k$$

   This phase requires $2^{56}$ encryptions and stores $2^{56}$ entries in memory.

2. The attacker takes the corresponding known ciphertext $C$.For every possible 56-bit candidate key $k' \in \{0, 1\}^{56}$, compute the decrypted middle value:

   $$M'_{k'} = D(k', C)$$

   Check if $M'_{k'}$ exists as a key in $\text{Table}$.If a match occurs ($M'_{k'} == M_k$), the pair $(K_1 = \text{Table}[M'_{k'}], K_2 = k')$ satisfies $E(K_1, P) = D(K_2, C)$ and becomes a candidate key pair.

3. Because the DES block size is 64 bits and the combined key space is 112 bits, there will be approximately $2^{112 - 64} = 2^{48}$ false-positive key pairs that satisfy this equation for a single $(P, C)$ pair.To identify the correct $(K_1, K_2)$, test the candidate pairs against 1 or 2 additional known plaintext-ciphertext pairs $(P_2, C_2)$ until only 1 pair remains.

Padding Oracle Attacks

This attack often happens to CBC padding cipher.

For example, if the attacker want to decrypt $C_2$. Let $X=\mathbf{D}(K, C_2)$.

1. Pick a random block $C_1$ and vary its last byte until the padding oracle accepts the ciphertext as valid. Usually, in a valid ciphertext, $C_1[15] \oplus X[15] = 01$, so you’ll find $X[15]$ after trying around 128 values of $C_1[15]$.
2. Find the value $X[14]$ by setting $C_1[15]$ to $X[15] \oplus 02$ and searching for the $C_1[14]$ that gives correct padding. When the oracle accepts the ciphertext as valid, it means you’ve found $C_1[14]$ such that $C_1[14] \oplus X[14] = 02$.
3. Repeat steps 1 and 2 for all 16 bytes.