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

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?


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


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.