Message Authentication Codes and Hash Functions

Corresponds to Katz & Lindell, Introduction to Modern Cryptography, Chapter 4.

Motivation: was this message really sent, unchanged?

IntuitionIntegrity is not secrecy

A supermarket emails a supplier an order for 10,000 crates of soda. Nothing is secret, but the supplier must know (1) the order is authentic (email addresses are trivial to spoof) and (2) it arrived unmodified. Unprotected orders, banking requests, email and SMS can’t be trusted at all, yet caller IDs and return addresses are routinely treated as proof of identity. Modification can’t be prevented on an open channel; the goal is to detect it so that tampered messages can be discarded. Privacy and authentication are distinct goals that are often confused; the chapter ends by combining them correctly.

Encryption does not authenticate

WarningCiphertexts are malleable

Stream ciphers, OFB, CTR: $c = G(k)\oplus m$ , so flipping a ciphertext bit flips the same plaintext bit. Fixed-format headers make it easy to flip a buy/sell flag or alter an amount, even without knowing its value.
CBC: flipping a bit of the $IV$ flips the same bit of the first plaintext block, often the header.
ECB: blocks can be reordered, with nothing scrambled.
Any block cipher: relying on the receiver to notice a “scrambled” block is application-dependent and unreliable.

An extra mechanism is required: a message authentication code.

Message authentication codes

DefinitionMAC syntax (Def. 4.1)

A tuple of ppt algorithms $(\mathrm{Gen},\mathrm{Mac},\mathrm{Vrfy})$ :

$k\leftarrow\mathrm{Gen}(1^n)$ , uniform in $\{0,1\}^n$ ;
$t\leftarrow\mathrm{Mac}_k(m)$ , the tag, for $m\in\{0,1\}^*$ ;
$\mathrm{Vrfy}_k(m,t)\in\{0,1\}$ ;
correctness: $\mathrm{Vrfy}_k(m,\mathrm{Mac}_k(m)) = 1$ (relaxable to $1 - \mathrm{negl}$ ).

Fixed-length with parameter $\ell$ : Mac is defined only on $\{0,1\}^{\ell(n)}$ , and Vrfy rejects other lengths. MACs are private-key primitives: the parties share $k$ .

DefinitionForgery experiment $\mathrm{Mac\text{-}forge}_{\mathcal A,\Pi}(n)$ (Def. 4.2)

$k\leftarrow\{0,1\}^n$ .
$\mathcal A^{\mathrm{Mac}_k(\cdot)}(1^n)$ queries a MAC oracle adaptively (query set $\mathcal Q$ ) and outputs $(m,t)$ .
Success iff $m\notin\mathcal Q$ and $\mathrm{Vrfy}_k(m,t) = 1$ .

$\Pi$ is existentially unforgeable under an adaptive chosen-message attack (“secure”) if every ppt $\mathcal A$ succeeds with negligible probability.

Component	Choice	Why
Power	adaptive tag queries on chosen messages	adversaries may influence what gets authenticated (an assistant drafting letters the boss signs)
Break	a valid tag on any new message	no assumption about meaningful formats: secure for every application

NoteTags must be super-logarithmic

Guessing a random tag of length $q$ succeeds with probability at least $2^{-q}$ . If $q = O(\log n)$ , that is $1/\mathrm{poly}(n)$ , which is not negligible. Secure MACs need tags of $\omega(\log n)$ bits.

WarningReplay attacks are outside the MAC’s job

Alice’s authenticated “pay Bob $1,000” can be resent ten times by Bob without forging anything. Whether a replay is legitimate depends on the application and its history. Defences: sequence numbers (MAC’d with the message; reuse is rejected) or timestamps (with duplicate rejection). A replay with a changed counter requires forging the MAC.

Fixed-length MAC from a PRF

AlgorithmConstruction 4.3

$k\leftarrow\{0,1\}^n$ ; $\mathrm{Mac}_k(m) = F_k(m)$ for $m\in\{0,1\}^n$ ; $\mathrm{Vrfy}_k(m,t) = 1$ iff $t = F_k(m)$ .

TheoremTheorem 4.4 — A PRF is a secure fixed-length MAC

