14
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – A. Hersean May 21 at 15:09
  • 1
    $\begingroup$ 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. $\endgroup$ – vol7ron May 21 at 22:00
  • 1
    $\begingroup$ 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! $\endgroup$ – user7761803 May 22 at 7:38
  • 1
    $\begingroup$ 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. $\endgroup$ – Konrad Rudolph May 22 at 8:53
  • 1
    $\begingroup$ 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. $\endgroup$ – Elaskanator May 22 at 19:09
33
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bristol May 22 at 19:28
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage May 21 at 15:47
0
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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