8
$\begingroup$

Context: We usually assume that the hash functions we use in practice are both: collision resistant and pseudorandom. I wonder what's the relation between those properties.

Question: Is a pseudo random function always collision resistant?

Clarification: This questions suggests that hash functions are pseudo-random functions, which is often not the case (e.g., see Length extension attack). The main question whether pseudo-randomness implies collision resistance is still a valid question.

Improve this question
$\endgroup$
4
  • $\begingroup$ Possible counterexample: the MD5 compression function, which is conjectured to be a PRF but which probably isn't collision-resistant. However, I'm not sure it fails the technical property of keyed collision-resistant hash family, and the way its PRFness is used to justify NMAC security is a little wacky, so… I don't know! $\endgroup$
    – Squeamish Ossifrage
    Commented Dec 21, 2017 at 18:32
  • $\begingroup$ Some related work eprint.iacr.org/2006/043.pdf. $\endgroup$
    – mti
    Commented Mar 24 at 8:58
  • 1
    $\begingroup$ A PRF with a 1-bit output is obviously not collision resistant... $\endgroup$
    – poncho
    Commented Mar 26 at 22:07
  • 1
    $\begingroup$ @poncho Obviously! Why didn't you point that out 5 years ago? jk It shows that there is one more thing (in addition to what was pointed out in other discussions) that I should have been more precise about when asking this question. Nevertheless, I'm happy with the discussions this question sparked, because it also shows that the details often do matter a lot in cryptography. $\endgroup$
    – mti
    Commented Mar 27 at 20:53

5 Answers 5

Reset to default
3
$\begingroup$

No, a PRF isn't always collision resistant.

Take CBC-MAC, which is a PRF assuming prefix-free messages. If you know the key, you can create a different message that produces the same tag, which is a collision.

With hash-based MACs (e.g., HMAC), this isn't the case assuming a collision-resistant hash function is used and not something cryptographically broken like MD5 or SHA-1.

There's a difference between being weakly collision resistant (collision resistant when the key is unknown) and strongly collision resistant (even when the key is known).

And it turns out this difference matters in practice because a lack of collision resistance is what has lead to commitment attacks on popular AEAD schemes. Key/context commitment has now become a desirable property in new schemes, which can be achieved using the duplex construction or similar.

Improve this answer
$\endgroup$
4
$\begingroup$

First, a PRF is a keyed function, meanwhile a hash function is usually keyless. So, a hash function cannot be a PRF.

Second, a secure PRF can be swapped with a uniform random function without detection, and the best way to find a collision of a uniform random function is the birthday attack. So, if the PRF has superpolynomially large codomain, then it would be collision-resistant, since the birthday attack would take more than polynomial-time.

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ I am considering the keyed setting here. Could you support your second statement by providing an algorithm that given access to a collision finding oracle distinguishes the PRF from a random function? $\endgroup$
    – mti
    Commented Dec 21, 2017 at 16:43
  • $\begingroup$ @mti: I believe the reasoning is "truly random functions with large outputs don't have efficient oracles that find collisions, hence if you have one, you don't have a truly random function" $\endgroup$
    – poncho
    Commented Dec 21, 2017 at 16:47
  • 1
    $\begingroup$ @poncho: What do you mean by "efficient oracle"? Do you mean "efficient algorithm"? Then you are saying that there is no efficient algorithm for finding collisions in a PRF, right? I would like to understand why! Again, I think what one has to show here is that given an algorithm for computing collisions, we can construct an algorithm for distinguishing the PRF from a randomly chosen function. $\endgroup$
    – mti
    Commented Dec 21, 2017 at 17:23
  • 1
    $\begingroup$ In more technical terms: Suppose you had a collision-finder $A(k)$ with cost $C$ for which $\operatorname{Adv}^{\operatorname{Coll}}_H(A) = \Pr[x_0 \ne x_1, H_k(x_0) = H_k(x_1)]$ is significantly better than the birthday probability for $q$, where $k$ is uniform random and $(x_0, x_1) = A(k)$. How does that let us make a PRF-distinguisher $B(f)$ making some $q$ calls to $f$ for which $\operatorname{Adv}^{\operatorname{PRF}}_H(B) = \Pr[B(H_k) = 1] - \Pr[B(F) = 1]$ is nontrivial, where $F$ is a uniform random function? Our desired $B$ can't just pass the unknown key $k$ to $A$. $\endgroup$
    – Squeamish Ossifrage
    Commented Dec 21, 2017 at 18:12
  • $\begingroup$ @SqueamishOssifrage: good question; by "collision-resistant", do you mean against adversaries that don't know the key, or ones that do? My comment assumed that the oracle didn't need to know the key; I would agree that the lack of resistance against adversaries that do know the key isn't a necessary property. $\endgroup$
    – poncho
    Commented Dec 21, 2017 at 18:48
1
$\begingroup$

Avoiding the question really, but collision resistance isn't really a considered property of Pseudo-random functions.

Looking at the definition of a PRF:

F :: {0,1}k x {0,1}n --> {0,1}m

F ( key, x ) = y

the main consideration is how well it emulates the random function [f(x) = y] when given a random key.

Improve this answer
$\endgroup$
1
1
$\begingroup$

Not any PRF is necessarily collision resist. If the PRF is a PRP, than for inputs of length of block-length, the PRP is necessarily collision resist because its on-to function, so it is impossible that two inputs are mapped to the same output. When the PRF is not PRP, depends on its output length, it can be collision resist.

Improve this answer
$\endgroup$
-2
$\begingroup$

A PRF is indistinguishable from a random oracle. A random oracle is collision resistant. Hence, a PRF is also collision resistant.

Update: This answer lacks some clarity. The comments showed that the definition of collision resistance in the context of a PRF is not necessarily clear. A PRF appears only random to an observer that doesn't know the key. However, collision resistance typically requires that collisions are also hard to find when the key is known.

Improve this answer
$\endgroup$
14
  • $\begingroup$ Why downvote? Please explain in comments... $\endgroup$
    – mti
    Commented Mar 25 at 8:43
  • $\begingroup$ Did you see the Dec 21, 2017 comment made by Squeamish Ossifrage under your question? $\endgroup$
    – DannyNiu
    Commented Mar 25 at 11:36
  • 1
    $\begingroup$ @samuel-lucas6, the CBC-MAC example is a great example for the lack of collision resistance if we interpret collisions in the technical sense of collision of a keyed hash family, in which case the key is indeed given to the adversary. So I think it comes down to the OP being precise about what collision notion we are evaluating and on what primitive. I agree with your comment otherwise. $\endgroup$
    – Marc Ilunga
    Commented Mar 25 at 22:10
  • 1
    $\begingroup$ @MarcIlunga However, my vote in itself is based on my judgement that OP's reasoning is flawed. $\endgroup$
    – DannyNiu
    Commented Mar 26 at 1:59
  • 1
    $\begingroup$ @samuel-lucas6 thank you for bringing that up. Indeed it shows that my question lacked some preciseness. I did not consider whether the key would be known, but that certainly plays a role here. I’ve unaccepted my answer. I’m considering to add some more clarity and will look into your answer in more detail later. $\endgroup$
    – mti
    Commented Mar 27 at 20:01

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.