Impact of the hash algorithm on a PRNG

Question

Pseudorandom number generators often use hash functions for the generation. Some applications allow the users to choose this hash function, for example OpenVPN.

From the OpenVPN manual:

--prng alg [nsl] (Advanced) For PRNG (Pseudo-random number generator), use digest algorithm alg (default=sha1), and set nsl (default=16) to the size in bytes of the nonce secret length (between 16 and 64).

Set alg=none to disable the PRNG and use the OpenSSL RAND_bytes function instead for all of OpenVPN's pseudo-random number needs.

What impact does the hash function have on the randomness of the resulting pseudorandom number?

For example, SHA1 suffers from proven hash collisions. Does that impact the pseudorandom number?

Would SHA2 be considered more secure or is the impact of the hash function not that crucial on the randomness?

Answer 1

What impact does the hash function have on the randomness of the resulting pseudorandom number?

None. A good cryptographic hash function like the ones you mention will produce output that is uniformly distributed random. Given a long stream of output, you will not be able to identify what hash function was used. The actual stream of numbers will however totally change if you change the hash, but they'll all be just as random. It should still be impossible to distinguish a good PRNG's output from true randomness, no matter how much effort you use.

For example, SHA1 suffers from proven hash collisions. Does that impact the pseudorandom number?

That's a highly contrived example in a very particular situation. We're not at the stage yet where we can immediately invert a SHA-1 output to determine the input. And actually, collisions in a PRNG output are nothing to be feared. You would expect these to occur naturally (but infrequently) as you produce the output. Random numbers repeat sometimes. What's important is that again given a long sequence of output, we can't at the moment discover the input sequence and therefore the generator's internal state.

Would SHA2 be considered more secure or is the impact of the hash function not that crucial on the randomness?

At this stage, it doesn't make a difference. /dev/random and Java's SecureRandom still use SHA-1 mixing functions and they're considered unbroken. If you specifically focus on the randomness, that's not a direct product of cryptographic security and invert ability. It's a function of the avalanche effect. Any hash function that exhibits the avalanche effect will generate perfect random output. For example a simple algorithm based on a substitution permutation network or matrix multiplication will produce perfectly random output. You'll just be able to invert it and therefore those wouldn't be suitable as cryptographic PRNGs.

Answer 2

As far as we know, there is no real danger in using for a RNG a hash algorithm which collision resistance, and only that, is broken, including SHA-1.

In RNGs

• The main property thought from a hash is that it's output is computationally indistinguishable from random when its input is chosen randomly in a set too large to explore (and that is not defined in term of the hash). SHA-1 is untainted in this regard.
• Preimage-resistance matters, but is not sufficient (for example, if we modify SHA-256 by replacing the first byte by '01' when it is '00', we still have a preimage-resistant hash, but it can be terrible in a RNG).
• Collision resistance is essentially immaterial (because the adversary does not control the whole input).