Chapter 1 · Lectures 1 to 4
Secret-Key Cryptography
Secret-key cryptography begins with two parties who share a key. This chapter develops the tools that follow: perfect secrecy and its cost, AES (Advanced Encryption Standard), block-cipher modes, security games, authentication, hashing and authenticated encryption. It closes with the boundary of Minicrypt.
Lecture 1 (23/09/25) is sections 1 to 3: the methodology of provable security, perfect secrecy, Shannon's bound, the one-time pad. Lecture 2 (26/09/25) is sections 4 to 6: AES (Advanced Encryption Standard), the modes of operation, Chosen-Plaintext Attack (CPA) security. Lecture 3 (30/09/25) is sections 7 to 9: Message Authentication Codes (MACs), Cipher Block Chaining MAC (CBC-MAC), collision-resistant hashing and the birthday bound. Lecture 4 (02/10/25) is sections 10 to 13: Merkle-Damgård, the sponge and SHA-3 (Secure Hash Algorithm 3), Hash-Based Message Authentication Code (HMAC), Chosen-Ciphertext Attack (CCA) security and authenticated encryption. The Minicrypt tour (section 14) is in this deck but was taught in Lecture 5 (07/10/25). Study plans: Lecture 1, Lecture 2, Lecture 3, Lecture 4, Lecture 5.
Section 1Modern Cryptography, and How It Argues
Lecture 1.
A secure system draws on many areas: mathematics, physics, computer science, networking and law. Cryptography is the part this course treats, with physical security, governance and implementation quality built around it.
For most of its history cryptography was an art of clever designs. The Caesar cipher, ENIGMA and the one-time pad were each proposed and each measured by how long they resisted ad hoc attack. Modern cryptography, built from the 1980s on by Goldwasser, Micali, Goldreich and others, turned the subject into a science with a repeatable method:
- State a precise definition of what it means for the scheme to be secure.
- Propose a construction.
- Prove that any attack violating the definition would solve a problem assumed hard.
A scheme is accepted because an attack would solve a problem believed hard. When a scheme falls, the failure identifies a gap in the definition, which is then strengthened to exclude that attack.
The running setting of this chapter is secret-key encryption. Alice wants to send a message $m$ to Bob over a channel Eve can listen to, and later modify. Alice and Bob first share a secret key $k$. Encryption turns $m$ into a ciphertext $c = \Enc(k, m)$; decryption recovers $m = \Dec(k, c)$. Correctness requires
$$\Dec\big(k, \Enc(k, m)\big) = m \qquad \text{for every } m.$$Kerckhoffs's principle fixes where the secrecy lives: the algorithms $\Enc$ and $\Dec$ are public, and security rests on the key alone. Algorithms are large, hard to keep secret and slow to change once leaked; a key is small and can be redrawn.
The adversary is modeled as a probabilistic polynomial-time machine: it flips coins. Its running time is bounded by a polynomial in the security parameter $\lambda$. The parameter indexes the key length and the adversary's budget at once. Success must be negligible:
$$\negl(\lambda) < \frac{1}{p(\lambda)} \quad \text{for every polynomial } p \text{ and all large enough } \lambda.$$The function $2^{-\lambda}$ is negligible; $1/\lambda$ is not. An advantage of $1/\poly(\lambda)$ is a break. An advantage of $\negl(\lambda)$ is noise.
Security depends on the definition. Perfect secrecy, indistinguishability under chosen-plaintext attack, unforgeability and collision resistance are each a game with a winner. Each construction below is measured against its game. The sections follow the history: a weak definition is stated, a scheme satisfies it, an attack outside the definition appears and the definition is strengthened.
Modern cryptography argues in three steps: definition, construction, proof. The adversary is polynomial time, success is negligible and the key is the only secret.
Section 2Perfect Secrecy, and Why It Costs Too Much
Lecture 1.
The strongest guarantee an encryption scheme can give makes no assumption about the adversary's computing power. Shannon stated it in 1949: the ciphertext reveals nothing about the plaintext.
An encryption scheme over message space $\mathcal{M}$ is perfectly secret if for every distribution over $\mathcal{M}$, every $m \in \mathcal{M}$ and every ciphertext $c$ with $\Pr[C = c] > 0$,
$$\Pr[M = m] = \Pr[M = m \mid C = c].$$The posterior equals the prior: observing $c$ changes no belief about which message was sent. Equivalently, the ciphertext distribution is independent of the plaintext.
The definition is information-theoretic and unconditional: it holds against an unbounded adversary. It is achievable. The cost is unconditional too.
If a perfectly secret scheme has message space $\mathcal{M}$ and key space $\mathcal{K}$, then $\abs{\mathcal{K}} \ge \abs{\mathcal{M}}$: the key is at least as long as the message.
Proof sketch. Take the uniform distribution over $\mathcal{M}$. Perfect secrecy and Bayes give $\Pr[C = c \mid M = m] = \Pr[C = c \mid M = m']$ for all $m, m'$ and every $c$ of positive probability. Fix $m$ and set $S = \{\Enc(k, m) : k \in \mathcal{K}\}$. Every $c \in S$ has positive probability given $m$, hence given every $m'$, so some key encrypts $m'$ to $c$: the same set $S$ serves every message. Correctness makes $\Enc(k, \cdot)$ injective for each fixed $k$, so any single key already produces $\abs{\mathcal{M}}$ distinct ciphertexts, all inside $S$. Hence $\abs{\mathcal{K}} \ge \abs{S} \ge \abs{\mathcal{M}}$. $\square$
No design choice evades the bound. Reusing a key adds another cost outside the theorem. Encrypting two messages under the same key leaks the relation between them (section 3 makes the leak explicit), so perfect secrecy demands one fresh key per message. Sending $n$ bits in confidence requires $n$ secret bits already shared over a confidential channel. Key distribution therefore becomes circular.
The escape is to weaken the guarantee in the controlled way of section 1: bound the adversary to polynomial time and ask that its advantage be negligible. One short key can then encrypt polynomially many messages, and security rests on a computational assumption.
Perfect secrecy exists and is unconditional, and Shannon's bound prices it: $\abs{\mathcal{K}} \ge \abs{\mathcal{M}}$, one key per message. Practical cryptography settles for computational security, where a short key suffices and the definitions are games against polynomial-time adversaries.
Section 3The One-Time Pad
Lecture 1.
Shannon's bound is tight: a scheme achieves perfect secrecy with a key exactly as long as the message. The scheme is the one-time pad, which predates the theorem.
For messages in $\bits^n$, draw the key $k \getsr \bits^n$ uniformly and set
$$\Enc(k, m) = k \oplus m, \qquad \Dec(k, c) = k \oplus c.$$Correctness is one property of XOR: $k \oplus (k \oplus m) = m$.
Fix $m, c \in \bits^n$. Exactly one key is consistent with the pair, namely $k = m \oplus c$, so
$$\Pr[C = c \mid M = m] = \Pr[K = m \oplus c] = 2^{-n},$$independent of $m$. The likelihood is constant in $m$, so Bayes gives $\Pr[M = m \mid C = c] = \Pr[M = m]$. $\square$
Every ciphertext is consistent with every message of the same length, each under its own equally likely key. An unbounded adversary holding $c$ can do no better than sample from the prior, so the pad meets Shannon's bound with equality.
If the same key encrypts $m_1$ and $m_2$, then $c_1 \oplus c_2 = (k \oplus m_1) \oplus (k \oplus m_2) = m_1 \oplus m_2$. The key cancels, and what remains is a relation between the two plaintexts, independent of the key's length. Natural-language redundancy then usually recovers both messages once one fragment is guessed. The VENONA project recovered Soviet communications from reused pads. Perfect secrecy is a statement about one message per key, so the adjective in the name is what carries the guarantee.
The Two-Time Pad
Encrypt two messages under the same pad, then XOR the two ciphertexts together and watch the key cancel out. Uncheck the box to see fresh independent pads instead.
The one-time pad achieves perfect secrecy and meets Shannon's bound with equality. One fresh pad per message is the price, which is why every deployed scheme settles for computational security.
Section 4AES (Advanced Encryption Standard): The Standard Block Cipher
Lecture 2.
A block cipher is a family of permutations indexed by a key. For each $k \in \mathcal{K}$, the map $\Enc(k, \cdot)$ permutes the block space $\bits^n$, and $\Dec(k, \cdot)$ is the inverse permutation. The AES finalist Rijndael, standardized by The US National Institute of Standards and Technology (NIST) in 2001, fixes the block size at $n = 128$ bits and admits keys of 128, 192 or 256 bits, with 10, 12 or 14 rounds respectively. The state is viewed as a $4 \times 4$ matrix of bytes, filled column by column: $s_{r,c} = m_{r + 4c}$.
Common mistake. AES was designed in secret by the United States government. NIST ran an open worldwide competition from 1997 to 2000 and announced the winner, Rijndael by the Belgian cryptographers Joan Daemen and Vincent Rijmen, on October 2, 2000.
Each round applies four steps. SubBytes supplies confusion; ShiftRows and MixColumns supply diffusion; AddRoundKey mixes in key material:
- SubBytes substitutes every byte through the S-box, the only nonlinear step in the round.
- ShiftRows rotates row $r$ left by $r$ positions, moving bytes that shared a column into four different columns.
- MixColumns multiplies each column by the fixed polynomial $03\,X^3 + 01\,X^2 + 01\,X + 02$ modulo $X^4 + 1$, so one changed input byte changes four output bytes.
- AddRoundKey XORs a round key into the state.
ShiftRows and MixColumns together spread each byte's influence across the whole state. The initial round is key whitening. The final round omits MixColumns.
What went wrong. Software AES lookup tables leak key bytes through cache timing (Bernstein 2005; Osvik, Shamir and Tromer 2006). Ship constant-time code or hardware AES instructions such as AES-NI.
The S-box is derived. The lab below derives one entry live. Take the multiplicative inverse of the input byte in $\GF(2^8)$ modulo $X^8 + X^4 + X^3 + X + 1$, with $0$ mapped to $0$, then apply a fixed affine transformation over $\GF(2)^8$. The inverse supplies nonlinearity. The affine map removes the algebraic regularity that would make the inverse itself too structured. The round keys come from the key schedule: words $W[4i]$ are formed from $W[4i-4]$ and a function $g$ of $W[4i-1]$ consisting of a byte rotation, an S-box pass and a round constant, while the remaining words are XORs of the previous word and the word four positions back.
Worked number. The Data Encryption Standard (DES) of 1977 has $2^{56}$ keys: one trillion guesses per second exhausts them in about 20 hours. The same rate against $2^{128}$ AES keys needs about $1.1 \times 10^{19}$ years, roughly 800 million times the age of the universe.
AES has no proof of security. No practical attack on full-round AES is known. Its standing comes from public scrutiny and from the failure of proposed attacks to improve substantially on exhaustive search. The stage below steps through one full round on the FIPS-197 (Federal Information Processing Standard 197) test vector, with every byte computed from the field arithmetic.
Common mistake. AES-256 is always the sensible default because a longer key is always stronger. A 128-bit key already puts guessing beyond any plausible budget. Real safety depends on the mode, the randomness and the implementation.
Deriving One S-box Entry
Enter a byte in hex. The lab computes its multiplicative inverse in $\GF(2^8)$, applies the fixed affine map and checks the result against the AES table.
AES alternates confusion (the S-box) with diffusion (ShiftRows and MixColumns) and key mixing (AddRoundKey). The S-box inverse in $\GF(2^8)$ plus an affine map gives the nonlinearity. The key schedule feeds fresh material into every round.
Section 5Modes of Operation: Turning One Permutation into a Channel
Lecture 2.
A block cipher encrypts exactly one block. Messages are longer, variable and structured, so a mode of operation says how to chain the primitive. The mode is where many deployed systems fail, because the primitive's guarantee covers one block under one key, while the mode must extend that guarantee to a whole transcript.
ECB (Electronic Codebook) encrypts each block independently: $c_i = \Enc(k, m_i)$. It is deterministic and parallel. It leaks equality of plaintext blocks: $m_i = m_j$ gives $c_i = c_j$. The classic demonstration encrypts a bitmap image under ECB: runs of equal pixel blocks stay equal after encryption, so the outline of the picture survives in the ciphertext. ECB is unusable for anything with structure.
Common mistake. ECB is safe when the key is strong. ECB encrypts every block independently, so equal plaintext blocks give equal ciphertext blocks whatever the key. Use a mode with an initialization vector (IV) so identical blocks encrypt differently.
CBC (Cipher Block Chaining) feeds the previous ciphertext into the next XOR: $c_i = \Enc(k, m_i \oplus c_{i-1})$, with $c_0 = \mathrm{IV}$ a fresh random initialization vector. Equal plaintext blocks now enter the cipher with different masks. Encryption is strictly sequential, because block $i$ waits for $c_{i-1}$; decryption parallelizes, since $m_i = c_{i-1} \oplus \Dec(k, c_i)$ reads blocks in any order.
Worked number. Decryption computes $P_2 = D(C_2) \oplus C_1$. An attacker who XORs the second byte of $C_1$ with $\mathrm{0x01}$ flips the lowest bit of the second byte of $P_2$, while $P_1$ becomes garbage.
CFB (Cipher Feedback) and OFB (Output Feedback) turn the block cipher into a keystream generator. CFB encrypts the previous ciphertext and XORs the result with the next plaintext segment; OFB encrypts an internal state repeatedly and XORs the output with plaintext. Both allow segment sizes below one block. In CFB, later keystream segments depend on earlier ciphertexts; OFB's keystream depends only on the key and IV. CTR (Counter) is the cleanest of the group: it encrypts successive counters, $c_i = m_i \oplus \Enc(k, \alpha + i)$, for a fresh nonce $\alpha$. Every block is independent, so encryption and decryption parallelize fully, and any single block can be recovered alone.
Worked number. One keystream byte $K$ encrypts $\mathrm{0x41}$ to $C_1 = \mathrm{0x41} \oplus K$ and $\mathrm{0x00}$ to $C_2 = K$ under a reused nonce. The attacker computes $C_1 \oplus C_2 = \mathrm{0x41}$, the XOR of the two plaintexts.
The common failure across CBC, CFB, OFB and CTR is reuse of the IV or nonce under one key. The damage differs by mode:
- CTR and OFB generate a keystream that depends only on the key and the IV or nonce. If the same pair serves two messages, the XOR of the two ciphertexts cancels the keystream and leaves the XOR of the two plaintexts, the two-time pad of section 3. The break is total.
- CBC and CFB leak less: a repeated IV exposes the first block of each message and any common prefix, because equal plaintext blocks chain to equal ciphertext blocks until the messages first differ.
- CBC has a stronger requirement still. The IV must be unpredictable, because a predictable IV lets the adversary cancel the first block's mask inside the chosen-plaintext (CPA) game of section 6.
Freshness of the IV or nonce is part of the key discipline. The stage and lab below make the contrast visible.
Common mistake. The IV is part of the secret key material. IVs and nonces travel in the clear next to the ciphertext; counter mode demands uniqueness and CBC demands unpredictability. Secrecy applies to the key alone.
ECB Versus CBC on an 8 by 8 Pixel Block
Choose a pattern and a mode. The lab encrypts 64 one-byte blocks with a keyed S-box permutation and counts equal ciphertext pairs. The colors are ciphertext bytes.
ECB leaks equality; CBC hides it by chaining; CTR hides it by encrypting independent counters and gains full parallelism. Every streaming mode requires a fresh IV or nonce per message under the same key.
Section 6Chosen-Plaintext Security
Lecture 2.
Eavesdropping is the weakest adversary. The standard confidentiality game gives Eve an encryption oracle: she may submit any plaintexts and receive their ciphertexts under the unknown key, before and after the challenge. This models known plaintext, chosen headers and any data the adversary can cause the system to encrypt.
The game runs as follows. Draw $k \getsr \mathcal{K}$. The adversary $\mathcal{A}$ has oracle access to $\Enc(k, \cdot)$. It outputs two equal-length messages $m_0, m_1$, receives the challenge $c^* = \Enc(k, m_b)$ for a uniform bit $b$, continues querying the oracle and outputs a guess $b'$. The advantage is
$$\Adv^{\mathrm{cpa}}_{\mathcal{A}}(\lambda) = \abs{\Pr[b' = b] - \frac{1}{2}}.$$The scheme is IND-CPA secure if every polynomial-time $\mathcal{A}$ has negligible advantage.
Deterministic encryption fails the game immediately. If $\Enc$ is a function of $m$ alone, $\mathcal{A}$ queries the oracle on $m_0$, compares the answer with $c^*$ and wins with probability $1$. ECB fails for this reason, and so does any mode with a fixed IV. CPA security requires fresh randomness inside every encryption: the same plaintext must be able to produce many ciphertexts.
CBC with a fresh unpredictable IV and CTR with a fresh unique nonce both satisfy IND-CPA, assuming the underlying block cipher behaves as a pseudorandom permutation: with a random key, no polynomial-time test can tell it from a uniformly random permutation. The IV in CBC must be unpredictable, because a predictable IV lets the adversary cancel the first block's mask; the nonce in CTR must be unique, because reuse recreates the two-time pad.
What went wrong. BEAST (CVE-2011-3389, 2011) exploited predictable CBC IVs in Transport Layer Security (TLS) 1.0 to decrypt secret bytes. Random IVs remove the guessing channel.
IND-CPA gives the adversary an encryption oracle and asks that the challenge ciphertext hide which of two messages was sent. Deterministic schemes lose with advantage $1/2$; CBC with a random IV and CTR with a unique nonce achieve the definition under the pseudorandom-permutation assumption.
Section 7Message Authentication Codes
Lecture 3.
Confidentiality hides content; authenticity detects modification. From this section on, Eve also writes: she can alter, replay or inject ciphertexts in transit. A message authentication code lets Bob check that the message he received is the one Alice sent. Alice and Bob share a key $k$; Alice appends a tag computed from the message and the key, and Bob recomputes it.
A MAC is a pair of algorithms $(\Tag, \Verify)$ with $\tau = \Tag(k, m)$ and $\Verify(k, m, \tau) \in \{0, 1\}$, satisfying $\Verify(k, m, \Tag(k, m)) = 1$ for every $m$. It is existentially unforgeable under chosen-message attack if in the game where $\mathcal{A}$ has oracle access to $\Tag(k, \cdot)$ and outputs a pair $(m^*, \tau^*)$ with $m^*$ never queried to the oracle,
$$\Adv^{\mathrm{mac}}_{\mathcal{A}}(\lambda) = \Pr[\Verify(k, m^*, \tau^*) = 1]$$is negligible for every polynomial-time $\mathcal{A}$.
Encryption alone gives no authenticity. A ciphertext is malleable whenever decryption is linear in it: for the one-time pad, flipping bit $i$ of $c$ flips bit $i$ of the recovered plaintext, and Eve needs neither the key nor the plaintext. For CBC, modifying one ciphertext block corrupts the next plaintext block in a controlled way. A MAC makes such edits detectable.
Common mistake. Encryption also gives integrity, since tampering just turns the plaintext into garbage. Cipher block chaining (CBC) and counter (CTR) modes are malleable: flipping a ciphertext bit flips a predictable plaintext bit. Detect edits with a MAC.
The unforgeability game is existential: the adversary wins by forging a tag on any fresh message, even a meaningless one. The tag need not relate to any message the adversary understands. A verifier cannot tell meaningful forgeries from meaningless ones, so this is the right strength for composition. The tag oracle models all valid tags Eve can obtain by sending messages through the system or observing traffic. A secure MAC stays unforgeable after polynomially many such queries.
A MAC is a keyed tag with a verification algorithm. Unforgeability is a game: after tag-oracle queries, the adversary must produce a valid tag on a message it never asked about. Encryption by itself offers no such guarantee, because ciphertexts are malleable.
Section 8Cipher Block Chaining Message Authentication Code (CBC-MAC), and the Variable-Length Break
Lecture 3.
The block cipher already in hand can be turned into a MAC. CBC-MAC runs CBC encryption with a fixed zero Initialization Vector (IV) over the message blocks and outputs the final ciphertext block as the tag. For a one-block message, $\Tag(k, m) = \Enc(k, m)$; for two blocks, $\Tag(k, m_1 \| m_2) = \Enc(k, \Enc(k, m_1) \oplus m_2)$.
If $\Enc$ is a pseudorandom permutation, then CBC-MAC is existentially unforgeable for messages of a fixed length $\ell$. $\square$
The security proof requires every message to have the same length. When messages of different lengths are accepted under one key, the chain becomes a tool for the adversary. Two tag-oracle queries set up a forgery on a message that was never queried:
| Step | Adversary's action | Result |
|---|---|---|
| Query 1 | Ask the oracle for the tag of a one-block message $m_1$. | Receive $\tau_1 = \Enc(k, m_1)$. |
| Query 2 | Choose any block $m_2$ and ask for the tag of the one-block message $q = m_2 \oplus \tau_1$. | Receive $\tau_2 = \Enc(k, q)$. |
| Forgery | Output $(m^*, \tau^*) = (m_1 \| m_2,\; \tau_2)$. | $m^*$ was never queried, yet its tag verifies. |
Verification runs the two-block chain: the first block reproduces $\tau_1$. The second block feeds $\tau_1 \oplus m_2 = q$ into the cipher, so the final value is exactly $\tau_2$. The lab below runs the algebra with a live block cipher pass.
Two standard repairs exist. The first encrypts the final chaining value under an independent key, $\Tag(k, k', m) = \Enc(k', \mathrm{CBC\text{-}MAC}_k(m))$; the oracle no longer hands over raw intermediate values, and the two-query recipe cannot start. The second, Cipher-Based MAC (CMAC), derives two subkeys from the block cipher and treats the last block differently depending on whether it is full, which also fixes the padding ambiguity. Both keep the efficiency of CBC-MAC while restoring unforgeability for variable-length messages.
The Variable-Length CBC-MAC Forgery
Query the tag oracle on two one-block messages. The second query is chosen so that its tag is already the tag of a two-block message. Check the fix that encrypts the final block under an independent key.
CBC-MAC is secure only for fixed-length messages. Across lengths, two oracle queries forge a tag on a fresh two-block message. Encrypting the final block under a second key, or using CMAC, closes the hole.
Section 9Collision-Resistant Hashing
Lecture 3.
A hash function compresses arbitrary-length input to a fixed-length digest. Cryptography studies three common security properties.
Let $\Hash : \bits^* \to \bits^n$. Preimage resistance: given $y = \Hash(x)$ for unknown $x$, it is hard to find any $x'$ with $\Hash(x') = y$. Second-preimage resistance: given $x$, it is hard to find $x' \ne x$ with $\Hash(x') = \Hash(x)$. Collision resistance: it is hard to find any pair $x \ne x'$ with $\Hash(x) = \Hash(x')$.
Collision resistance implies second-preimage resistance: an algorithm that finds a second preimage for a given $x$ already outputs a colliding pair. The converse fails, because a collision finder may choose both inputs freely. The two notions have different costs. A preimage search over an $n$-bit digest takes about $2^n$ trials. A collision search takes about $2^{n/2}$ trials, by the birthday bound.
Draw $q$ independent uniform values from a set of size $N = 2^n$. The probability of at least one collision is
$$1 - \prod_{i=1}^{q-1}\left(1 - \frac{i}{N}\right) \approx 1 - e^{-q(q-1)/(2N)}.$$The probability reaches $1/2$ at $q \approx 1.1774 \sqrt{N} = 1.1774 \cdot 2^{n/2}$. $\square$
The bound sets digest lengths. A 128-bit digest gives about $2^{64}$ work to find a collision, which is within reach of a determined adversary; 256 bits pushes the cost to $2^{128}$. It also explains why collision resistance is the property used in signatures and commitments: the adversary gets to choose both colliding documents, so the defender must price the birthday attack. The price is the square root of the digest space.
Hashing is unkeyed. Anyone can compute $\Hash(x)$, so a bare digest binds nothing to anyone. The next sections add a key for authentication and a domain transform for arbitrary lengths.
Preimage resistance costs $2^n$, collision resistance costs $2^{n/2}$. Digest lengths are chosen against the birthday bound, and collision resistance is the strongest of the three notions because it lets the adversary choose both inputs.
Section 10Merkle-Damgard: From Fixed to Arbitrary Length
Lecture 4.
Collision resistance was defined for a function on all bit strings, while the constructions in hand compress one fixed-size block. The Merkle-Damgard transform iterates a compression function $\mathbf{cmps} : \bits^\ell \times \bits^{\ell'} \to \bits^\ell$ over the message. Split the input into $\ell'$-bit blocks, start from a fixed initial value $z_0 = 0^\ell$ and compute $z_i = \mathbf{cmps}(z_{i-1}, x_i)$. A final block records the total message length. The digest is the last chaining value.
If $\mathbf{cmps}$ is collision-resistant on its fixed domain, then the iterated hash $\Hash$ is collision-resistant on arbitrary-length messages. $\square$
The length block is what makes the proof go through. Without it, two messages that share a prefix could collide at different stopping points; with it, a collision in $\Hash$ can be traced back through the chain to a collision in one call to $\mathbf{cmps}$. SHA-1 and SHA-2 (Secure Hash Algorithm versions 1 and 2) are built this way, with different compression functions and digest lengths. Collision attacks break SHA-1. SHA-2 uses a different compression function that has resisted practical collision attacks.
The same structure that gives the proof also gives the length-extension property. The digest is the final chaining value. The compression function is public. Anyone holding $\Hash(x)$ and the length of $x$ can continue the chain: start from the digest, absorb extra blocks and obtain $\Hash(x \| \mathrm{pad} \| x')$ without knowing anything about $x$. For a bare digest this is a curiosity. For the naive MAC $\Tag(k, m) = \Hash(k \| m)$ it is a forgery: Eve holds one valid tag, extends the message and computes the tag of the extended message herself. The stage below shows the chain being continued from the tag.
Merkle-Damgard iterates a fixed-size compression function and appends a length block; the transform preserves collision resistance. The public chaining structure makes digests extendable, which breaks any MAC built as $\Hash(k \| m)$.
Section 11The Sponge and SHA-3 (Secure Hash Algorithm 3)
Lecture 4.
SHA-3, standardized by NIST in 2015 after the Keccak selection, replaces the Merkle-Damgard chain with a sponge. The state holds $b$ bits, split into a rate $r$ and a capacity $c$, with $b = r + c$. SHA-3 fixes $b = 1600$. Message blocks of $r$ bits are XORed into the rate. The whole state passes through a fixed permutation $\mathbf{f}$ after each absorption. When the message is exhausted, output bits are squeezed from the rate, applying $\mathbf{f}$ again whenever more output is needed.
The capacity is the security parameter. Message bits touch the rate alone, so the capacity stays hidden inside the state. Generic attacks on an ideal permutation succeed with probability about $q(q-1) \cdot 2^{-(c+1)}$ in $q$ calls, so $c = 512$ sets a $256$-bit capacity security bound. Output length can impose a lower bound, as it does for collision resistance of SHA-3-256. One construction serves several digest lengths by changing the rate: SHA-3-224, SHA-3-256, SHA-3-384 and SHA-3-512 use capacities $448$, $512$, $768$ and $1024$ respectively. The squeezing phase can produce any requested output length.
The hidden capacity removes the Merkle-Damgard extension property. A SHA-3 digest reveals only the rate portion of the final state; the capacity portion is never output, so there is no chaining value an adversary can continue from. The naive MAC $\Hash(k \| m)$ is still unwise, because other attacks exist, and section 12 gives the keyed construction to use. The permutation itself, Keccak-f[1600], is 24 rounds built from the steps $\theta, \rho, \pi, \chi, \iota$, using XOR, AND and NOT on a $5 \times 5$ array of 64-bit lanes.
The sponge absorbs message blocks into the rate and squeezes output from it, with the capacity hidden inside the state. SHA-3's security level is set by the capacity. The construction has no length-extension property.
Section 12Hash-Based Message Authentication Code (HMAC): A Keyed Hash That Resists Extension
Lecture 4.
Two naive ways to key a hash both fail:
- $\Tag(k, m) = \Hash(k \| m)$ falls to length extension (section 10). Eve holds one valid tag, extends the message and computes the tag of the extended message without knowing $k$.
- $\Tag(k, m) = \Hash(m \| k)$ falls to collisions. The hash is public, so a collision $m, m'$ found offline carries over to the keyed tag whatever the key: equal chaining values where $k$ is absorbed give equal tags.
HMAC is the standard repair, used in TLS (Transport Layer Security), IPsec (Internet Protocol security) and most protocols that need a symmetric authenticity tag from a hash function. It hashes the message with an inner key, then hashes the result with an outer key:
$$\mathrm{HMAC}(k, m) = \Hash\big((k \oplus \mathit{opad}) \,\|\, \Hash((k \oplus \mathit{ipad}) \,\|\, m)\big).$$The key is first brought to the block size of the hash: keys longer than the block are hashed, shorter keys are padded with zeros. The constants $\mathit{ipad}$ and $\mathit{opad}$ are the bytes $0x36$ and $0x5c$ repeated across the block.
The double hash is what blocks extension. The inner digest $\Hash((k \oplus \mathit{ipad}) \| m)$ is exactly a Merkle-Damgard chaining value, so an adversary holding it could extend it if that were the tag. The outer hash consumes the inner digest as input, and its own chaining value starts from $k \oplus \mathit{opad}$, which the adversary does not know. Extending the final tag would require continuing a chain whose initial value is secret.
HMAC's security is analyzed as a pseudorandom function (PRF), a keyed family that no polynomial-time test can tell from a uniformly random function. If the compression function of the underlying hash is a good PRF, then HMAC is a PRF. A PRF with output length $n$ gives a MAC whose best forgery probability after $q$ attempts is about $q / 2^n$. The construction works with any Merkle-Damgard hash and with the sponge, where the extension problem never existed; the keyed sponge construction KMAC takes that route for SHA-3.
HMAC hashes the message under an inner key and hashes the result under an outer key. The outer hash hides the chaining value that length extension needs. The construction is provably a PRF when the compression function is.
Section 13Chosen-Ciphertext Attack (CCA) Security and Authenticated Encryption
Lecture 4.
The strongest standard game adds a decryption oracle to the CPA game of section 6: Eve may submit ciphertexts of her choice and learn their plaintexts, with the single restriction that she may not submit the challenge ciphertext itself. This is IND-CCA. It models padding oracles, protocol endpoints that decrypt and react and any situation where Eve can observe the effect of a modified ciphertext.
The adversary has access to both $\Enc(k, \cdot)$ and $\Dec(k, \cdot)$. After receiving $c^* = \Enc(k, m_b)$, it may continue querying both oracles, except that $\Dec(k, c^*)$ is disallowed. The advantage is $\abs{\Pr[b' = b] - 1/2}$. The scheme is IND-CCA secure if it is negligible.
The padding oracle is the concrete instance. CBC decryption checks padding only after decrypting, so a server that reports whether the padding is valid gives Eve one bit per query. She adjusts one ciphertext byte at a time until the check passes. Each pass reveals one plaintext byte: at most 256 tries per byte and 16 bytes per block, so at most $256 \times 16 = 4096$ oracle queries recover a whole block, against $2^{128}$ work for a key search. Authenticated encryption with associated data (AEAD) closes the hole by withholding plaintext until authentication succeeds.
What went wrong. POODLE (CVE-2014-3566, 2014) turned a padding validity signal into byte-by-byte CBC decryption, building on Vaudenay's 2002 attack. Verify a message authentication code before processing padding.
Authenticated encryption is the composition target: one scheme providing both IND-CPA confidentiality and ciphertext integrity. The composition that works is encrypt-then-MAC. Encrypt under one key, tag the ciphertext under a second key and send $(c, \tau)$. Verification rejects any ciphertext whose tag does not check, before decryption ever runs. The decryption oracle of the CCA game is then useless to Eve: any ciphertext she did not create herself carries a fresh valid tag with negligible probability, and the MAC's unforgeability is exactly the statement that she cannot create one. The theorem requires the MAC to be strongly unforgeable, so that even altering the tag on a seen ciphertext fails. IPsec uses this order.
The other two orders are fragile:
- MAC-then-encrypt hides the tag, so the receiver must decrypt before checking. The decryption step itself can leak through padding or timing. TLS used this order for its CBC suites, and padding-oracle attacks on the decrypt-then-check sequence were the result.
- Encrypt-and-MAC sends the tag of the plaintext, which may reveal plaintext information and does not cover the ciphertext. SSH uses this order.
Deployed schemes package the working order. GCM (Galois/Counter Mode) runs CTR (Counter) encryption with a universal hash authentication tag, and ChaCha20-Poly1305 does the same with a stream cipher and a one-time authenticator. Both are AEAD schemes, taking an associated data field that is authenticated in the clear. GCM limits each plaintext to about $2^{39}$ bits. Its safe per-key usage limit depends on tag length, message lengths and nonce generation. TLS 1.3 accepts only AEAD ciphers.
Worked number. GCM usually takes a 96-bit random nonce. By the birthday bound, $2^{32}$ messages (about 4.3 billion) under one key give a collision probability near $2^{-33}$, roughly one chance in 8.6 billion.
IND-CCA adds a decryption oracle to the CPA game. Encrypt-then-MAC with independent keys and a strongly unforgeable MAC achieves it, because every valid ciphertext the adversary can produce was already produced by the encryption oracle. GCM and ChaCha20-Poly1305 are the deployed instances.
Section 14Minicrypt: What One Assumption Buys
Lecture 5.
Every construction so far has rested on a block cipher assumed secure. The last step asks what the minimal assumption is and what it can build. The assumption is a one-way function: a polynomial-time computable function $f$ such that for every polynomial-time inverter, $\Pr[f(x') = f(x)]$ is negligible when $x \getsr \bits^\lambda$ and the inverter sees $f(x)$. Minicrypt is the world where one-way functions exist and public-key cryptography does not. Whether one-way functions imply public-key cryptography remains unknown.
One-way functions first yield pseudorandom generators. A PRG stretches a short seed into a longer string that no polynomial-time distinguisher can tell from uniform. The existence of one-way functions implies the existence of PRGs, by a theorem of Håstad, Impagliazzo, Levin and Luby. PRGs then yield pseudorandom functions. A PRF is a keyed function family $\PRF(k, \cdot)$ indistinguishable from a uniformly random function, given oracle access. The GGM (Goldreich-Goldwasser-Micali) construction, shown in the stage below, builds one from a length-doubling PRG by tree expansion: the input bits select a root-to-leaf path. The leaf is the output. Evaluation costs $\lambda$ PRG calls. The proof shows that any pattern of queried leaves looks random.
PRFs in turn yield pseudorandom permutations. A Feistel network builds a permutation from any function: split the block into halves, and in each round replace the right half by the left half XORed with a round function of the right half. Luby and Rackoff proved that three Feistel rounds with independent pseudorandom-function round functions give a PRP, and four rounds give a strong PRP, secure even when the adversary can query the inverse. AES is a substitution network with a similar goal. The Feistel theorem explains why a few rounds of a good keyed function suffice in principle.
One-way functions give PRGs, PRGs give PRFs and PRFs give PRPs. These primitives support encryption, modes and MACs. Collision-resistant hash functions require an additional assumption in general. The boundary of Minicrypt is the subject of Chapter 2, where public keys require assumptions believed stronger.
One-way functions imply PRGs, PRGs imply PRFs via the GGM tree and PRFs imply PRPs via Feistel networks. Minicrypt is the world where this chain runs and public-key primitives may not exist.
Section 15Further Resources
- Crypto 101. A free programmer-first course that builds to TLS and teaches by exploiting real flaws.
- CryptoHack Symmetric course. Interactive: rebuild AES from its parts, then attack ECB, CBC and stream misuse.
- The Joy of Cryptography (Rosulek). A free undergraduate textbook anchored in the one-time pad and game-based definitions.
- A Graduate Course in Applied Cryptography (Boneh and Shoup). Free PDF; a clean arc through stream ciphers, block ciphers, CPA, integrity and AEAD.
- Practical Cryptography for Developers (Nakov). Code-first AES, modes, AES-GCM, ChaCha20-Poly1305, Hash-Based Message Authentication Code (HMAC) and Key Derivation Functions (KDFs) with Python.
- NIST SP 800-38A, block cipher modes. The canonical definitions of ECB, CBC, CFB, OFB and CTR.
- Wikipedia: Block cipher mode of operation. Strong diagrams and per-mode property tables.
- Interactive AES pipeline (cryptii). Live in-browser AES with selectable mode, IV and padding.
- Cryptopals. Sets 2 to 4 for hands-on block and stream cipher attacks.
Further reading: Sweigart, Hacking Secret Ciphers with Python, Katz and Lindell (2015), Introduction to Modern Cryptography, Kościelny, Kurkowski and Srebrny (2013), Modern Cryptography Primer and Kotzanikolaou and Douligeris (2007), Cryptography Primer.
Section 16Exercises
Drills first, then the attacks and the composition theorem. Answers are worked out in full; the arithmetic in them has been checked against the labs on this page.
Take the one-time pad over $\bits^2$ with uniform message and uniform key. Given $c = 10$, compute $\Pr[M = 00 \mid C = 10]$ and explain why the calculation is the definition of perfect secrecy. Drill
The prior is $\Pr[M = 00] = 1/4$. For the likelihood, $C = 10$ given $M = 00$ requires $K = 00 \oplus 10 = 10$, so $\Pr[C = 10 \mid M = 00] = \Pr[K = 10] = 1/4$. The same calculation holds for every message: each of the four messages has exactly one consistent key, each with probability $1/4$. Hence $\Pr[C = 10] = 4 \cdot (1/4) \cdot (1/4) = 1/4$, and Bayes gives
$$\Pr[M = 00 \mid C = 10] = \frac{(1/4)(1/4)}{1/4} = \frac{1}{4} = \Pr[M = 00].$$The posterior equals the prior. Repeating the argument for every message and every ciphertext gives the definition.
Prove Shannon's bound: a perfectly secret scheme with message space $\mathcal{M}$ and key space $\mathcal{K}$ satisfies $\abs{\mathcal{K}} \ge \abs{\mathcal{M}}$. Theory
Use the uniform distribution over $\mathcal{M}$. Perfect secrecy and Bayes give $\Pr[C = c \mid M = m] = \Pr[C = c \mid M = m']$ for all $m, m'$ and every $c$ of positive probability. Fix $m$ and let $S = \{\Enc(k, m) : k \in \mathcal{K}\}$. Every $c \in S$ has positive probability given $m$, hence given every $m'$, so some key encrypts $m'$ to $c$. Therefore the same set $S$ is reachable from every message. Correctness makes $\Enc(k, \cdot)$ injective for each fixed $k$, so one key already produces $\abs{\mathcal{M}}$ distinct ciphertexts, all inside $S$. Hence $\abs{\mathcal{K}} \ge \abs{S} \ge \abs{\mathcal{M}}$.
Two 8-bit messages are encrypted with the same one-time pad, producing $c_1 = \mathrm{0x9f}$ and $c_2 = \mathrm{0xe3}$. If $m_1 = \mathrm{0x20}$, recover $m_2$ and state the general lesson. Attack
XOR the two ciphertexts:
$$c_1 \oplus c_2 = (k \oplus m_1) \oplus (k \oplus m_2) = m_1 \oplus m_2 = \mathrm{0x9f} \oplus \mathrm{0xe3} = \mathrm{0x7c}.$$Then $m_2 = m_1 \oplus \mathrm{0x7c} = \mathrm{0x20} \oplus \mathrm{0x7c} = \mathrm{0x5c}$. The key cancels completely; the attack uses only the two ciphertexts and one known plaintext. The lesson is that pad reuse turns the scheme into a relation between plaintexts, independent of the pad's length.
The ECB lab's smiley pattern has 16 foreground bytes and 48 background bytes across 64 blocks. Count the equal plaintext pairs, explain why ECB preserves the count and estimate the CBC count. Attack
The number of equal pairs is the sum over the two values of $\binom{n}{2}$:
$$\binom{16}{2} + \binom{48}{2} = 120 + 1128 = 1248$$out of $\binom{64}{2} = 2016$ total pairs. ECB computes $c_i = F(k, m_i)$ with $F(k, \cdot)$ a permutation, so $c_i = c_j$ exactly when $m_i = m_j$; the ciphertext has the same 1248 equal pairs, so the shape survives. CBC computes $c_i = F(k, m_i \oplus c_{i-1})$, so equal plaintext bytes enter the cipher with different masks. The ciphertext bytes behave close to uniform independent draws, giving an expected $2016 / 256 \approx 7.9$ equal pairs; the lab's fixed seed gives 26, a chance fluctuation around that mean.
Construct a two-query forgery against CBC-MAC when messages of different lengths are accepted under one key. Attack
CBC-MAC uses a fixed zero IV. Query the tag oracle on the one-block message $m_1$ and receive $\tau_1 = \Enc(k, m_1)$. Choose any block $m_2$ and query the oracle on the one-block message $q = m_2 \oplus \tau_1$, receiving $\tau_2 = \Enc(k, q) = \Enc(k, m_2 \oplus \tau_1)$. Output $(m^*, \tau^*) = (m_1 \| m_2, \tau_2)$. Verification runs the two-block CBC chain: the first block gives $t_1 = \Enc(k, m_1) = \tau_1$. The second gives $t_2 = \Enc(k, t_1 \oplus m_2) = \Enc(k, \tau_1 \oplus m_2) = \tau_2$. The message $m_1 \| m_2$ was never queried, so the pair is a valid forgery.
Derive the number $q$ of random inputs needed for collision probability at least $1/2$ in an $n$-bit hash, and evaluate it for $n = 128$. Drill
With $N = 2^n$ possible digests, the probability that $q$ independent draws are all distinct is
$$\prod_{i=1}^{q-1}\left(1 - \frac{i}{N}\right) \approx e^{-q(q-1)/(2N)}.$$Setting the collision probability to $1/2$ gives $q(q-1) \approx 2N \ln 2$, so
$$q \approx \sqrt{2 \ln 2}\, 2^{n/2} \approx 1.1774 \cdot 2^{n/2}.$$For $n = 128$, this is about $1.1774 \cdot 2^{64}$, usually quoted as $2^{64}$ work. Doubling the security level requires doubling the digest length, which is why collision resistance is priced at $2n$ bits for an $n$-bit security target.
Show that encrypt-then-MAC from an Indistinguishability under Chosen-Plaintext Attack (IND-CPA) cipher and a strongly unforgeable Message Authentication Code (MAC) is Indistinguishability under Chosen-Ciphertext Attack (IND-CCA) secure. Theory
The combined scheme sends $(c, \tau)$ with $c = \Enc(k_e, m)$ and $\tau = \Tag(k_m, c)$, using independent keys. In the CCA game, the adversary's decryption oracle accepts only pairs with a valid MAC. Consider any decryption query the adversary makes on a pair it did not receive from the encryption oracle. If the pair verifies, then the adversary has produced a valid tag on a fresh ciphertext, or a valid tag under a modified ciphertext. Either event breaks strong unforgeability of the MAC. Hence all such queries are rejected except with negligible probability.
With the decryption oracle effectively disabled, the remaining view is the IND-CPA game for the encryption scheme: the challenge ciphertext $c^* = \Enc(k_e, m_b)$ hides $b$ up to negligible advantage. The MAC tag on $c^*$ is computed by the challenger, giving the adversary no extra information about $m_b$. The total advantage is bounded by the MAC forgery advantage plus the CPA advantage, both negligible.
Compute the AES S-box output for input $\mathrm{0x68}$, given that its inverse in $\GF(2^8)$ is $\mathrm{0xf4}$. Drill
First check the inverse: multiplication in $\GF(2^8)$ modulo $X^8 + X^4 + X^3 + X + 1$ gives $\mathrm{0x68} \cdot \mathrm{0xf4} = 1$, as the S-box lab verifies. The affine step computes, for bit $i$ in little-endian order,
$$y_i = z_i \oplus z_{i+4} \oplus z_{i+5} \oplus z_{i+6} \oplus z_{i+7} \oplus c_i,$$with indices modulo 8 and $c = \mathrm{0x63}$. For $z = \mathrm{0xf4}$, the bits $z_0,\dots,z_7$ are $0,0,1,0,1,1,1,1$. Evaluating the formula gives $y_0,\dots,y_7 = 1,0,1,0,0,0,1,0$, which is the byte $\mathrm{0x45}$. Hence $\mathrm{S}(\mathrm{0x68}) = \mathrm{0x45}$.
These pages are written by a student of the course. The mathematics is stated in the standard way. The formulation is the author's own, taken from no slide. Errors are the author's alone. Prof. Venturi bears no responsibility for them; where this page and the PDFs differ, the PDFs are authoritative and only material in them is examinable.