MAC unforgeability and secret key guessing

Question

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?

Answer 1

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?

Answer 2

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