If $F$ is a PRF, Construction 4.3 is existentially unforgeable for $n$ -bit messages.

ProofRandom function first, then a distinguisher

Ideal world: with a truly random $f$ , for any $m\notin\mathcal Q$ the value $f(m)$ is uniform from the adversary’s view, so success is at most $2^{-n}$ .

Distinguisher $D^{\mathcal O}$ : answer $\mathcal A$ ‘s queries with $\mathcal O$ . When $\mathcal A$ outputs $(m,t)$ , check $m\notin\mathcal Q$ and $\mathcal O(m) = t$ , and output 1 iff both hold. Then $\Pr[D^{F_k} = 1] = \varepsilon(n)$ and $\Pr[D^f = 1]\le2^{-n}$ , so $\varepsilon(n) - 2^{-n}$ is negligible, hence so is $\varepsilon$ .

∎

Extending to variable-length messages

WarningThree tempting constructions that fail

Split $m$ into blocks $m_1,\ldots,m_d$ :

MAC only the first block: change the other blocks freely.
MAC the XOR of all blocks: modify two blocks while keeping their XOR.
MAC each block separately (ECB-like): blocks can be dropped, repeated, reordered, and spliced from different messages.

The fix must bind each block to its position, its message, and the total length.

AlgorithmConstruction 4.5 — Variable-length MAC

Split $m$ (length below $2^{n/4}$ , padded with $10^*$ ) into $d$ blocks of $n/4$ bits. Choose a random identifier $r\leftarrow\{0,1\}^{n/4}$ . For each $i$ :

$t_i = F_k(r\,\Vert\,d\,\Vert\,i\,\Vert\,m_i)$

(each field $n/4$ bits). The tag is $(r,t_1,\ldots,t_d)$ . Vrfy recomputes using the tag’s $r$ .

What each field blocks: $i$ stops reordering, $d$ stops truncation and extension, $r$ stops splicing across messages.

TheoremTheorem 4.6 — Construction 4.5 is secure

If $F$ is a PRF, Construction 4.5 is existentially unforgeable.

ProofCase analysis in the random-function world

With a truly random $f$ , take a forgery $(m,(r,t_1,\ldots,t_d))$ with $m\notin\mathcal Q$ :

$r$ is new: $f$ was never evaluated at any $(r,\cdot,\cdot,\cdot)$ , so each $t_i$ is a fresh guess, succeeding with probability at most $2^{-n}$ .
$r$ appeared in exactly one oracle tag, for $m'\ne m$ $m^{'} \neq = m$ with $d'$ $d^{'}$ blocks:
- $d = d'$ : some block has $(i,m_i)\ne(i,m'_i)$ , so $f(r\Vert d\Vert i\Vert m_i)$ is fresh: $2^{-n}$ .
- $d\ne d'$ : $f$ was never applied to any $(r,d,\cdot,\cdot)$ : $2^{-n}$ .
$r$ appeared in two or more oracle tags: honest identifiers collide with probability at most $\binom N2 2^{-n/4}$ over $N$ queries, which is negligible (birthday).

Then the distinguisher step is as in Theorem 4.4.

∎

NoteCost and variations (Exercise 4.3)

A message of $\ell n$ bits needs $4\ell$ PRF calls and a $4\ell n$ -bit tag, which is impractical. Any fixed-length MAC can replace the PRF. Replacing $d$ with a last-block bit $b$ removes the need to know the length in advance (useful for streaming). Outputting $(r,\bigoplus_it_i)$ shrinks the tag to $n/4 + n$ bits (the harder proof).

ExampleA broken two-block MAC (Exercise 4.1)

$\mathrm{Mac}_k(m_0\Vert m_1) = F_k(0\Vert m_0)\Vert F_k(1\Vert m_1)$ for $(n-1)$ -bit halves is insecure: there is no link between the halves. Query $(a,b)$ to get $(x,y)$ and $(c,d)$ to get $(z,w)$ , then output the forgery $\big((a,d),(x,w)\big)$ . (Worked here.)

CBC-MAC

AlgorithmBasic CBC-MAC (Construction 4.7)

