# Using a Hash as a secure PRNG

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

-

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

-
So generally, the NIST wasn't quite sure, but they felt like doing some random stuff would make it more.. random? ;) –  cooky451 Jul 6 at 22:53
@cooky451 "Convincingly robust" does not sound like "random" to me. –  owlstead Jul 6 at 23:13
It will only be devilishly fast if your API/runtime provided access to the AES-NI instruction set of course :). –  owlstead Jul 6 at 23:15

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.