3
$\begingroup$

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?

|improve this question
$\endgroup$
4
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for the elaboration. So if I use, for example OpenSSL RAND_bytes, the hashing function does not impact the randomness, right? Even if I were to a deprecated hashing function such as MD5, or even MD4? $\endgroup$ – SaAtomic Jul 21 '17 at 10:59
  • 1
    $\begingroup$ @SaAtomic For the security of the CSPRNG you need preimage resistance of the hash function, just collision resistance doesn't matter. That is no issue for SHA-1, and for MD-5 that's ... arguably feasable. For MD4, preimage resistance can be broken with $2^{102}$ - that is a lot closer to what is possible today, and would be considered insecure. But MD4 is declared obsolete anyway, and when designing a new system no one should use MD5 or SHA-1. When designing a new car, you're not going to use the oldest engine, either. $\endgroup$ – tylo Jul 21 '17 at 11:22
  • 2
    $\begingroup$ @SaAtomic In addition to tylo's numeric analysis, you'd be tainted by association. MD4 /5 isn't considered appropriate any more, and your usage of it would be viewed with derision /suspicion. You'd have a hard time convincing users to trust your scheme, and in cryptography trust is a major factor in adoption. $\endgroup$ – Paul Uszak Jul 21 '17 at 11:58
1
$\begingroup$

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).
|improve this answer
$\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.