Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 7 down vote accepted

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

share|improve this answer
    
So generally, the NIST wasn't quite sure, but they felt like doing some random stuff would make it more.. random? ;) –  cooky451 Jul 6 '13 at 22:53
    
@cooky451 "Convincingly robust" does not sound like "random" to me. –  owlstead Jul 6 '13 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 '13 at 23:15
add comment

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

share|improve this answer
    
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. –  cooky451 Jul 6 '13 at 21:22
    
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. –  Michael Jul 6 '13 at 21:40
    
Yeah but that makes like 2 additional lines, still nowhere near the NIST algorithm –  cooky451 Jul 6 '13 at 21:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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