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?

  • $\begingroup$ Your forgery on $S$ is for $m = 0^n$. You have already computed the tag for $S(k, 0^n)$, therefore your forgery is not valid. Simple as that. $\endgroup$ Jun 29, 2016 at 23:18
  • $\begingroup$ What this incorrect proof should teach you is to always carefully specify how you simulate the oracles in your security reduction. :) $\endgroup$
    – Maeher
    Jun 30, 2016 at 9:00

2 Answers 2


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)$.


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).

  • $\begingroup$ Can someone verify by proofs ? $\endgroup$
    – Biv
    Jun 29, 2016 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.