4
$\begingroup$

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.

$\endgroup$

2 Answers 2

4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ What are "independent hash functions"? $\endgroup$
    – fkraiem
    Sep 8, 2017 at 3:48
  • $\begingroup$ 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. $\endgroup$ Sep 8, 2017 at 14:02
  • $\begingroup$ 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. $\endgroup$ Sep 8, 2017 at 14:06
4
$\begingroup$

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

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

Your Answer

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

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