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

  • $\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 '16 at 18:55

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.

  • $\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 '16 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.