Insecure MAC built on pseudorandom function

Question

this is a question about Katz-Lindell book, introduction to modern cryptography, 2nd edition, exercise 4.7, part c.

For (a) and (b) it is clear that the Macs are insecure, but for (c) I am struggling to see why.

For me, when the attacker will present his pair $(m^*, \langle r^*,t^* \rangle)$, the MAC will sample uniformly its own $r$ (before applying the $\operatorname{Vrfyk}(.)$ algorithm), and will prepend $r$ to the computed $t$.

So no matter how the attacker will choose $m^*$ (even if the attacker chooses $m^*$ randomly), the MAC (assuming that it is a deterministic MAC using a canonical verification) will always sample a random $r$ from ${0,1}^n$, independently from the one $(r^*)$ that the attacker output to it, and the probability that $r=r^*$ will be negligible. So it is still secure MAC, the one presented in part (c).

Can someone correct me if I am wrong please?

Answer 1

assuming that it is a deterministic MAC using a canonical verification

It is not, randomness is involved in the tag generation, therefore it is not deterministic and cannot use canonical verification.

This then means that an attacker doesn't have to follow the MAC algorithm but instead has to find $m',(r',t')$ such that verification suceeds, picking $t'=0$ is a good starting point for that.