Chapter 2: Symmetric Cryptography¶
Symmetric cryptography uses the same key for both encryption and decryption. It’s orders of magnitude faster than public-key cryptography and forms the workhorse for bulk data encryption. This chapter covers block ciphers, stream ciphers, authenticated encryption, and the formal security definitions that make these claims precise.
2.1 Block Ciphers¶
Definition 2.1 (Block Cipher)
A block cipher with block size \(n\) and key size \(k\) is a family of permutations:
For each key \(K \in \{0,1\}^k\), \(E_K(\cdot)\) is a permutation on \(\{0,1\}^n\) with inverse \(D_K = E_K^{-1}\).
A block cipher is a keyed shuffling function: given the same key, the same input block always produces the same output block, and the mapping is invertible. The key selects one specific permutation from an astronomically large family of possible permutations. Security depends on the key-selected permutation being indistinguishable from a random permutation — an adversary who can’t see the key shouldn’t be able to tell the cipher apart from a random function with access to only a polynomial number of input-output pairs.
2.1.1 Advanced Encryption Standard (AES)¶
AES (FIPS 197, 2001) operates on a \(4 \times 4\) matrix of bytes called the state, over \(\mathbb{F}_{2^8}\).
Parameters:
| Variant | Key Size | Rounds |
|---|---|---|
| AES-128 | 128 bits | 10 |
| AES-192 | 192 bits | 12 |
| AES-256 | 256 bits | 14 |
Round structure (each of \(r-1\) full rounds):
-
SubBytes: Apply S-box (a non-linear substitution in \(\mathbb{F}_{2^8}\)) to each byte independently.
-
ShiftRows: Cyclically shift row \(i\) left by \(i\) positions.
-
MixColumns: Multiply each column by a fixed \(4 \times 4\) matrix over \(\mathbb{F}_{2^8}\).
-
AddRoundKey: XOR state with round key derived from key schedule.
The final round omits MixColumns.
Each of the four operations targets a different cryptographic requirement. SubBytes provides non-linearity: without it, AES would be a linear map over \(\mathbb{F}_2\), and an attacker could solve for the key with a handful of known plaintexts using linear algebra. ShiftRows ensures that bytes from the same column don’t stay together round after round, so a single modified input byte eventually affects all output bytes. MixColumns is the diffusion engine: each output byte depends on all four input bytes in its column, so any single-bit change propagates widely within two rounds (the “avalanche effect”). AddRoundKey binds everything to the secret key.
S-Box construction: Invert in \(\mathbb{F}_{2^8}\) (with \(0 \mapsto 0\)) then apply affine transformation. This provides:
-
Confusion: Non-linear; algebraic degree 7
-
Maximum nonlinearity; no fixed points or complement fixed points
The S-box nonlinearity is measured by how much it deviates from all linear Boolean functions. AES’s S-box achieves the maximum possible nonlinearity for an \(8 \times 8\) bijection, leaving no linear approximation with correlation significantly above \(1/2\), which is the property that blocks linear cryptanalysis. The fixed-point condition (no \(x\) where \(\mathrm{S}(x) = x\), and no \(x\) where \(\mathrm{S}(x) = \overline{x}\)) prevents weak keys that collapse certain cipher states.
2.1.2 AES Security¶
Best known attacks on full AES:
| Attack | Target | Complexity | Notes |
|---|---|---|---|
| Biclique | AES-128 | \(2^{126.1}\) | Marginal improvement over brute force |
| Related-key | AES-256 | \(2^{99.5}\) | Requires related keys — not realistic |
| Side-channel | All | Low | Timing, cache, power attacks |
| Brute force | AES-128 | \(2^{128}\) | Infeasible classically |
| Grover | AES-128 | \(2^{64}\) | Quantum; use AES-256 for quantum resistance |
The related-key attack on AES-256 exploits weaknesses in the key schedule, not in the rounds themselves. In practice it’s irrelevant because no real protocol exposes related keys — the attacker would need to see ciphertexts encrypted under keys related by a known difference, which doesn’t happen in properly designed systems. Side-channel attacks are the real operational threat: a correctly implemented AES-256 in a leaky environment is weaker than a correctly implemented AES-128 on constant-time hardware.
AES Side-Channel Attacks
AES table-based implementations using T-tables are vulnerable to cache-timing attacks (Bernstein 2005). Use AES-NI hardware instructions or bit-sliced implementations for side-channel resistance.
2.1.3 Modes of Operation¶
A block cipher encrypts exactly one block. Modes extend it to arbitrary-length messages.
| Mode | Parallelizable | IV Needed | Auth |
|---|---|---|---|
| ECB | Yes (both) | No | No |
| CBC | Dec only | Yes (random) | No |
| CTR | Yes (both) | Yes (nonce) | No |
| GCM | Yes (both) | Yes (nonce) | Yes |
| CCM | Partial | Yes (nonce) | Yes |
| SIV | Yes | Deterministic | Yes |
The mode of operation is often where implementations go wrong. The cipher itself might be perfect, but the wrong mode choice (ECB), a reused IV (CBC, CTR, GCM), or a missing MAC (CBC without authentication) converts a strong primitive into a broken system. In practice, the rule is simple: use GCM or ChaCha20-Poly1305 for nearly all new applications, and treat anything without built-in authentication as a footgun.
ECB Mode — Never Use
ECB encrypts each block independently with the same key. Identical plaintext blocks produce identical ciphertext blocks, leaking structure. The classic demonstration: encrypting a bitmap image in ECB mode still reveals the image’s outline.
CBC Mode:
The IV must be random and unpredictable; reusing it with the same key is catastrophic.
CBC’s chaining creates a critical asymmetry: encryption must run sequentially (each ciphertext block depends on the previous one), but decryption can run in parallel (you have all ciphertext blocks upfront). This is why CBC was popular for disk encryption before better modes existed — you could read any block without decrypting the whole disk. The IV predictability requirement bites HTTPS in the BEAST attack (2011): CBC in TLS 1.0 used the last ciphertext block of the previous record as the IV, making it predictable and enabling chosen-plaintext attacks against session cookies.
CTR Mode:
Turns a block cipher into a stream cipher; the nonce-counter pair must never repeat.
CTR mode is elegant: the block cipher runs entirely on predictable counter values, so you can precompute the keystream before the plaintext arrives. This makes it ideal for latency-sensitive applications. The catch is that nonce-counter uniqueness is a strict requirement with no tolerance. If the same (key, nonce, counter) combination ever produces the same keystream block twice, any two plaintexts encrypted at those positions are XORed together and recoverable.
GCM (Galois/Counter Mode):
-
Encryption: CTR mode with starting counter 2
-
Authentication: GHASH (polynomial hash in \(\mathbb{F}_{2^{128}}\)) over ciphertext + AAD
-
Output: ciphertext + 128-bit authentication tag
-
Critical: Nonce must be unique per (key, nonce) pair; reuse reveals the keystream and GHASH key
GCM nonce reuse has catastrophic consequences beyond just exposing the keystream. Because GHASH uses a secret polynomial evaluation key \(H = E_K(0^{128})\), and because a nonce-reuse attack lets an attacker recover \(H\) from two (ciphertext, tag) pairs, the attacker can then forge valid authentication tags for arbitrary ciphertexts. This breaks both confidentiality and integrity simultaneously. For applications where nonce management is difficult (e.g., stateless servers, distributed systems), AES-GCM-SIV or AES-SIV provide misuse resistance at modest performance cost.
Example 2.1 (AES-GCM in Python)
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
import os
key = os.urandom(32) # 256-bit key
nonce = os.urandom(12) # 96-bit nonce (unique per key!)
aad = b"Associated data" # Authenticated but not encrypted
aesgcm = AESGCM(key)
# Encrypt
plaintext = b"Secret message"
ciphertext = aesgcm.encrypt(nonce, plaintext, aad)
# ciphertext contains encrypted bytes + 16-byte authentication tag appended
# Decrypt (raises InvalidTag if authentication fails)
recovered = aesgcm.decrypt(nonce, ciphertext, aad)
assert recovered == plaintext
2.2 Stream Ciphers¶
Definition 2.2 (Stream Cipher)
A stream cipher generates a pseudorandom keystream from a key (and nonce), which is XORed with plaintext: \(C = P \oplus \text{KS}\).
Stream ciphers shine in environments where data arrives in a continuous stream, block boundaries are inconvenient, or latency is critical. A hardware sensor sending sensor readings byte-by-byte doesn’t naturally produce 16-byte blocks, and forcing it to buffer up to a block before encrypting introduces unacceptable latency. A well-designed stream cipher handles this naturally. The security burden shifts entirely to nonce uniqueness: the keystream must never repeat, so the nonce must change with each message.
ChaCha20-Poly1305 (RFC 8439):
-
ChaCha20: ARX (Add-Rotate-XOR) based; 20 rounds on \(4 \times 4\) matrix of 32-bit words
-
Poly1305: 128-bit MAC using polynomial evaluation over \(\mathbb{F}_{2^{130}-5}\)
-
Security: 256-bit key; 96-bit nonce; 128-bit tag
-
Advantage over AES-GCM: no hardware instruction dependency; constant time in software
-
Used in: TLS 1.3, SSH, WireGuard
ChaCha20 was designed by Bernstein as a response to RC4’s weaknesses and AES-GCM’s requirement for hardware support. On CPUs without AES-NI (including many ARM processors in mobile devices at the time), AES in software is slow and prone to timing side-channels; ChaCha20 is naturally constant-time because it uses only addition, rotation, and XOR — none of which branch on secret data or access lookup tables. Google adopted ChaCha20-Poly1305 in Chrome for HTTPS connections to mobile users, which is partly why it became a TLS 1.3 mandatory cipher.
Stream Cipher Key/Nonce Reuse
If two plaintexts \(P_1, P_2\) are encrypted with the same key and nonce:
The XOR of ciphertexts is the XOR of plaintexts — both messages are compromised. This is the “two-time pad” failure. Nonces must never repeat.
2.3 Authenticated Encryption (AEAD)¶
Definition 2.3 (AEAD)
An Authenticated Encryption with Associated Data scheme provides both:
-
Confidentiality: ciphertext reveals nothing about plaintext
-
Integrity + Authenticity: any modification of ciphertext or AAD is detected
Interface: \(\mathsf{Enc}(K, N, M, A) \to C\) and \(\mathsf{Dec}(K, N, C, A) \to M\) or \(\perp\).
The “associated data” field is easy to overlook but critical in practice. Consider an encrypted database record where the record ID is stored in plaintext alongside the ciphertext — without authenticating the record ID, an attacker can swap the IDs and cause the server to decrypt record 7’s ciphertext while believing it’s record 3, potentially returning another user’s data. Binding the record ID into the AEAD’s AAD field ensures any such manipulation is detected and rejected.
Always Use AEAD
Never use unauthenticated encryption in practice. Unauthenticated ciphertexts are vulnerable to padding oracle attacks (CBC), bit-flipping attacks, and decryption oracle attacks. TLS 1.3 mandates AEAD; only AES-GCM and ChaCha20-Poly1305 are allowed.
The padding oracle attack deserves explicit attention because it has broken real systems. In CBC mode without a MAC, the server’s error response when decryption fails with a padding error leaks one bit of information per query: does the decrypted last block have valid PKCS#7 padding? An attacker who can observe this error can send crafted ciphertexts and determine the plaintext byte by byte, using roughly \(256\) queries per plaintext byte. The BEAST, POODLE, and Lucky13 attacks all exploit this pattern in different contexts. AEAD eliminates the vulnerability entirely because the authentication tag is checked before any decryption output is returned.
2.4 The Data Encryption Standard (DES) and Triple-DES¶
DES (1977): 64-bit block, 56-bit key, 16 rounds (Feistel network). Brute-forced in 22 hours by the EFF DES Cracker (1998). Do not use.
3DES (Triple-DES): \(C = E_{K_3}(D_{K_2}(E_{K_1}(P)))\) with 3 independent keys — effective security 112 bits (due to meet-in-the-middle). NIST deprecated 3DES in 2023; disallowed after 2024.
DES’s 56-bit key wasn’t an accident of mathematics — it was an engineering decision made under NSA influence that deliberately restricted the key space to what government decryption capabilities of the era could handle. The academic community complained at the time; by 1998 the EFF built the DES Cracker for $250,000 and proved the concern justified. 3DES was a stopgap: it re-uses DES hardware by applying it three times, but the meet-in-the-middle attack means you only get 112 bits of security from 168 bits of key material. Any new system using DES or 3DES should treat it as a bug, not a feature.
2.5 Pseudorandom Functions and Permutations¶
Definition 2.4 (PRF Security)
A function family \(F: \{0,1\}^k \times \{0,1\}^n \to \{0,1\}^m\) is a pseudorandom function (PRF) if no efficient adversary can distinguish \(F_K(\cdot)\) (for random \(K\)) from a truly random function.
Definition 2.5 (PRP Security)
A block cipher \(E_K: \{0,1\}^n \to \{0,1\}^n\) is a pseudorandom permutation (PRP) if it is computationally indistinguishable from a random permutation.
A secure PRP is also a secure PRF (PRP/PRF switching lemma: advantage difference \(\leq q^2/2^n\) for \(q\) queries).
The PRF/PRP distinction matters when analyzing modes of operation. CTR mode uses a block cipher as a PRF (it only calls the cipher in the forward direction, never the inverse), which means its security analysis can use the PRF assumption directly. The birthday bound in the switching lemma is the reason you need to re-key or change nonces well before reaching \(2^{n/2}\) blocks encrypted under one key: for AES with a 128-bit block, this limit is \(2^{64}\) blocks — about \(1.8 \times 10^{19}\) bytes, which sounds large, but high-throughput encrypted links can approach it faster than you’d expect.
Exercises¶
Exercise 2.1
Encrypt the ASCII string "HELLO" (padded to 16 bytes) with AES-128 in ECB mode using key \(K = \texttt{0x00}^{16}\). Then encrypt with CBC using a random IV. Explain why ECB is insecure for structured data.
Exercise 2.2
Prove that GCM encryption is not secure if nonces are repeated: given two GCM ciphertexts \((C_1, T_1)\) and \((C_2, T_2)\) encrypted under the same key \(K\) and nonce \(N\), show how to recover the GHASH key \(H\).
Exercise 2.3
A developer encrypts a 32-byte message with AES-128-CBC without appending a MAC. An attacker intercepts and modifies the last 16 bytes of the ciphertext. Describe exactly what the decrypted plaintext looks like. How does AES-GCM prevent this?
Exercise 2.4
Compare ChaCha20-Poly1305 and AES-256-GCM on: (a) security level, (b) performance on systems without AES hardware instructions, (c) nonce misuse resistance, (d) suitability for TLS 1.3.
Exercise 2.5 (Security Proof Sketch)
Define IND-CPA security for a symmetric cipher. Prove that CTR mode instantiated with a PRF is IND-CPA secure, given that nonces are chosen randomly. What is the probability of nonce collision for \(q\) encryptions with 96-bit nonces?