1
$\begingroup$

In standard secret-suffix fashion, assume we compute the PRF of some message $m$ as $MD5(x || k)$. Preneel and Van Oorschot showed in [1] that this secret-suffix method is unsatisfactory for constructing a secure MAC. (Particularly because MD5 is not collision resistant and therefore the scheme is susceptible to forgeries.) But does that also mean this is not a secure PRF?

[1] http://people.scs.carleton.ca/~paulv/papers/Crypto95.pdf

$\endgroup$
1
  • $\begingroup$ This isn't a homework question -- and I am aware of both facts. I guess the answer is "yes" by virtue of contrapositive equivalence. That is, if PRF => MAC is true then ~MAC => ~PRF is also true. I just needed a sanity check. :) $\endgroup$
    – caw
    Oct 3, 2016 at 18:55

1 Answer 1

1
$\begingroup$

The collision resistance of MD5 is fully broken, for 2 rounds, or even just 1 round. If follows that we can exhibit distinct 1024-bit or even 512-bit $x_0$, $x_1$ such that for any $k$, $\operatorname{MD5}(x_0||k)=\operatorname{MD5}(x_1||k)$.

This allows to make a near-perfect distinguisher between the PRF (family) parametrized by $k$: $x\to\operatorname{MD5}(x||k)$, and a random oracle; thus breaking that PRF.

$\endgroup$
1
  • $\begingroup$ Yep -- I acknowledged this in my comment above. As I mentioned, I just needed a sanity check. Thank you for your (second) response. $\endgroup$
    – caw
    Oct 3, 2016 at 20:09

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.