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?
  • 1
    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 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 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 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 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 at 4:58
up vote 14 down vote accepted

The answer is most certainly not! Well, I sort of lied, since it depends on what you are doing. I'll explain.

The basic property of hash functions is collision resistance, and this requires nothing beyond that. The output doesn't have to look random in any form, and this suffices for anywhere that you need collision resistance.

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.)

  • 1
    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 at 13:33
  • 1
    @Daniel You can even give an example in the other direction. I.e., a function can look random for some reasonable interpretation of "looking random" but have trivial collisions. E.g., if the function would happen to be a PRG for inputs somewhat shorter than the output size. Those certainly "look random", but their security says nothing about collisions. – Maeher Nov 8 at 14:57
  • 1
    An interesting class of hashes to consider in this discussion are similarity preserving hashes. These are very intentionally and specifically non-random, and are very useful in a number of scenarios. A survey of the motivations and methods is given here: arxiv.org/pdf/1408.2927.pdf – Ken Goss Nov 8 at 15:16
  • 1
    @UKMonkey this is not a good example since it doesn’t compress the output. Collision resistance without compression is trivial and uninteresting. – Yehuda Lindell Nov 8 at 15:33
  • 1
    @UKMonkey an arbitrary size means that it has to work for arbitrary size inputs, so also large inputs. – Yehuda Lindell Nov 8 at 15:42

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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