I'm trying to find an efficient deterministic PRF construction that can quickly output a large amount of pseudo-random data from a seed of collected entropy. I ran tests with a contruction based on hash functions, similar to NIST's HASH_DRBG, but it was a bit inefficient due to the many calls to the underlying hash function for larger output sizes. I found that on my computer it was much faster to use a stream cipher to produce the data, given an efficient construction.

The stream-cipher based constructions I've found are NIST's CTR_DRBG which is a complex construction and Daniel J. Bernstein's response to it which is very simple in comparison. There must be some reason behind why the NIST construction is so complex so I'm wondering about the security tradeoffs in case the extra complexity is not always needed. Bernstein's blog article is focused around explaining the key erasure aspect so I'm guessing the rest of the construction might've been simplified in order to make the explanation clearer. But maybe there is not any obvious loss of security?

My question is whether the much simpler construction from Bernstein has any obvious security tradeoffs compared to the complex one from NIST. Maybe there are other trusted constructions that are also more simple than what NIST proposes.

I'm including my benchmark code I mentioned which was based on my understanding of Bernstein's construction, since there is no super clear description of it on the blog:

function initialise_prng(seed) {
    key = h(seed)

function get_random_bytes(output_size) {
    output = E(key, zeroes(iv_size), zeroes(output_size+key_size))
    key = output[0] || output[1] || ... || output[key_size-1]
    return output[key_size] || output[key_size+1] || ... || output[key_size+output_size-1]

where E is the block-cipher (e.g. AES) in CTR mode, h is a hash function (e.g. SHA-256), and zeroes(x) is a byte array of all zeroes with length x.

  • 1
    $\begingroup$ It matters if seed is high-entropy (e.g. true random as wide as key is, that is I guess 256-bit) or low-entropy (e.g. a password), and that's unclear. In the former case, the h step is pointless (update: only sometime, as rightly pointed in a follow-up comment) but mostly harmless. In the later case, SHA-256 is a poor choice for the h step. $\endgroup$
    – fgrieu
    Commented May 31 at 10:07
  • $\begingroup$ Small note: if your stream cipher already outputs the key stream then there is no need for an "encryption" function. XOR with zero won't take that much time, but it is obviously unnecessary as XOR with zero is the identity function. $\endgroup$
    – Maarten Bodewes
    Commented May 31 at 10:14
  • 1
    $\begingroup$ @fgrieu I think I would want the h step regardless since true random numbers are always guaranteed to be random but not always to be uniformly distributed. The h step gives a decent guarantee that the output is uniformly distributed and also allows you to use entropy sources that give larger outputs than is usable as a key. $\endgroup$
    – n-l-i
    Commented May 31 at 10:25
  • $\begingroup$ @MaartenBodewes That's a good note. I wonder if it's common for high level libraries to let you access the key stream directly. The one I'm using doesn't seem to enable that, but good to keep in mind in case the library includes that in their api. $\endgroup$
    – n-l-i
    Commented May 31 at 11:40
  • 1
    $\begingroup$ One answer went into the possibility of NIST from deliberately altering their DRBG algorithms to weaken them. It seems unlikely that this is the case but NIST of course does have a weak track record considering the Dual EC DRBG. Any answers should however focus on this difference between these complex constructions and the simpler algorithm with objectively verifiable differences, hard as that may be. I'm mainly pointing this out for 2 reasons: 1. the point has been made and is not without merit and 2. to indicate that such answers are not considered on topic for this question regardless. $\endgroup$
    – Maarten Bodewes
    Commented Jun 4 at 21:22


Your Answer

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