0
$\begingroup$

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.

Improve this question
$\endgroup$
14
  • $\begingroup$ 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) ? $\endgroup$
    – countduckula
    Commented Nov 13, 2018 at 12:48
  • $\begingroup$ 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. $\endgroup$
    – kelalaka
    Commented Nov 13, 2018 at 13:02
  • $\begingroup$ 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? $\endgroup$
    – countduckula
    Commented Nov 13, 2018 at 13:04
  • $\begingroup$ 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 $\endgroup$
    – countduckula
    Commented Nov 13, 2018 at 13:22
  • 1
    $\begingroup$ 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 :). $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 13, 2018 at 14:16

1 Answer 1

Reset to default
2
$\begingroup$

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.

According to this understanding, I don't see why the statement is true. From here on, I will use the term "a secure MAC" rather than "computation resistant", since this is more standard terminology.

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

In any case, I wrote this out in detail since I think it has value.

Improve this answer
$\endgroup$

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.