1

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
Adversary A^Mac(k,·),Vrfyk(·,·)
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?

eddydee123
  • 147
  • 11
  • 1
    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... – kelalaka Nov 15 '21 at 21:26
  • 2
    Hint: state the goal of an adversary against a MAC. Why is not that goal reached? – fgrieu Nov 15 '21 at 21:30
  • What textbook are you using? – hft Nov 15 '21 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. – Manish Adhikari Nov 16 '21 at 06:12
  • 1
    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. – poncho Dec 16 '21 at 22:53

2 Answers2

1

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

hft
  • 219
  • 3
  • 10
  • This might quite HW and we don't answer them, rather provide some hints on the comments – kelalaka Nov 15 '21 at 22:47
  • 1
    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 '21 at 04:23
  • Well, we don't provide answers, we only provide comments. – kelalaka Nov 16 '21 at 08: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 '21 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. – kelalaka Nov 16 '21 at 18:50
  • I can see that Lindell's answer has 18 up 4 down votes and wins the community decision by margin of 6. – kelalaka Nov 16 '21 at 18:52
  • ok, sounds good. – hft Nov 17 '21 at 20:49
-2

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

Sezzart
  • 49
  • 5
  • This might quite HW and we don't answer them, rather provide some hints on the comments – kelalaka May 21 '22 at 12:58
  • Also, did you consider that one need second image attack to forge a message not collision attack! – kelalaka May 21 '22 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. – Sezzart May 21 '22 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.. – kelalaka May 21 '22 at 17:19