How can I resolve this basic MAC paradox I’m stumbling upon in my proof?

Question

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?

Answer 1

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:

1. Compute $S'(k,m)$ for some $m \ne 0^n$.
2. 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)$.

Answer 2

First remark:

Throw at $S′$ some $m\neq0^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.

Building a forgery is exposing $m$ and $m'$ such as $S'(m,k) = S(m',k')$.

Here you computed: $S'(k,m) = (S(k,m),s) = (\sigma,s)$
and $S'(k,0^n) = (s,s)$
but you do not have a collision between $(\sigma,s)$ and $(s,s)$ or I am missing something. If you take $m = 0^n$ obviously the result will be the same as you have the same inputs.

Second remark:

If $S: K \times M \rightarrow T$ is perfectly secure, then this assumes that for any couple $(k,m)$, there is a single $t$ such as $S(k,m) = t$. In other word, $card(K) \times card(M) \le card(T)$.

Under this assumption, $S'$ can be seen secure as for any $(k,m)$, $S'(k,m) = (S(k,m), \chi)$ will be unique (due to the first coordinate).