12
$\begingroup$

I was just looking at some NIST PRNG recommendations, specifically at Hash_DRBG. I read briefly through the algorithm, and even though it is not overly complex, it still seems unnecessary to me. I asked myself how I would implement a (cryptographically secure) PRNG on top of a Hash algorithm (SHA256 or SHA512), what came up is:

Idea one:

Obviously this can only provide half the "strength" of the hash

Initialization: state = hash(seed);
Iteration: output = first_half_of(state); state = hash(state);
Reseeding: state = hash(state || new_seed)

Idea Two:

Maybe with a separate counter

Initialization: state = hash(seed);
Iteration: output = hash(state); ++state;
Reseeding: state = hash(state || new_seed)

Now, these two "schemes" seem safe to me, I'm a complete crypto noob though. The point is that I don't think that I'm the first one to think of these very basic PRNGs, and I'd like to understand the reason for NIST not to choose something similar in their recommendations. Do these PRNGs have some (obvious?) weaknesses? (If not, is there something known about after how many iterations they should be reseeded?)

$\endgroup$

2 Answers 2

10
$\begingroup$

Both ideas are safe if the hash function behaves like a random oracle and has a large enough output (in particular for "idea 1": with a function which outputs n bits at a time, it is expected that the state will enter a cycle of length about 2n/2, after about 2n/2 steps, so if you want "128-bit security", you will need n = 256 or more).

However, we do not have random oracles, but concrete hash functions, which are not as good and have subtle "flaws" which can compromise simple PRNG designs without contradicting the core security properties of the hash function. See this answer for some details. Proposals like yours are not necessarily weak when used with existing hash functions like SHA-256, but it is hard to make sure of it.

The NIST constructions are a bit more complex because they try to be more robust, or at least more convincingly robust. For these reasons, HMAC_DRBG is preferred.


If you want a lot of pseudorandomness with a very high bandwidth, you should look at specialized stream ciphers like these ones (a stream cipher can be turned into a PRNG by making it encrypt a long sequence of zeros). Alternatively, use AES in CTR mode, which will be devilishly fast on recent x86 processors (the ones which have an hardware AES implementation).

$\endgroup$
4
  • $\begingroup$ So generally, the NIST wasn't quite sure, but they felt like doing some random stuff would make it more.. random? ;) $\endgroup$
    – cooky451
    Jul 6, 2013 at 22:53
  • $\begingroup$ @cooky451 "Convincingly robust" does not sound like "random" to me. $\endgroup$
    – Maarten Bodewes
    Jul 6, 2013 at 23:13
  • 1
    $\begingroup$ It will only be devilishly fast if your API/runtime provided access to the AES-NI instruction set of course :). $\endgroup$
    – Maarten Bodewes
    Jul 6, 2013 at 23:15
  • $\begingroup$ The problem with using ciphers as PRNG's seems to be that if someone finds out the key used, they can reconstruct the sequence from the beginning. With hash values, it's a better, since you only store the prior output in ram... not the initial key. Sure compromised RAM will break forward security of the hash method... but compromised RAM will break backward security too with a cipher technique. $\endgroup$ Jul 6, 2018 at 17:13
7
$\begingroup$

Not a complete answer, but some observations on your proposed schemes:

Idea two (counter) is susceptible to state compromise extension: if state gets revealed, all past outputs can be predicted. This is something good PRNGs resist.

Neither scheme allows for addition of entropy. A naive reseed (i.e. repeating the initialisation) throws away any entropy currently in the system.

Both schemes have fixed length output dependent on the underlying hash function (i.e. you can't request n bits of output).

$\endgroup$
3
  • 1
    $\begingroup$ As for the flaw in idea 2: That is correct, thanks for pointing that out. As for addition of entropy, what about hash(state || new_seed)? The fixed-length output can also easily be fixed, that's not really a concern I'm afraid. $\endgroup$
    – cooky451
    Jul 6, 2013 at 21:22
  • $\begingroup$ Reseeding and support for arbitrary output lengths are some of the reasons why the specification for Hash_DRBG is longer than your specification, which is why I pointed them out. $\endgroup$
    – Michael
    Jul 6, 2013 at 21:40
  • $\begingroup$ Yeah but that makes like 2 additional lines, still nowhere near the NIST algorithm $\endgroup$
    – cooky451
    Jul 6, 2013 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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