For $m = m_1\cdots m_\ell$ with $n$ -bit blocks: $t_0 = 0^n$ , $t_i = F_k(t_{i-1}\oplus m_i)$ , tag $t_\ell$ . That is $\ell$ block-cipher calls and an $n$ -bit tag.

TheoremTheorem 4.8 — Secure for one fixed length

For any fixed $\ell$ , if $F$ is a PRF then basic CBC-MAC is a secure MAC for $\ell n$ -bit messages (the proof is involved and omitted). The length can be any fixed value, not tied to the PRF’s input length.

WarningCBC-MAC is not CBC encryption

Feature	CBC encryption	CBC-MAC
IV	random, essential	fixed ( $0^n$ ), essential
Output	all blocks	only the last block, essential

Harmless-looking changes break it, and libraries often expose one “CBC function” for both uses. Implement exactly the proven construction.

ExampleThe attacks (Exercises 4.4–4.5)

Random IV (tag $(IV,t)$ ): for one block, $t = F_k(IV\oplus m_1)$ , so $(IV\oplus\Delta,t)$ is a valid tag on $m_1\oplus\Delta$ . Any change to the first block can be absorbed by the IV.
All blocks output (two blocks): query $(x,y)$ to get $(t_1,t_2)$ and $(x',y')$ to get $(t'_1,t'_2)$ . Then $(x,\ t_1\oplus x')$ has tag $(t_1,\ F_k(x')) = (t_1,t'_1)$ .
Variable lengths with basic CBC-MAC: if $t = F_k(m)$ for one block $m$ , then the two-block message $(m,\ t\oplus m)$ has tag $F_k(t\oplus t\oplus m) = t$ . This gives little control over the forged content, but one known attack signals that others may exist.

(Worked here.)

AlgorithmProvably secure variable-length CBC-MAC

Length-derived key: $k_\ell = F_k(\ell)$ , then basic CBC-MAC under $k_\ell$ (send $\ell$ too).
Prepend the length: the first block is $\ell$ . Appending the length is insecure.
Encrypt the last block (ECBC): $t = F_{k_2}(\mathrm{CBC\text{-}MAC}_{k_1}(m))$ . No need to know the length in advance. Derive $k_1 = F_k(1)$ and $k_2 = F_k(2)$ to store one key.

(The standardised descendant is CMAC, which uses derived subkeys to handle the final block.)

Collision-resistant hash functions

IntuitionFrom data structures to cryptography

Hash tables want few collisions among non-adversarial data. Cryptography demands that no efficient adversary, actively searching, can find any collision. Compression guarantees collisions exist (pigeonhole), so they must merely be hard to find. Without compression it is trivial: the identity function is collision-resistant.

DefinitionHash function (Def. 4.9)

$(\mathrm{Gen},H)$ : $s\leftarrow\mathrm{Gen}(1^n)$ is a public key (it just selects a function from a family; it is not secret), and $H^s(x)\in\{0,1\}^{\ell(n)}$ for $x\in\{0,1\}^*$ . Fixed-length with parameter $\ell' > \ell$ : defined only on $\{0,1\}^{\ell'(n)}$ , so it compresses.

DefinitionCollision resistance (Def. 4.10)

Experiment $\mathrm{Hash\text{-}coll}_{\mathcal A,\Pi}(n)$ : $s\leftarrow\mathrm{Gen}(1^n)$ , $(x,x')\leftarrow\mathcal A(s)$ , success iff $x\ne x'$ and $H^s(x) = H^s(x')$ . Collision-resistant if every ppt $\mathcal A$ succeeds with negligible probability.

TheoremHierarchy of hash security (Exercise 4.6)

Notion	Given	Find
Collision resistance	$s$	any $x\ne x'$ with $H^s(x) = H^s(x')$
Second-preimage resistance	$s$ and random $x$	$x'\ne x$ with $H^s(x') = H^s(x)$
Preimage resistance (one-wayness)	$s$ and $y = H^s(x)$	any $x'$ with $H^s(x') = y$

Collision resistance ⇒ second-preimage resistance (a second preimage is a collision) ⇒ preimage resistance (invert $H^s(x)$ for random $x$ ). The returned $x'$ differs from $x$ with good probability because $H$ compresses: most outputs have many preimages.

