How can I resolve this basic MAC paradox I’m stumbling upon in my proof? Suppose $S: K \times M \to T$ is a secure MAC. ($K$ = key space, $M$ = message space, $T = \{0,1\}^n$ = tag space.)

$S$ being secure means that no matter what messages $m_1,...,m_q$ we throw at $S$ to get back tags $t_1,...,t_q$:

$\{ (m_1,t_1),...,(m_q,t_q) \}$

we cannot subsequently find another message-tag pair $(m,t)$ that is not in the above set. In other words, we cannot find a forgery $(m,t)$.



Let's create a new MAC $S'$ based on $S$:

$S'(k,m) = (S(k,m), S(k,0^n))$

It is clear by example that $S'$ is not secure. The attack is simple: Throw at $S'$ some $m \neq 0^n$, and extract the value $s = S(k,0^n)$ out of the tag. Then, the message $0^n$ and tag $(s,s)$ is our forgery.



Here is the paradox. I believe I can prove that if $S'$ can be forged, than so can $S$. This would prove that if $S$ is secure (as we assumed), $S'$ is secure! There must be something wrong with my proof, so my question is, what is wrong with the following proof?

Assume $S'$ can be forged. In other words, we have thrown at $S'$ messages $m_1,...,m_q$ and gotten back the tags $t_1 = S'(k,m_1), ..., t_q = S'(k,m_q)$ and subsequently obtained a forgery message-tag pair $(m, t = S'(k,m))$ such that

$(m, S'(k,m)) \notin$ $\{ (m_1,S'(k,m_1)),...,(m_q,S'(k,m_q)) \} $

In other words,

$(m, (S(k,m),S(k,0^n))) \notin$ $\{ (m_1,(S(k,m_1),S(k,0^n))),...,(m_q,(S(k,m_q),S(k,0^n)))\}$ (*)

Then it seems obvious that the following is our forgery on $S$:

$(m, S(k,m)) \notin$ $\{ (m_1,S(k,m_1)),...,(m_q,S(k,m_q)) \} $

because $(m, S(k,m))$ being an element in that set would contradict (*).

That's the end of my proof. There must be something wrong with it. The question is, what?
Your attack on $S$ involves computing $S'(k,m_i)$ for arbitrary messages $m_1,\dots,m_q$. In order to do that, you must compute $S(k,m_i)$ and $S(k,0^n)$, and thus you have obtained $S(k,0^n)$. This means that $0^n$ must be added to the list of invalid forgeries, and so in order to present a valid forgery for $S$, you must have
$$(m,S(k,m)) \notin \{(0^n,S(k,0^n),(m_1,S(k,m_1)),\dots,(m_q,S(k,m_q))\}.$$

But you do not know how to do that: the only known attack on $S'$ precisely involves computing $S(k,0^n)$. More precisely, the attack goes like this:


Compute $S'(k,m)$ for some $m \ne 0^n$.
Output $(0^n, (s,s))$ as a forgery for $S'$ (where $s = S(k,0^n)$).


Then, you present $(0^n, s)$ as a forgery for $S$, but this is not a valid one.

The exact point where this error manifests itself in your proof is when you write


  because $(m,S(k,m))$ being an element in that set would contradict (*).


This assumes that if $(m,S(k,m))$ is in the second set, that necessarily means that $(m,S'(k,m))$ is in the first one. In other words, that if a "request" for $S(k,m)$ was made, it necessarily means that a request for $S'(k,m)$ was made as well. This is, again, not correct: it is possible to make a request for $S(k,0^n)$ without making one for $S'(k,0^n)$.