ISE Cryptography — Quiz Solutions
L04: Message Integrity
10 questions · 1 mark each · 10 marks total.
Q01: MAC correctness
A MAC system \(\mathcal{I} = (S, V)\) satisfies its correctness property when \(\Pr[V(k, m, S(k, m)) = \text{accept}] = 1\) for every key \(k\) and message \(m\). What does this property guarantee?
Answer:
Verification accepts any tag produced by the signing algorithm under the same key.
Q02: What the UF-CMA adversary must produce
In the UF-CMA security game, the adversary \(\mathcal{A}\) issues \(Q\) signing queries and then outputs a candidate forgery \((m, t)\). What must this forgery satisfy for the adversary to win?
Answer:
The pair \((m, t)\) must be distinct from every queried pair and \(V(k, m, t)\) must accept.
Q03: Why existential forgery is the right bar
UF-CMA defines a MAC as broken if the adversary forges any new valid message-tag pair, not just a tag for a specific target message. Why does asking the adversary to do less make the security guarantee stronger?
Answer:
Because every targeted forgery is also an existential forgery, so a MAC that resists existential forgery automatically resists targeted forgery.
Q04: CBC-MAC extension attack
An adversary requests the CBC-MAC tag \(t = F(k, a_1)\) for the one-block message \(m = (a_1)\), then outputs \(((a_1, a_1 \oplus t), t)\) as a forgery on a two-block message. Why does this verify as a valid CBC-MAC tag?
Answer:
Because the second block’s CBC input is \(F(k, a_1) \oplus (a_1 \oplus t) = a_1\), so the final PRF evaluation is \(F(k, a_1) = t\).
Why the algebra works: the tag from the first signing query is \(t = F(k, a_1)\). The adversary constructs the second block as \(a_1 \oplus t\). CBC-MAC chains: the input to the second PRF call is \(F(k, a_1) \oplus (a_1 \oplus t) = t \oplus a_1 \oplus t = a_1\). So the final tag is \(F(k, a_1) = t\) again.
Q05: Why H(k \(\|\) m) is not a secure MAC
A naive MAC defines \(\text{tag} = H(k \| m)\), prepending the key before hashing. This construction is insecure against an adversary who knows the tag and \(|k|\). Why?
Answer:
Because Merkle-Damgård’s iterated chain state lets an adversary continue the hash from the tag, computing \(H(k \| m \| \text{pad} \| m')\) for any chosen suffix \(m'\) without knowing \(k\).
This is the length-extension attack. The Merkle-Damgård chain state after processing \(k \| m \| \text{pad}\) is exactly the output tag \(t\). An adversary who knows \(t\) can initialise a fresh hash at that chain state and process any chosen \(m'\), producing a valid tag for the extended message \(m \| \text{pad} \| m'\) under the same key.
Q06: The PRF-to-MAC reduction bound
Define a MAC from a PRF \(F : \mathcal{K} \times \mathcal{X} \to \mathcal{Y}\) by \(S(k, m) = F(k, m)\). Which inequality correctly bounds the MAC adversary’s advantage?
Answer:
\(\text{MAC}_\text{adv}[\mathcal{A}, \mathcal{I}] \leq \text{PRF}_\text{adv}[\mathcal{B}, F] + 1/|\mathcal{Y}|\), where \(1/|\mathcal{Y}|\) is the random-guess probability.
Why the extra term: if \(F\) were a truly random function, any forgery attempt on a fresh message would succeed with probability exactly \(1/|\mathcal{Y}|\) (random tag over the tag space). The PRF assumption closes the gap between a real \(F\) and a truly random function.
Q07: Encrypt-then-MAC vs MAC-then-Encrypt
Encrypt-then-MAC is generally secure as authenticated encryption, while MAC-then-Encrypt is not. What structural property of Encrypt-then-MAC produces this gap?
Answer:
The MAC lets the receiver reject modified ciphertexts before decrypting, reducing chosen-ciphertext attacks to chosen-plaintext ones.
Q08: Nonce, IV and salt
AEAD nonces, CBC initialisation vectors (IVs), and password-hashing salts are all non-secret auxiliary inputs, but their required properties differ. Which statement correctly characterises all three?
Answer:
A nonce must be unique per key, a CBC IV must be unpredictable per ciphertext, and a salt must be unique per user.
Q09: Why the polynomial one-time MAC fails on reuse
The polynomial one-time MAC with key \((k_1, k_2) \in \mathbb{Z}_p^2\) and tag \(P_m(k_1) + k_2 \bmod p\) is information-theoretically secure for a single message. After observing two signed pairs \((m, t)\) and \((m', t')\) with \(m \neq m'\) under the same key, what can the adversary do?
Answer:
With high probability, recover the full key \((k_1, k_2)\) and forge tags on any chosen message.
Why: the adversary has two equations \(P_m(k_1) + k_2 = t\) and \(P_{m'}(k_1) + k_2 = t'\), both mod \(p\). Subtracting gives \(P_m(k_1) - P_{m'}(k_1) = t - t'\), a polynomial equation in \(k_1\) alone of degree at most \(v\). This has at most \(v\) roots mod \(p\), so \(k_1\) is recoverable with high probability. Once \(k_1\) is known, \(k_2 = t - P_m(k_1) \bmod p\) follows immediately.
Q10: Consequences of AES-GCM nonce reuse
An implementation accidentally encrypts two distinct messages \(m_1\) and \(m_2\) under AES-GCM with the same key \(k\) and same nonce. Which statement best describes the consequences?
Answer:
The XOR \(m_1 \oplus m_2\) leaks the plaintexts and the GHASH key is recovered, enabling tag forgery under the reused nonce.
Why: the CTR-mode keystreams cancel (same nonce \(\Rightarrow\) same keystream), giving \(c_1 \oplus c_2 = m_1 \oplus m_2\). More critically, having two tag equations under the same GHASH key \(H = E_k(0)\) lets an adversary solve for \(H\) over \(\text{GF}(2^{128})\), after which they can forge authentication tags for arbitrary ciphertexts under that nonce.