Can we assume that a hash function with high collision resistance also means a highly uniform distribution?

Question

I want to use a hash function to generate a random sequence from number 0-n. And so I would like to find a good function that results in values that are seemingly random (does not need to be secure), but gives a sequence that is uniformly distributed.

Can I look at a function that has the property of high collision resistance and expect that it would also have a highly uniform distribution?

Answer 1

Define $H(x) = \operatorname{SHA-256}(x) \mathbin\| 1$; that is, append a single 1 bit to SHA-256. Can you find a collision under $H$? Does $H$ have anything resembling uniform distribution?

This counterexample is not merely pathological; designs like Rumba20 and VSH provide collision resistance but neither preimage resistance nor uniformity.

That said, typical ‘cryptographic hash functions’ like SHA-256, BLAKE2b, and SHAKE128 are designed for collision resistance and preimage resistance, and more broadly for random oracle modeling (barring length extension attacks on SHA-256), meaning that the outputs on distinct inputs can reasonably be modeled as independently uniformly distributed.

---

In the dark ages of the early '90s, when the United States still banned the export of cryptography as a munition, the ban covered encryption, per se, like DES—but had an explicit exception for authentication (22 CFR §121.1(XIII)(b)(1)(vi), since rescinded), and so the hash function Snefru was allowed to be published and exported.

A grad student named Dan pointed out in 1992 that you could use Snefru as a subroutine in an otherwise cryptography-free program to encrypt messages. When he informed the United States Department of State of his remarkable discovery, and asked them to confirm his understanding that publishing his cryptography-free program together with the exempted Snefru would not fall afoul of the export controls, they were not amused.

The State Department's lack of humor led to a nearly decade-long court battle, Bernstein v. United States, about whether the regulations in 22 CFR §§120–130 and 15 CFR §§730–744 prohibiting the export of encryption software constitute prior restraint in violation of the First Amendment to the United States Constitution. Eventually, the United States federal government, backed into a corner by an annoying grad student, relaxed the regulations and the case was dismissed.

Today, a newer incarnation of the same idea—using a hash function, ChaCha, together with a method inspired by the advanced technology of the one-time pad (also known in some circles as ‘xor’), to encrypt messages—protects the confidentiality of probably petabytes of data daily on the internet, in the form of the ChaCha/Poly1305 cipher suites in TLS.

But collision resistance is neither necessary—indeed, it is well-known that ChaCha is not collision-resistant—nor sufficient—as Rumba20 and VSH show—for indistinguishability from uniform random, which is what one needs for, e.g., a one-time pad to get any security.

_{P.S. If you do use a hash function, e.g. generating the sequence of bits $H(k \mathbin\| 0)$, $H(k \mathbin\| 1)$, etc., and want to use that sequence of bits to choose an integer $x$ with $0 \leq x < n$ uniformly at random, make sure to do rejection sampling to avoid modulo bias if $n$ is not a power of two: if $H$ returns a string of $t$ bits interpreted as a $t$-bit integer, and $H(k \mathbin\| i)$ is below $2^t \bmod n$, reject it and try $i + 1$; otherwise return $H(k \mathbin\| i) \bmod n$}

Answer 2

It does not follow from the definition of a cryptographic hash function that its output would be uniformly random. However, this is the case for the hash functions used in practice.

A common assumption when reasoning about hash functions is that they are indistinguishable from taking a random element of a pseudorandom function family (PRF). By definition of a PRF, it's practically impossible to distinguish between the following two behaviors if you don't know which PRF element was chosen:

1. Given an input, yield the output from the chosen function.
2. Given an input, if that particular output has already been passed, return the same input as last time. Otherwise generate a uniforly random output and remember it for future queries.

Since the second method gives uniformly random outputs, so does the first method.

The effective randomness of hash functions allows using them to build hash-based key derivation functions and random generators (Hash_DRBG). Because hash calculations are pretty cheap, and because some past hash functions have been proven to be weak (though not in ways that would invalidate the use as KDF/PRNG), there are common constructions that use HMAC, i.e. two nested hash invocations, as a building block rather than just one hash: HKDF and HMAC_DRBG. No weakness is known in the basic methods though (KDF1, Hash_DRBG).

Answer 3

No, but high collision resistance per bit has an influence. Non-uniformity -> less entropy -> weakned collision resistance.

As keysize is significant factor: most cryptographic hash functions have uniform output given entropic input. Using a hash (or encryption) routine to make a stream of random numbers from a single block of entropy is an established practice. There are lists of recommended primatives and pitfalls etc.

From wikipedia:

"A cryptographically secure hash of a counter might also act as a good CSPRNG in some cases. In this case, it is also necessary that the initial value of this counter is random and secret. However, there has been little study of these algorithms for use in this manner, and at least some authors warn against this use."

Answer 4

Only my 2 cents, you don't necessarily need an (heavy) hash function to generate a sequence or a series of pseudo-random numbers.

A practical, low-level way, to generate an uniform distribution of values, in a specific range, could be to use a simple acceptance/rejection method, combined with pseudo-random generation of numbers:

• if we want $k$ different output values, then our range will be $[0, k-1] $

• use a dumb 0/1- generator, like Math.random for js, a refined quantum random input source, or simply flip a coin $r$ times, for generating a pseudo-random sequence of $r$ bits, where:

  • $r = roundup( \log_{2}(k) )$

• the resulting value $n$ is in the interval $ [0, 2^{r}-1]$

• if $( n < k )$, pick and output the number (no modulo operation)

• otherwise, discard the number and regenerate a new pseudo-random sequence/number.

Obviously, we will consume more random input data from our source, when $k<<2^{r}$, because we expect much more rejections, but using the modulo is not a good solution in this case, it will not give us a uniform distribution.

---

The best scenario occurs when $k$ is a power of $2$:

• $k = 2^{i}$, for a generic natural $i$
• we consume precisely $1$-bit of input data to produce $1$-bit of output
• no waste of time

---

The worst scenario for rejections occurs when:

• $k = (2^{r-1}+1)$
• $(k - 1)= 2^{r-1}$
• $r = 1 + \log_{2}(k - 1)$
• we'll consume ~ $2$-bit of input data to produce $1$-bit of output
• we'll spend much more time in the generation process

---

For example, if we need, for a chosen interval $[0, k-1]$:

• $r = 10$ bits to generate at least $k$ different values, then:
• when $k = ( 2^{10-1} + 1 ) = 513$
  • we expect to sacrifice, on average, about ~$50\%$ of our pseudo-random input data, discarding all output numbers $> 513$, when they occur.
  • a total of $(2^{10} - 513 ) = 511$ values