MAC security game

Question

In the applied cryptography book by Boneh and Shoup, Chapter 6 on MACs, it is stated that one can modify SUF-CMA game by removing verify oracle access to the adversary. Therefore, the two versions are equivalent(within some factor in the advantage).

However, I am a bit confused by this no-verify version of the game. I have already had some explanation on this but I am still lost... Informally it seems to me that since the verification algorithm doesn't appear anywhere in the game, nothing prevents me from defining a MAC that does some kind of verification (i.e conditions to accept or reject) but also behaves insecurely. For instance, the verification algorithm also broadcasts the MAC key.

My first (failed) attempt was, starting with a secure MAC $M$, create a new one $M'$ such that one of the tag values ($\tau$) will never be used. And modify the new verification algorithm to reject any $(m,\tau)$ and output the key on such input. However, this construction doesn't meet the correctness requirement, i.e the output is not a bit. Therefore this counter-example would not be valid

So my questions are as follows:

1. Is it really OK, that the game doesn't use all of the algorithms and will remain secure as long as it is correct?

2. What is wrong with my failed counter-example? Namely, is it or not possible to find a correct counter-example such that the verification algorithm behaves insecurely?

Answer 1

1. Yes, it's really ok. I would recommend trying to read through section 6.2 and understand it better (and ask more questions if needed). They prove that for any adversary $\mathcal{A}$ who expects to be able to make $q$ verification queries, one can make an adversary $\mathcal{A}'$ who makes 0 queries, but still has "fairly high" advantage in a formal way.

2. You are missing that the verification algorithm is a predicate --- it must return "true" on valid tags, and "false" on invalid tags. One cannot make it "broadcast the key" as this would make it return something other than true/false. So essentially the algorithm you suggest is not a verification algorithm, because it returns the incorrect type to be a verification algorithm.