Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Out of the two deterministic random bit generators defined in section 10.1 of NIST SP 800-90A (i.e. based on hash functions), which one is cryptographically stronger?
Is there any other criteria to select between these two?
Short answer: Hash-DRBG is faster. According to page 42 in these NIST slides, HMAC-DRBG is stronger not weaker. BUT update¹: Doanne Woodage and Dan Shumow's An Analysis of NIST SP 800-90A, in Proceedings of Eurocrypt 2019, shows that HMAC-DRBG's backtracking resistance requires the "additional input" parameter described as optional in the standard, when it described backtracking resistance as a security feature for all the generators.
That caveat is not in this positive Security Analysis of DRBG Using HMAC in NIST SP 800-90, nor in this security proof from 2017 (nor, for now, in the following).
[The rest of this posit is outdated and needs rework]
Hash-DRBG seems secure if the hash function $H$ that it uses is indistinguishable from a random function. That's even trivial for the first sequence generated, which is $H(V), H(V+1), H(V+2), \dots$ where $V$ is derived from seed material.
However, Hash-DRBG exposes several values derived from the secret seed $V$ in a known, simple, almost linear way, after going through one layer of $H$. By contrast, the output of HMAC-DRBG is an HMAC result, which derivation from the secret $K$ goes through two layers of $H$. That's fair reason to believe HMAC-DRBG has more resilience against state recovery than Hash-DRBG, assuming a weakness in $H$.
On the same line of thought, the security of HMAC-DRBG derives from that of HMAC, this construct has a security proof holding for weak assumptions on $H$, and an history of remaining strong even when the underlying hash function succumbs: HMAC-MD5 stands unbroken AFAIK, although MD5 collisions can be obtained including in real time, and there is a theoretical pre-image attack; HMAC-MD4 is broken, but the best claimed attack still costs 2^77 hashes.
¹ Kudos for the formerly active and still highly appreciated contributor who brought this to my attention by a side channel; no, not that one.
To complement fgrieu's short answer, here is an overview of the two RNG algorithm sets.
The state of Hash-DRBG is composed of a value $V$ (which is updated with each request of new bits), and a same-size constant $C$ (which is only updated on reseeding the generator), and a counter $c$ to track when the next reseeding is needed.
Only $V$ is directly used to generate new bits, by concatenating $H(V), H(V+1), H(V+2), \dots$ until enough bits are generated.
After each generation of new bits, both the constant, the counter and a hashed version of the value are added to the value to generate the new value:
$$V_{\text{new}} = V + H(\text{0x03}||V) + C + c $$
Then $c$ is increased by one.
You can also provide additional input to the generator, in which case another hash call with $V_{\text{new}} = H(\text{0x02}||V||A)$ is done before generating the output.
For initial seeding and reseeding, an adaptable-output-size version $\tilde H$ of $H$ is used (as defined in Section 10.4.1), to generate enough bits for $V$ and $C$.
Hash-DRBG relies on $V$ and $C$ staying secret. For $V$, this is the preimage-resistance of the hash function (as $V$ is hashed to generate the output), while $C$ can be easily derived from two (or three, if the counter value is not known) consecutive values of $V$ (as it is simply added).
From this, the following output can be predicted, until the application adds non-predictable additional data or the state is reseeded.
(Of course, we also need that the output of $H$ is pseudo-random, i.e. has no detectable patterns.)
Initialization: The value $V$ is created by hashing the "seed material", and the constant $C$ then by hashing $V$ (with a prefix byte of $0$) (both producing 440 bits).
In HMAC-DRBG, the state is composed of a key $K$, a value $V$ and a counter c (to keep track of when a reseed is needed - it is not used for generation itself).
The actual generation of random bits uses
$$ V := HMAC(K, V)$$
in a loop and concatenates these new values of $V$ until enough output is generated.
After this, an update function is called, which changes both key and value by two HMAC calculations:
$$\begin{align*} K_{\text{new}} &= HMAC(K_{\text{old}}, V_{\text{old}} || \text{0x00}) \\ V_{\text{new}} &= HMAC(K_{\text{new}}, V_{\text{old}}) \end{align*} $$
Update can alternatively also incorporate additional data $A$ provided by the application, using four such calls in total:
$$ \begin{align*} K_{\text{tmp}} &= HMAC(K_{\text{old}}, V_{\text{old}} || \text{0x00} || A) \\ V_{\text{tmp}} &= HMAC(K_{\text{tmp}}, V_{\text{old}}) \\ K_{\text{new}} &= HMAC(K_{\text{tmp}}, V_{\text{tmp}} || \text{0x01} || A) \\ V_{\text{new}} &= HMAC(K_{\text{new}}, V_{\text{tmp}}) \end{align*} $$
(If additional input is given to the generate-function, update will be called before and after generating more output.) This will also be used for seeding and reseeding, where the additional data contains entropy input (and maybe any application-specific stuff).
HMAC-DRBG's security depends on the key $K$ staying secret (intermediate values of $V$ are output directly as pseudorandom bits), i.e. on the key-retrieval-resistance of the HMAC.
If value of $K$ is known, all the following ones can be derived, until the application adds non-predictable additional data or a reseeding occurs.
But other than this worst-case break, there might be other weaknesses in the hash function's output which make HMAC's output be non-random (i.e. show patterns). Optimally, we want the HMAC output be a pseudorandom function of the input.
Initialization: The HMAC_DRBG_Instantiate_algorithm function sets $K$ to 0 and $V$ to $\texttt{0x01010101}\dots\texttt{01}$, before calling first the Update function with the seed material as "additional data".
One can see that HMAC-DRBG shuffles stuff around a bit more than Hash-DRBG ... and HMAC itself even contains two hash invocations. Thus HMAC-DRBG is certainly slower.
But as any possible weaknesses of HMAC will come from weaknesses of the underlying hash function, HMAC can't be weaker than the hash ... but it could be stronger (i.e. some weaknesses of a hash function will not transfer to the corresponding HMAC). For now, there is no weakness known in either of both constructions, though.
