# Do hash functions need to “look random”?

I've noticed that looking random is not often listed as a requirement for a good hash function in the same way that preimage or collision resistance is.

• Do we need hash functions to look random?

Specifically, suppose $$s$$ is a seed, and consider the PRNG that outputs $$H(s \|0) \| H(s \|1 ) \| H(s \|2) \| ...$$

• Do we need this to be indistinguishable from random?
• Will any protocols be weakened if it wasn't?
• looking random? What is the definition? We can apply some statistical test to determine the randomness. If they fail to pass some margins, this will indicate that there is some weakness in the construction to behave like randomly. – kelalaka Nov 8 '18 at 9:03
• Note that for hash functions to have $n$ bits of security or $n/2$ bits of security for collision resistance you would expect a relatively well distributed output: if some values are more likely then the security of the function would also be affected. A hash with an output of 256 bits would not deliver 256 / 128 bits of security, in other words. – Maarten Bodewes Nov 8 '18 at 15:13
• "Being random" is an opposite to "having patterns". And "having patterns" is close to "insecure". So if you are talking about cryptografically secure hash function then I would say "yes". – freakish Nov 8 '18 at 20:53
• I found that Matthew Green's blog post about indifferentiability and his series about the Random Oracle Model are wonky-but-not-too-hard readings to get a beginner's sense of hash functions vs. randomness. Lots of linked references to follow up, too. – Luis Casillas Nov 9 '18 at 0:25
• @kelalaka By "looking random" I mean : For every efficient adversary that takes in a bitstring and outputs 0 or 1, give the adversary either H(s ||0) || H(s || 1) || H(s || 2) || ...., or a random string . The difference in the probability that the adversary outputs 1 is negligible. – David Lui Nov 9 '18 at 4:58

However, in many cases, because most hash functions in practice do look sort of random (completely undefined), they are used for other things. For example, HMAC assumes that the compression function (with one part of the input being the key) is essentially a pseudorandom function. More extreme, but very common examples, are the modeling of the hash function as a "random oracle". This is used for OEAP encryption padding, in most cases in practice for signatures, and more. You also somewhat assume this property for hashing passwords. (Note that for any hash function $$H$$, if you define $$H'(x) = x|_n\|H(x)$$ where $$x|_n$$ is the first $$n$$ bits of $$x$$, then $$H'$$ is collision resistant if $$H$$ is collision resistant. However $$H'$$ would be a very poor choice for password hashing.)
• It's also good to add that there is a strong separation between collision-resistance and "looking random", i.e. you can have collision-resistant hash functions whose output does not look random at all! e.g. $H'(x) = 0^\ell\|H(x)$ where $H$ is a collision-resistant hash function. (Realized you addressed this in the answer already) – Daniel Nov 8 '18 at 13:33