The birthday attack

AlgorithmGeneric collision finding

Hash $q$ distinct random inputs and look for a repeated output. Modelling $H^s$ as random, with $\ell$ -bit outputs,

$\Pr[\text{collision}]\approx1 - e^{-q^2/2^{\ell+1}},\qquad q\approx2^{\ell/2}\ \Rightarrow\ \text{constant probability}$

(23 people make a shared birthday more likely than not). Being far from random only helps the attacker.

ImportantOutput length must be twice the security level

Resisting time- $T$ collision attacks needs output length $\ell\ge2\log_2T$ . Asymptotically $2^\ell$ and $2^{\ell/2}$ are the same (both polynomial iff $\ell = O(\log n)$ ), but practically, 128-bit outputs give only about $2^{64}$ collision security, which is feasible. No generic attack finds second preimages or preimages faster than about $2^\ell$ .

AlgorithmBirthday attacks with constant memory, and with meaningful messages

Constant memory (cycle finding): iterate $x_i = H(x_{i-1})$ and $y_i = H(H(y_{i-1}))$ until $x_m = y_m$ . Then $x_{m-1}$ and $H(y_{m-1})$ collide (usually distinct), after about $2^{\ell/2}$ steps with no table. Time $2^{64}$ is far more feasible than $2^{64}$ storage.
Meaningful collisions: a sentence with independent synonym choices has many variants ( $3\cdot4\cdot2\cdot3 = 72$ for the book’s example). With 64 binary word choices a letter has $2^{64}$ versions. Generate $2^{\ell/2}$ variants of a dismissal letter and $2^{\ell/2}$ of a recommendation letter, then find a cross-collision. This needs memory, so the cycle trick doesn’t apply.

The Merkle–Damgård transform

AlgorithmConstruction 4.11 — Merkle–Damgård

Given a compression function $h^s : \{0,1\}^{2\ell}\to\{0,1\}^\ell$ , for $x\in\{0,1\}^*$ with $\lvert x\rvert = L < 2^\ell$ :

zero-pad $x$ to $B = \lceil L/\ell\rceil$ blocks $x_1,\ldots,x_B$ ;
$z_0 = IV$ (any fixed constant, e.g. $0^\ell$ ) and $z_i = h^s(z_{i-1}\Vert x_i)$ ;
output $H^s(x) = h^s(z_B\Vert L)$ , the length block.

It reduces “hash arbitrary lengths” to “compress by even one bit” (Exercise 4.7 generalises the block sizes). It underlies MD5, SHA-1 and SHA-2.

TheoremTheorem 4.12 — Merkle–Damgård preserves collision resistance

If $h$ is collision-resistant, so is $H$ .

ProofAny collision in

H

exposes a collision in

h

Let $x\ne x'$ with $H^s(x) = H^s(x')$ .

