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

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?

• Why cannot you use a stream cipher? That would be more efficient: stream ciphers are faster than hash functions. They also produce an output indistinguishable from truly random data. May 21, 2019 at 15:09
• If you have a billion possibilities and are generating a million values, if those values are in the first million slots, is that uniformly distributed? Even if the likelihood of collision for the next generated value is not likely to use one of the previously used values, I’d argue that it is low risk of collision, but not uniform in disparity. May 21, 2019 at 22:00
• Not an answer (@Squeamish Ossifrage has already answered your headline question), but to address your first paragraph: yes, concrete cryptographic hash functions can be and are used to generate streams of random data (which can be for cryptographic purposes when seeded appropriately, so should meet your "seemingly random" requirement). See, for example, Hash_DRBG in the NIST recommendations. But look for a good implementation - don't go re-inventing the wheel! May 22, 2019 at 7:38
• This seems like an X–Y problem: If you need to produce uniformly distributed random numbers, don’t use a hash function, use a (CS)PRNG, possibly in conjunction with a uniform distribution derivation function. May 22, 2019 at 8:53
• If you don't care about the cryptographic properties, then maybe take a look at the Halton sequence. This is useful for numeric sampling algorithms (not super highly-dimensional ones tho!) as a pseudo-random number sequence that very uniformly covers the sampling space. May 22, 2019 at 19:09

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$$

• Indeed. The property people often want when they reach for a cryptographic hash function is indifferentiability from a random oracle, which covers a lot of bases.
– user2552
May 22, 2019 at 19:28

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

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

• How do you draw these implications? The most prevalent ciphers today—AES-GCM and ChaCha/Poly1305—use a ‘hash function’ of a counter, inspired in part because the United States export controls on cryptography as a munition did not cover the hash function Snefru. But neither AES nor ChaCha provide collision resistance. Conversely, Rumba20 and VSH, designed for collision resistance, do not provide preimage resistance or uniformity. GHASH has uniformity and low collision probability, but no collision resistance. ‘Hash function’ means many things; the question was about specific properties. May 21, 2019 at 15:47

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