# Show that if a fixed key MAC is not collision resistant then the MAC function is not computation resistant for every key K

I'm really having some trouble with this one.

Let $$H$$ be a MAC function. For every key $$K$$ we can create an unkeyed hash function (i.e.an MDC) by using $$H$$ to hash messages with the fixed key $$K$$. We denote this unkeyed hash function by $$H_K.$$ (Note that every key $$K$$ gives a different hash function $$H_K$$. Therefore, we can create a large family of MDC functions from a single MAC function, one for each key).

Show that if $$H_K$$ is not collision resistant, then $$H$$ is not computation resistant for every key $$K$$.

Make your argument as clear as possible.

• Well I am sure that I am required to prove that if there exists M, M' s.t. HK(M)=HK(M') IS computationally feasible (not collsition resistant) then this implies --> given M, MAC(K,M) (one message -mac pair) and M' it is computationally possible to compute MAC(K,M') Now we know if HK has a n-bt output we can find a collsion after check 2^(n/2) and I am guessing I need to use the fact one one could perform a meet in the middle attack the M and MAC(K,M) which again you would have to check 2^(n/2) ? Commented Nov 13, 2018 at 12:48
• HK is not collision resistant means that you can find a collision, no need to go birthday attack. Now assume that you find a collision. Commented Nov 13, 2018 at 13:02
• Well, HK is not collision resistant so we expect a collision [HK(M)=HK(M')] after hashing 2^(n/2) inputs (birthday paradox). Thus we have found for Key K two Messages that have the same hash value. and therefor these messages when pumped through the MAC with Key K will have the same MAC value? Commented Nov 13, 2018 at 13:04
• Yay :) no it doesn't however I do have a Q that says an attacker can perform 10^21 hach operations a second, how many years would it take to perform a brute force birthday attack on SHA-256. I put 2^128/(10^21x60x60x24x7x52) which is ~ 1.8 billion years. I wasn't sure about this as this seems like a huge number Commented Nov 13, 2018 at 13:22
• On the off topic calculation: well, you're some 2.25 billion days off (or more if you consider the slow down of the earths' rotation), but don't let that stop you :). Commented Nov 13, 2018 at 14:16

By my read of the question, I don't see why this is even correct. It does depend on how one interprets that "H is not computation resistant for every key K". I assume that this just means that $$H$$ is not computation resistant for a randomly chosen key $$K$$. Otherwise, I'm not sure what it would mean.
Now, the straightforward way you would try to prove this is to find a collision in $$H_K$$ and use this to break the MAC. However, the fact that $$H_K$$ is not collision resistant for a fixed $$K$$ means that when you are given the function description, you can find a collision. However, this doesn't mean that you can also do it when you are not given the function description. To be very concrete, define $$H_K$$ as follows. Parse $$K$$ into a key for a PRF and into the description of a group where the discrete log is assumed to be hard, along with a generator $$g$$ and random value $$a$$ and value $$h=g^a$$. The function works by first hashing the message using $$hash(x_1\|x_2)=g^{x_1}\cdot h^{x_2}$$ (using Merkle-Damgård based on this compression function, you get a full-blown hash function) and then applying the PRF. Now, if you know the value $$a$$, then it's easy to find collisions. Thus, $$H_K$$ is not collision resistant for any fixed key, since in the fixed-key setting you know $$K$$. However, in the standard MAC setting where you don't know $$K$$ and so don't know $$a$$, this will be a secure MAC (under the assumption that the discrete log problem is hard in this group).
So, I must be misreading the question somewhere. Either there is something in the quantifiers with the "for every key $$K$$" that I am misreading, or the intention of what a fixed-keyed hash function is is different to what I understand. Or there's an error in the question...