# Is a PRF always collision resistant?

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?

• 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! – Squeamish Ossifrage Dec 21 '17 at 18:32

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.

• 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? – mti Dec 21 '17 at 16:43
• @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" – poncho Dec 21 '17 at 16:47
• @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. – mti Dec 21 '17 at 17:23
• 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$. – Squeamish Ossifrage Dec 21 '17 at 18:12
• @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. – poncho Dec 21 '17 at 18:48

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.

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.