Cryptographically strong seeded pseudo random number generator

Question

Why is the following not cryptographically secure?

Seed the algorithm with 32 random bytes S[0].

S[0] --hash--> S[1] --hash--> S[2] --hash--> S[3] ...
 |              |              |              |
hash           hash           hash           hash
 |              |              |              |
 v              v              v              v
R[0]           R[1]           R[2]           R[3]

The hash function is cryptographically strong, i.e. it cannot be reversed.

The outputs (R) comes in 32 byte blocks, R[0] onwards.

Obviously this is far too simple to be secure, but I wondered why.

Answer 1

If you pick only one hash function so that $R_i = S_{i + 1}$, then you've just revealed the entire state to the attacker in a single output.

But if you pick two independent preimage-resistant hash functions $H_\mathrm R$ and $H_\mathrm S$ with $R_i = H_\mathrm R(S_i)$ and $S_i = H_\mathrm S(S_i)$, then this is essentially the structure of most cryptographic PRNGs.

For example, Dan Bernstein's fast key erasure PRNG with AES-256 has exactly this structure, with \begin{align*} H_\mathrm R(k) &= \operatorname{AES256}_k(2) \mathop\Vert \operatorname{AES256}_k(3) \mathop\Vert \cdots \mathop\Vert \operatorname{AES256}_k(47), \\ H_\mathrm S(k) &= \operatorname{AES256}_k(0) \mathop\Vert \operatorname{AES256}_k(1). \end{align*} You could substitute $\operatorname{ChaCha20}_k(i)$ for $\operatorname{AES256}_k(i)$ (with some tweaks to the indexing because ChaCha20 produces more output per call) to get higher performance and higher security, but government auditors sometimes like the letters AES better. You could also use $\operatorname{HMAC-SHA512}_k(i)$, but you definitely won't set any speed records that way because you're paying doubly for collision resistance and doubly again for HMAC.

The NIST SP800-90A constructions such as CTR_DRBG and Hash_DRBG, which are much more elaborate for essentially no reason, can also be shown to fit this structure; details left as an exercise for the reader.

One detail is worth noting, though: the Dual_EC_DRBG. With the bureaucratic drudgery of NIST DRBGs elided, it is structured as above, and the hash functions are \begin{align*} H_\mathrm R(k) &= x([H_\mathrm S(k)]Q), \\ H_\mathrm S(k) &= x([k]P), \end{align*} where $P$ and $Q$ are independently chosen base points in a standard elliptic curve and $[k]P$ is scalar multiplication of the point $P$ by the integer $k$. As far as you're concerned, these hash functions are independent, but if the NSA knows the scalar $d$ by which $P$ and $Q$ are related by $Q = [d]P$, then given $R_i$ they can trivially compute $$S_{i + 1} = x([S_i]P) = x([S_i][d]Q) = x([d][S_i]Q) = x([d] x^{-1}(R_i)),$$ where $x^{-1}(R_i)$ is one of the two possible points with the $x$ coordinate that is $R_i$.

Answer 2

In your scheme, $R[0] = S[1]$, because hashing $S[0]$ always gives the same result.

So knowing the output $R[0]$, the attacker can predict the entire stream - he knows the complete internal state at the position of $S[1]$.