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?