What's the name of the property of ideal cryptographic hash functions that effectively make it a random number generator?

Question

Wikipedia says that, for an ideal cryptographic hash function, "the probability of a particular n-bit output result [...] for a random input string [...] is $2^{-n}$ (as for any good hash), so the hash value can be used as a representative of the message".

I'm looking for the name of this property. People often mention it without a name.

I looked at Douglas Stinson's "Cryptography: Theory and Practice", 4th edition (with Maura B. Paterson) and they don't seem to define this one. They defined pre-image resistance, second pre-image resistance and collision resistance. Why didn't they define this one about the probability of a bit in the output? If you can answer that, too, that'd be great.

Last question. It's not clear to me what is technically a cryptographic hash function. Should it have all of these properties? Do we still consider it to be cryptographic if it has some weak sides such as --- someone found a second pre-image once but nobody knows how to do it again?

Answer 1

I believe you are looking for the concept of 'indistinguishability'. Boneh and Shoup mention it when they discuss the 'Message Integrity' construction in their book A Graduate Course in Applied Cryptography, pg 321 (version 0.5),

Now suppose we use a hash function $H : S \to T$ to derive the key t from s. Intuitively, we want t to “look random”. To formalize this intuitive notion, we use the concept of computational indistinguishability from Section 3.11

Perhaps Dods, Smart, and Stam refer to it as 'undetectability' in the paper Hash based digital signature schemes. In Cryptography and Coding, pages 96–115, 2005; as that is what we can hear from this talk Andreas Hülsing - Hash-Based Signatures, in the moment 7:50.

So, framing your question would be: given that a hash doesn't maintain a $2^{-n}$ probability, an adversary might 'detect' specific outputs

Answer 2

I second the other answer: "indistinguishability" (from a "random oracle" or a "random function") is the name of the property thought.

Addressing the last question: indistinguishability is typically the property assumed for an ideal hash in a modern theoretical context. THat's because indistinguishability of a wide-enough hash implies it (first) pre-image resistance, second pre-image resistance and collision resistance.

More precisely: asymptotically and ignoring constant factors, with effort $2^b$, assuming indistinguishability, an at-least $b$-bit hash has both kinds of pre-image resistance, and an at-least $2b$-bit hash has collision resistance.

Answer 3

Why didn't they define this one about the probability of a bit in the output?

They kinda did. Statistically the fundamental requirement for a hash function based (or any other) random number generator is the next bit test. I.e. $Pr(x=0,x=1) = \frac{1}{2} \pm \epsilon$ where $\epsilon$ is a bias away from evens. NIST recommends that $\epsilon < 2^{-64}$ and cryptographically that bit $x_{n + 1}$ cannot be predicted otherwise with reasonable compute power even after having observed all of the previous output.

Answer 4

Adding to the other answers, the questions leave a few things open to interpretation. Therefore, there are many ways to answer the question. The main thing that isn't clearly stated in the question is whether we think of a keyed hash function. Also, the quote in the question only considers random inputs (assumedly of a given length?). This isn't a common restriction for hash functions, and it's unclear who chooses the input. But we can consider different options.

The common understanding of the property you look after is that the hash function behaves like a random oracle (a random function. But formally characterizing this appears to be tricky. In particular, indistinguishability from a random oracle is not a sound characterization if the hash function is unkeyed. I'll come back to this later.

The hash function is keyed

In this scenario, the property is akin to the undetectability notion mentioned in this answer, which resembles a pseudo-random generator notion but for keyed primitives. Alternatively, since the function is keyed, we may also discuss indistinguishability from a random function. The keyed hash has PRF-like properties even if the inputs aren't random.

The hash function is unkeyed

All the notions mentioned make sense only when the key is hidden from the adversary or when the adversary doesn't choose the inputs and only sees the outputs and must distinguish them from a truly random value. For unkeyed hash functions, if the adversary doesn't select the input, but the challenger chooses random inputs, we are again in a PRG-like scenario, but for shrinking outputs (PRG are deterministic systems).

Indistinguishability from a random function: Sadly, a single (unkeyed) hash function cannot be indistinguishable from a random oracle. The reason is that there are schemes that are secure in the random oracle model but that are always insecure when using a specific hash function. One such example is Canetti, Goldreich and Halevi's "pathological" signature scheme. This means that these schemes essentially become distinguishers.

Indifferentiability: Indistinguishability is not a formalism that is sound for a given, fixed hash function. Indifferentiability has been used to characterize what it is to behave like a random oracle. Today, it is also central for designing and analyzing hash functions (Coron et al.). At a high level, it says that assuming an idealization of the compression function or the permutation, an indifferentiable hash function behaves like a random oracle and can be used in most scenarios where a random oracle is expected without breaking the security. A downside to this is that we need to idealize a building block.