Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

  1. Hash-DRBG (Section 10.1.1)
  2. HMAC-DRBG (Section 10.1.2)

Is there any other criteria to select between these two?

share|improve this question

2 Answers 2

up vote 7 down vote accepted

The short answer seems to be: HMAC-DRBG is stronger. Hash-DRBG is faster.

That's according to page 42 in these NIST slides. And we have this positive Security Analysis of DRBG Using HMAC in NIST SP 800-90.

Edit: a more detailed hand-waving justification follows.

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.

share|improve this answer
6  
To be precise: HMAC-DRBG is not weaker than Hash-DRBG. We have no indication that Hash-DRBG is weak in any way, and you cannot be strictly stronger than that. Yet we have good reasons to believe that HMAC-DRBG cannot be weaker than Hash-DRBG (an attack against HMAC-DRBG would probably work just as well against Hash-DRBG). –  Thomas Pornin Dec 2 '11 at 12:49

To complement fgrieu's short answer, here is an overview of the two RNG algorithm sets.

Hash-DRBG

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

HMAC-DRBG

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 $0x01010101\dots01$, before calling first the Update function with the seed material as "additional data".

Summary

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.

share|improve this answer
    
Is there any information on the initial value of $V$? –  Chris Smith Jun 10 '12 at 17:53
    
@ChrisSmith: My answer was not meant as an alternative specification and implementation guide, just an overview from the cryptography point of view. For this, the initial value doesn't matter at all. But I looked again in the standard and added the relevant information from the appendix D. –  Paŭlo Ebermann Jun 10 '12 at 19:52
    
Thank you @Paulo Ebermann, I missed the appendices. –  Chris Smith Jun 10 '12 at 20:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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