$L\ne L'$ : the final calls $h^s(z_B\Vert L)$ and $h^s(z'_{B'}\Vert L')$ have equal outputs on different inputs.
$L = L'$ : let $i^*$ be the largest $i$ with $(z_{i-1}\Vert x_i)\ne(z'_{i-1}\Vert x'_i)$ . It exists because some $x_i\ne x'_i$ . Its outputs are equal: either $i^* = B$ (then $z_B = z'_B$ from the final call with equal $L$ ), or by maximality $z_{i^*} = z'_{i^*}$ . Either way it is a collision in $h^s$ .

The formal reduction runs the $H$ -collision finder and applies this extraction (Exercise 4.10).

∎

ExampleVariations on Merkle–Damgård (Exercise 4.11)

(a) Drop the length block: insecure with zero padding. $x$ and $x\Vert0$ (when $\lvert x\rvert$ isn’t a multiple of $\ell$ ) pad to the same blocks.
(b) Output $z_B\Vert L$ instead of hashing it: secure. Equal outputs force $L = L'$ and $z_B = z'_B$ , and the case-2 argument applies.
(c) Random $IV$ included in the output: secure. Equal outputs force equal $IV$ s, reducing to the standard proof.
(d) No IV, $z_1 = x_1$ : secure. In the maximal-index argument, if no index $i\ge2$ differs then $z_1 = z'_1$ forces $x_1 = x'_1$ , so $x = x'$ . Different lengths are caught by the length block.

(Worked here.)

ExampleComposing hashes (Exercises 4.8–4.9)

$H^s(H^s(x))$ is collision-resistant: a collision is either a collision of the inner $H$ , or of the outer $H$ on two distinct inner outputs.
Concatenation $H_1^{s_1}(x)\Vert H_2^{s_2}(x)$ is collision-resistant if either component is (a collision must collide in both). That is useful for hedging between candidate designs. It does not hold for (second-)preimage resistance: a contrived component that leaks its input breaks the combination.

Hash functions in practice

WarningUnkeyed hashes don’t fit the asymptotic definition

Real hashes have no Gen and fixed output length.

For a fixed compressing $H$ , a collision $(x,x')$ exists, so the constant algorithm “print $x, x'$ ” succeeds with probability 1. No analogue exists for a randomly keyed family.
Fixed output length means no security parameter: a collision is always findable in constant time $2^{\ell/2}$ .

The meaningful claim is concrete: no known feasible algorithm finds collisions.

NoteReconciling theory and practice

The fixed $IV$ and constants can be viewed as a key $s$ chosen once and used by everyone for years, which is acceptable even in theory.
Reductions are constructive: “breaking the scheme yields an actual collision” is a meaningful guarantee if nobody can exhibit one.

RemarkMD5, SHA-1 and successors

MD5 (128-bit output, birthday about $2^{64}$ ) and SHA-1 (160-bit, about $2^{80}$ ) iterate compression functions in Merkle–Damgård style. Wang et al. (2004–5) produced practical MD5 collisions (now found in minutes, including colliding PostScript files with arbitrary chosen content) and a $2^{69}$ SHA-1 attack, below the birthday bound. Never use MD5 where collision or even second-preimage resistance matters. This drove adoption of SHA-2 (256- and 512-bit outputs) and a new standard. (Since then, the first explicit SHA-1 collision was published in 2017, “SHAttered”, and SHA-3, a non–Merkle–Damgård sponge, was standardised in 2015.)

NMAC and HMAC

DefinitionSecretly keyed hashing via the IV

For a Merkle–Damgård hash $H^s$ with compression function $h^s$ (output $n$ bits):

$h^s_k(x) := h^s(k\Vert x)$ , keying the compression function’s chaining input;
$H^s_k(x) := H^s$ computed with $IV = k$ secret, so the first step is $h^s(k\Vert x_1) = h^s_k(x_1)$ .

AlgorithmNMAC (Construction 4.13)

Keys $s$ and $k_1, k_2\leftarrow\{0,1\}^n$ :

$\mathrm{NMAC}^s_{k_1,k_2}(x) = h^s_{k_1}\big(H^s_{k_2}(x)\big)$

The inner keyed hash compresses $x$ to $n$ bits; the outer keyed compression function acts as a fixed-length MAC on that digest.

TheoremTheorem 4.14 — Security of NMAC

If the secretly keyed $\hat H$ (IV = $k$ ) is collision-resistant and the secretly keyed $\hat h$ (prefix $k$ ) is a secure fixed-length MAC, then NMAC is a secure arbitrary-length MAC. This is hash-and-MAC; the same proof appears for signatures in Chapter 12.

ProofSketch: a forgery either collides or forges the outer MAC

Let $m^*$ be the forged message and $\mathcal Q$ the queries.

Some $m\in\mathcal Q$ has $H^s_{k_2}(m) = H^s_{k_2}(m^*)$ : a collision in the keyed inner hash, contradicting collision resistance.
Otherwise $H^s_{k_2}(m^*)$ is a new input to $h^s_{k_1}$ . The adversary has forged the fixed-length MAC $h^s_{k_1}$ on messages of the form $H^s_{k_2}(\cdot)$ .

∎

NoteWhy key the inner hash?

If $H^s$ is truly collision-resistant, $k_2$ is unnecessary. Keying it is a hedge: collisions in $H^s$ needn’t give collisions in $H^s_k$ ; the attacker can’t compute the keyed hash offline and must get MAC values from honest parties; and it sees only the outer output. The hedge is weaker than it looks: modern attacks work for any IV, and any known prefix’s chaining value acts as an IV. The proof doesn’t exploit the outer hiding.

AlgorithmHMAC (Construction 4.15)

NMAC needs a custom IV, which libraries don’t expose. HMAC uses the standard IV and a single key, padded to the block length:

$\mathrm{HMAC}_k(x) = H\Big((k\oplus\mathrm{opad})\ \Vert\ H\big((k\oplus\mathrm{ipad})\ \Vert\ x\big)\Big)$

with fixed constants: ipad = 0x36 repeated, opad = 0x5C repeated (RFC 2104).

TheoremTheorem 4.16 — HMAC is NMAC with derived keys

The first compression call of each hash derives the keys: $k_2 = h^s(IV\Vert k\oplus\mathrm{ipad})$ and $k_1 = h^s(IV\Vert k\oplus\mathrm{opad})$ . The outer hash of a single digest block is one keyed compression call, so

$\mathrm{HMAC}_k(x) = h^s_{k_1}\big(H^s_{k_2}(x)\big) = \mathrm{NMAC}_{k_1,k_2}(x)$

If additionally $G(k) = h^s(IV\Vert k\oplus\mathrm{opad})\ \Vert\ h^s(IV\Vert k\oplus\mathrm{ipad})$ is a PRG (length-doubling), HMAC is a secure MAC.

WarningWhy not just $H(k\Vert m)$ ? (Exercise 4.13)

With Merkle–Damgård, the tag $h(z_B\Vert L)$ is the chaining value after an extra “block” $L$ . So from the tag on $m$ alone, anyone can continue the iteration over appended blocks $y$ and output the tag on $m' = m\Vert\mathrm{pad}\Vert\langle L\rangle\Vert y$ without the key: length extension. This is why HMAC’s outer keyed hash exists. HMAC arrived at the right time (practitioners called CBC-MAC “too slow” and were using such broken heuristics) and became an industry standard: efficient, simple, and provably secure under assumptions believed true of practical hashes.

CCA-secure encryption from encrypt-then-MAC

AlgorithmConstruction 4.17

Given CPA-secure $(\mathrm{Enc},\mathrm{Dec})$ and a secure MAC, with independent keys $k_1, k_2$ :

$\mathrm{Enc}'(m)$ : $c\leftarrow\mathrm{Enc}_{k_1}(m)$ , $t\leftarrow\mathrm{Mac}_{k_2}(c)$ , output $(c,t)$ .
$\mathrm{Dec}'(c,t)$ : if $\mathrm{Vrfy}_{k_2}(c,t) = 1$ output $\mathrm{Dec}_{k_1}(c)$ , else $\perp$ .

Idea: the adversary can’t create new valid ciphertexts, so the decryption oracle becomes useless.

DefinitionUnique tags

Each $(k,m)$ has exactly one valid tag. Construction 4.3, CBC-MAC and HMAC have unique tags; Construction 4.5 (random $r$ ) does not.

TheoremTheorem 4.18 — CPA + MAC with unique tags ⇒ CCA

If $\Pi_E$ is CPA-secure and $\Pi_M$ is a secure MAC with unique tags, Construction 4.17 is CCA-secure.

ProofTwo reductions: decryption queries are useless, then CPA

Step 1: New valid decryption queries are negligible. Let $\mathsf{validQuery}$ be the event that $\mathcal A$ submits a decryption query $(c,t)$ that wasn’t output by the encryption oracle yet doesn’t decrypt to $\perp$ . Build a forger $\mathcal A_{\mathrm{mac}}$ : pick $k_1$ itself, guess $i\leftarrow[q(n)]$ , and simulate encryption using its MAC oracle. Answer decryption queries from its table of past encryptions (else $\perp$ ). Output the $i$ -th decryption query as the forgery. Unique tags guarantee $c$ was never MAC’d (otherwise $(c,t)$ would have come from the encryption oracle), so a valid new pair is a real forgery. The simulation is perfect until the first valid query, giving success at least $\Pr[\mathsf{validQuery}]/q(n)$ . Hence $\Pr[\mathsf{validQuery}]$ is negligible.

Step 2: Reduce to CPA. $\mathcal A_{\mathrm{enc}}$ picks $k_2$ , forwards encryption queries to its CPA oracle, attaches tags, answers decryption queries from its table (else $\perp$ ), and relays the challenge. On $\neg\mathsf{validQuery}$ the views are identical. If $\mathcal A$ had advantage $\varepsilon$ , then $\Pr[\mathcal A_{\mathrm{enc}}\text{ wins}] > \frac12 + \frac\varepsilon2$ , a contradiction.

∎

NoteUnique tags and “useless” oracles

Without unique tags, change the challenge’s tag to another valid one, query its decryption, and get $m_b$ . Exercise 4.14 shows Construction 4.5 still works under a strong unforgeability requirement: even a new tag on an already-queried message is a forgery. Making the decryption oracle useless is the point: real adversaries can at best decrypt ciphertexts the honest parties already sent.

Combining privacy and authentication

DefinitionSecure combination (Def. 4.19)

With independent keys $(k_1,k_2)$ , a combination $\mathrm{EncMac}'$ with $\mathrm{Dec}'$ and $\mathrm{Vrfy}'$ is secure if it is both CCA-secure as encryption and existentially unforgeable as a MAC. The standard is all-or-nothing: it must be secure for every CPA-secure scheme and every secure MAC, because libraries and standards swap components (3DES → AES).

WarningEncrypt and authenticate: $(\mathrm{Enc}_{k_1}(m),\ \mathrm{Mac}_{k_2}(m))$

Insecure. A secure MAC may leak $m$ : $\mathrm{Mac}'_k(m) = (m,\mathrm{Mac}_k(m))$ is still unforgeable. Even with real MACs (Exercise 4.15): CBC-MAC and HMAC are deterministic, so equal messages get equal tags. That breaks multi-message eavesdropping security outright (did the client send the same command twice?).

WarningAuthenticate then encrypt: $\mathrm{Enc}_{k_1}(m\Vert\mathrm{Mac}_{k_2}(m))$

Not generically secure. Counterexample: encode each bit, $0\mapsto00$ and $1\mapsto01$ or $10$ (arbitrarily), with $11$ decoding to $\perp$ , then encrypt with a fresh-pad stream cipher (CTR with random IV, still CPA-secure). To learn the first bit, flip the first two ciphertext bits and ask only whether the result is valid:

bit 1: $01\leftrightarrow10$ , still decodes to 1, valid;
bit 0: $00\to11$ , decodes to $\perp$ , invalid.

Repeat for every bit to decrypt fully, using only a validity oracle, which is very realistic. Specific instantiations can be secure (SSL’s, per Krawczyk), but relying on that is bad practice. (Real-world descendants are padding-oracle attacks: Vaudenay 2002, Lucky 13 in 2013.)

TheoremTheorem 4.20 — Encrypt then authenticate is secure

$(c,t)$ with $c = \mathrm{Enc}_{k_1}(m)$ and $t = \mathrm{Mac}_{k_2}(c)$ , for any CPA-secure scheme and any secure MAC, is a secure combination. CCA security is Theorem 4.18; unforgeability follows by reduction to the MAC as in its Step 1 (Exercise 4.16). It upgrades CPA to CCA.

NoteSecure combination versus CCA security

A secure combination gives CCA security plus authenticity. CCA security alone needn’t give authenticity: they are different goals that happen to share a construction.

WarningUse independent keys for different goals

With $\mathrm{Enc}_k(m) = F_k(r\Vert m)$ (CPA-, even CCA-secure) and $\mathrm{Mac}_k(c) = F^{-1}_k(c)$ (a secure MAC since $F^{-1}$ is also a PRP), sharing one key gives $\mathrm{Mac}_k(\mathrm{Enc}_k(m)) = r\Vert m$ : the plaintext in the clear. Reusing keys across goals needs its own explicit proof.

RemarkEncrypt or also authenticate?

Default to both. Even disk encryption benefits: undetected edits to financial files can cause real harm, and missing integrity can even leak secrecy (the authenticate-then-encrypt attack above).

Remaining exercises

ExampleMACs with a verification oracle (Exercise 4.2)

Add a $\mathrm{Vrfy}_k$ oracle to the forgery experiment: real attackers learn whether forged packets are accepted.

Deterministic MACs (unique tags): equivalent to Definition 4.2. Before any successful forgery, every Vrfy query on a new message answers 0 (except negligibly), and queries on old messages are answerable from the transcript. A reduction guesses the index of the first accepting query, losing a factor $q$ .
Probabilistic MACs: not equivalent. A scheme can have many valid tags whose acceptance pattern leaks key bits, for example verification that accepts slightly malformed tags depending on a key bit, so Vrfy queries reconstruct the key.

(Sketch worked here.)

Quick reference

Object	Statement	Note
Malleability	stream/CTR/OFB bit flips; CBC IV flips; ECB reordering	encryption ≠ integrity
MAC security	no valid tag on a new message after adaptive queries	tags $\omega(\log n)$ bits
Replay	the application’s job	sequence numbers, timestamps
PRF MAC	$t = F_k(m)$	forgery $\le2^{-n} + \mathrm{negl}$
Variable-length	$F_k(r\Vert d\Vert i\Vert m_i)$	binds position, length, message
CBC-MAC	$t_i = F_k(t_{i-1}\oplus m_i)$ , output $t_\ell$	fixed length only; IV 0; last block only
Fixes	length-keyed; prepend length; encrypt last block	appending length is insecure
Collision resistance	ppt can’t find $x\ne x'$ with $H^s(x) = H^s(x')$	⇒ second preimage ⇒ preimage
Birthday	about $2^{\ell/2}$ evaluations	output ≥ 2 × security bits
Merkle–Damgård	$z_i = h(z_{i-1}\Vert x_i)$ , output $h(z_B\Vert L)$	collision in $H$ ⇒ collision in $h$
Practice	MD5 broken; SHA-1 broken (2017 collision); SHA-2, SHA-3	unkeyed: concrete security
NMAC	$h_{k_1}(H_{k_2}(x))$	keyed CR inner + MAC outer
HMAC	$H(k\oplus\mathrm{opad}\Vert H(k\oplus\mathrm{ipad}\Vert x))$	NMAC with PRG-derived keys
$H(k\Vert m)$	insecure	length extension
Encrypt-then-MAC	CPA + MAC (unique tags) ⇒ CCA + authenticity	the safe default
Encrypt-and-MAC, MAC-then-encrypt	not generically secure	tag leaks; validity oracle
Keys	independent per goal	shared key can leak $m$

Facts to keep to hand

Authentication is its own goal. Encryption leaves ciphertexts malleable. A MAC must resist forgery on any new message under adaptive chosen-message attack. Replays are the application’s problem.
PRFs make MACs; details make them variable-length. $F_k(m)$ is a fixed-length MAC. Variable length needs binding of order, length and message (Construction 4.5) or CBC-MAC with a proven length fix. Small deviations (random IV, all blocks output, appended length) break it.
Collision resistance is limited by the birthday bound and built by Merkle–Damgård. Generic attacks cost about $2^{\ell/2}$ ; MD reduces arbitrary lengths to a compression function; practical hashes are unkeyed and judged concretely, and MD5 and SHA-1 have fallen.
Hash-based MACs need nesting; combinations need encrypt-then-MAC. HMAC (NMAC with derived keys) defeats length extension. Encrypt-then-MAC with independent keys turns CPA security into CCA security plus authenticity. The other two orders fail generically.

References

Katz & Lindell, Introduction to Modern Cryptography — Chapter 4
Bellare, Kilian & Rogaway, “The Security of the Cipher Block Chaining MAC” (2000)
Bellare, Canetti & Krawczyk, “Keying Hash Functions for Message Authentication” (1996) — NMAC/HMAC
Bellare & Namprempre, “Authenticated Encryption: Relations among Notions” (2000); Krawczyk, “The Order of Encryption and Authentication” (2001)

Related