# Cryptographically strong seeded pseudo random number generator

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.

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

• What are "independent hash functions"? – fkraiem Sep 8 '17 at 3:48
• A loose but useful use of terminology, just like ‘preimage-resistant’. One read: independent random oracles. Another read: Pick a bit string function $F$ uniformly at random. For two inputs $a \ne b$, the bit strings $F(a)$ and $F(b)$ are independent uniform random variables. Now pick a key $k$ uniformly at random, and a PRF $F_k$. To call $F_k(a)$ and $F_k(b)$ independent uniform random variables is an abuse of language, but to an adversary who does not know $k$, they have no hope of distinguishing $F_k(a)$ from $F_k(b)$ from an independent uniform random bit strings. – Squeamish Ossifrage Sep 8 '17 at 14:02
• This is the same idea as the ‘customization strings’ or ‘personalization strings’ seen in many collision-resistant hash functions of the past decade, such as BLAKE2 and SHA-3. In fact, the NIST standard even describes different customization strings as inducing ‘independent hash functions’ in those terms, in ‘SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash, and ParallelHash’, NIST SP800-185, p. 20. – Squeamish Ossifrage Sep 8 '17 at 14:06

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]$.

• Thanks - is this fixed by making the "vertical" and "horizontal" hash functions different? – fadedbee Sep 7 '17 at 8:30
• Simply "different" is not enough. The design in the question is fine - but hash functionsa might be too general. – tylo Sep 7 '17 at 9:15
• The problem with "different" is that it includes "almost equal"... (For example the second hash function could be the first with one bit flipped.) – fkraiem Sep 7 '17 at 12:13