# MAC unforgeability and secret key guessing

The standard notion security for MACs is usually expressed by means of experiments like the following one (given an attacker A):

1. $k \leftarrow \mathsf{KG}(1^\lambda)$
2. Invoke $A^{\mathsf{TAG}_k(\cdot),\mathsf{VRFY}_k(\cdot,\cdot)}$
3. Output $1$ if $A$ queried $(m^*,\tau^*)$ to $\mathsf{VRFY}_k(\cdot,\cdot)$ s.t. $\mathsf{VRFY}_k(m^*,\tau^*) = \mathsf{Accept}$ and $A$ didn't receive $\tau^*$ by querying $m^*$ to $\mathsf{TAG}_k(\cdot)$

Now consider the following variation to point 3: Output $1$ if $A$ gives $k'$ s.t. $k=k'$

How could I prove that a MAC unforgeable according to the first game is unforgeable according to the second game too? Is there a specific $\mathsf{MAC}(\mathsf{KG},\mathsf{TAG},\mathsf{VRFY})$ that is unforgeable according to the second game, but not according to the first one?

• contrapositive ​ ​ – user991 Jul 9 '16 at 12:28
• Your notation seems a bit confused. Are $\kappa$ and $k$ supposed to be the same thing? And what does $= \leftarrow$ mean? – Ilmari Karonen Jul 9 '16 at 17:24

I was going to make this a comment; however you asked for hint, and these are hints.

Suppose you had an Oracle that solved the second game for you; how could you use that Oracle to solve the first game?

Does that imply that a MAC where the first game is unsolvable imply that the second game is also unsolvable?

Thanks to everyone for the hints and comments. I would like to propose you my proof by contradiction and kindly ask for a further comment.

Being $\pi=(KG,TAG,VRFY)$ an uuf MAC according to the first game, we suppose that $\pi$ isn't uuf according to the second one. On the basis of this hypothesis, an attacker A can guess the secret key $k$. More formally, $A$ gives $k'$ s.t. $k=k'$.

In such a condition, given a fresh message $m^*$, $A$ can compute the authenticator $\tau^*$ without querying the oracle, because he has got the key $k$ and full knowledge of the tag function $TAG_k(\cdot)$. Therefore the initial assumption must be false.

Considering the $TAG$ function $H(k||m)$, where $H$ is a Merkle-Damgard collision-resistant hash function and $||$ indicates concatenation , we could find a specific MAC $\overline{\pi}=\overline{(KG,TAG,VRFY)}$ which is uuf according to the second game, because the attacker $A$ can't reconstruct the key $k$ it by knowing the stored hash value.

$\overline\pi$ isn't however uuf according tho the first game: given a couple $(m,\tau)$ s.t. $VRFY_k(m,\tau) = Accept$, the attacker $A$ could straightforwardly forge an authenticator $\tau^*$ for the message $m^*=m||pad_m||m'$ s.t. $VRFY_k(m^*,\tau^*)=Accept$

Thank you again, FG

• You seem to have created two accounts. You could look into merging them so that you can accept the correct answer. – otus Jul 11 '16 at 11:21
• I actually posted twice as a guest; can I merge the accounts anyway? – Frank Gerritz Jul 11 '16 at 12:07
• I'm not sure. You can try. – otus Jul 11 '16 at 12:21