Why is a weakly secure MAC without verification queries not necessarily weakly secure in the presence of verification queries?

Question

I'm self-studying cryptography from A Graduate Course in Applied Cryptography by Boneh and Shoup (version 0.5), and I'm having trouble seeing the result in Exercise 6.7.

In the book a secure MAC system is defined in terms of an attack game where an adversary can perform signing queries on arbitrary messages to receive tags. The adversary sends messages $m_1, m_2, \ldots, m_Q$ to its challenger and receives the tags $t_1, t_2, \ldots, t_Q$. Security is measured by the probability of the adversary winning by presenting a message-tag pair forgery $(m, t)$ where the pair $(m, t) \notin \{(m_1, t_1), \ldots, (m_Q, t_Q)\}$. Later, a new attack game is created where the adversary can also perform verification queries in which the adversary proposes a message-tag pair $(m, t)$ and receives either a $\textsf{accept}$ or $\textsf{reject}$ depending on if the pair is valid or not. Security is measured by the probability of the adversary receiving a $\textsf{accept}$ for a message-tag pair $(m, t) \notin \{(m_1, t_1), \ldots, (m_Q, t_Q)\}$.

Theorem 6.1 in the book shows that security under the first attack game implies security under the second attack game. Exercise 6.7 asks to demonstrate this result not holding if we modify the winning conditions to presenting a $(m, t)$ forgery where $m \notin \{m_1, m_2, \ldots, m_Q\}$. Under this new condition, we get the definition of weak security with/without verification queries. The hint is to use a secure PRF that can be "sabotaged".

I am having trouble understanding how this result on weak security holds. Looking at the proof of Theorem 6.1, it is not clear why that proof cannot extent to weakly secure MACs as the proof seems to never make any explicit use of the $(m, t) \notin \{(m_1, t_1), \ldots, (m_Q, t_Q)\}$ condition. Thus, I guessed naively that the proof for Theorem 6.1 would still work. Why does this proof break down for weakly secure MACs?

From looking at the hint, the only thing that comes to my mind is that somehow getting a rejection from a verification could reveal information about the PRF used to create MACs. Thus I would need to somehow create a PRF that loses its security after an adversary learns of some sort of rejection. I am at a lost for how such a construction might work. I also have a feeling that I would need to create nondeterministic MACs, but again it isn't clear to me how I would construct a relevant one.

Answer 1

Thanks to Samuel Neves for pointing me in the right direction. I took a look at the reference mentioned, and it touches on how Theorem 6.1 fails for weak security. It also covers a MAC that is weakly secure without verification queries but loses its security in the presence of verification queries.

Why Theorem 6.1 breaks down

I found that the subtlety occurs in how the attack games are defined. The adversary can send any message-tag pair $(m, t)$ for verification so long as it is not among the previously signed pairs. What's important is that in the original definition of security the adversary wins the attack game if and only if the adversary sends a valid, previously unseen message-tag pair for verification. The equivalency follows from the definition of the winning condition.

However, under weak security, the forward direction still holds (sending a valid $(m, t)$ pair where $m$ has never been seen before clearly forms a valid never before seen pair) but the backwards direction fails. The backwards direction could fail because the adversary could obtain a $(M, T)$ pair from a signing query and then submit a valid $(M, \bar{T})$ pair by modifying the tag $T$. $(M, \bar{T})$ is a valid and previously unseen pair, but the adversary fails to win because the pair involves a message that was previously signed.

Where Theorem 6.1 fails for weak security is when the authors assert $\text{Pr}[W_0] = \text{MAC}^\text{vq}\text{adv}[\mathcal{A, I}]$ which assumes winning the attack game is equivalent to presenting a valid, previously unseen message-tag pair. In the above extreme example above, this is not the case as it is possible for $W_0$ to occur but without winning the weak security attack game.

How to solve the exercise

As for how to construct a MAC system that is weakly secure without verification queries but is not weakly secure with verification queries, you basically construct a system where after receiving $(M, T)$ from a signing query an adversary can easily construct valid $(M, \bar{T})$ pairs. By presenting these valid but not-winning pairs, the adversary learns enough information to break the MAC system.

Let $\mathcal{K} = \{0,1\}^\ell$ and $|\mathcal{T}|$ be super-poly. Let $F$ be a PRF defined over $(\mathcal{K, M, T})$, $k \stackrel{R}{\gets} \mathcal{K}$ and $\mathcal{I} = (S, V)$ be a MAC defined over $(\mathcal{K, M, T} \times \{\perp, 0,\ldots,\ell-1\})$. The signing algorithm is defined to be $S(m) = (F(k, m), \perp)$ and the verification algorithm is

V(m, (t, i))
    // Validate tag against PRF
    d = F(k, m) == t
    if !d or i == ⟂
       return d ? accept : reject

    // Return ith bit of the key
    return k[i] == 1 ? accept : reject
    

The correctness property hold because the second component of $S(m)$ is $\perp$ which enters the if statement. This MAC system essentially is the deterministic MAC system derived from $F$ but with an extra index field.

First we notice that $\mathcal{I}$ is weakly secure without validation queries. If an adversary wins, then the adversary submitted a valid pair $(m, (t, i))$ where $m$ was not seen before. This means $\textsf{accept}$ was returned which implies $d$ is true in $V(m, (t, i)))$ (either the if statement was entered where $\textsf{accept}$ was returned or the if statement did not execute which implies $d$ was not false). This happens with negligible probability by Theorem 6.2 as $d$ being true means a forgery was made against the deterministic MAC derived from $F$ (this MAC is secure under the stronger definition of security).

However, $\mathcal{I}$ is not weakly secure with verification queries. An adversary that breaks the security is

Let m be an arbitrary message
Obtain (m, (t, ⟂)) from the challenger

k[0..l-1] = 0
for i = 0 .. l-1
    Let r be the challenger's response to the validation query (m, (t, i))
    if r == accept
        k[i] = 1
    else
        k[i] = 0

// The key has been reconstructed
Let m' be an arbitrary message not equal to m

// Compute the tag of m' with the reconstructed key
Let t' = S(m')
Send the validation query (m', (t', ⟂)) to the challenger