# Why is birthday attack invalid on this MAC

I am trying to understand why the following birthday attack is invalid for this MAC construction.

Let Mac : $$\{0, 1\}^{128} \times \{0, 1\}^{256} \to \{0, 1\}^{128}$$ be a MAC. Consider the following adversary $$A$$, that is meant to work with Expt $$Mac(A)$$:

1
Initialize an empty hash table Y .
For m ∈{0, 1}^256:
Query y ←Mac(k, m)
If y ∈Y :
m′ ←Y [y]
Query Vrfyk(m′, y) and halt
Else:
Y [y] ← m


According to my professor, by the birthday bound, this attack should terminate in approximately $$2^{64}$$ iterations of the loop, which is practical for a strong adversary. But this is not a valid attack. Why?

• Welcome to Cryptography.SE. We have $\LaTeX$/MathJax in our site. You can edit your question to become more clear since only some part was convertible at least for me. Note that if this is homework, please indicate this and show your work... Nov 15, 2021 at 21:26
• Hint: state the goal of an adversary against a MAC. Why is not that goal reached?
– fgrieu
Nov 15, 2021 at 21:30
• What textbook are you using?
– hft
Nov 15, 2021 at 22:24
• This question is hard to follow as you have not even explained how Y is filled in but inferring from your statements, it seems that the adversary finds the collision but does not achieve what he is supposed to be achieving. Nov 16, 2021 at 6:12
• Actually, against CMAC (and XCBC), this is a valid attack - or, at least, make generating additional (M, tag) pairs easy. However, the details of converting the collision into an additional (M, tag) pair is specific to the internals of CMAC/XCBC, and does not apply to a generic MAC construction. Dec 16, 2021 at 22:53

But this is not a valid attack. Why?

It's a valid collision if m and m' are not equal, but it isn't a successful attack on the MAC.

To understand why this would not be described as a "valid attack," consider the description of a successful attack from "Introduction to Modern Cryptography":

An attacker “breaks” the scheme if... (1) t is a valid tag on the message m... and (2) the honest parties had not previously authenticated m...

(Citation: Katz, Jonathan; Lindell, Yehuda. Introduction to Modern Cryptography; Third Edition/Kindle Edition; page 110.)

Consideration of this definition will help you understand if the attack is "valid."

• This might quite HW and we don't answer them, rather provide some hints on the comments Nov 15, 2021 at 22:47
• Hmm. OK, I modified the answer to not be so direct (more like just a hint). I didn't know you only put hints in the comments for HW-like questions here.
– hft
Nov 16, 2021 at 4:23
• Well, we don't provide answers, we only provide comments. Nov 16, 2021 at 8:33
• From the link you provided: "We should not leave the question unanswered... Instead, we should write an answer that contains only the hint and comments..." – kelalaka, Jan 25 '19 at 10:06
– hft
Nov 16, 2021 at 18:46
• It was my comment, however, the accepted answer doesn't contain this. Only hints and in comments. This is a community decision (+6 more votes ( now less is accepted, too)). You can give an answer and it may get a higher vote to change the decision or you can upvote/downvote whatever answer you liked. Downvote doesn't decrease your reputation. You may consider it like voting. Meta is the place where our community decides its problems and applies the suggestions etc. Nov 16, 2021 at 18:50

$$2^{64}$$ is not polynomial but exponential in the size of the key (which is 256 in your case)

• This might quite HW and we don't answer them, rather provide some hints on the comments May 21, 2022 at 12:58
• Also, did you consider that one need second image attack to forge a message not collision attack! May 21, 2022 at 13:01
• It does not really sound like a homework(if that's what you mean) question, more like a failure to understand the concept of PPT. May 21, 2022 at 16:55
• Besides $2^{64}$ is neither polynomial nor exponential. They are constant and the keyspace is $2^{256}$. The OP is left, so high probably it was.. May 21, 2022 at 17:19