Weakness in the NIST Random Number Generator CTR_DRBG

Written by Jonathan Landis of Caliber Security Partners

NIST SP.800-90Ar1 specifies several mechanisms for generating random numbers. The mechanisms vary, but each mechanism must accept a variable number of bits from an entropy source and convert it into a fixed number of bits for the internal state of the generator. In other words, in one form or another the generator must employ a hash function. The flaw presented here is the lack of collision resistance in the hash function used in CTR_DRBG.

In the case of CTR_DRBG, it is an implementation decision whether to use a "derivation function." Specifically on page 50: "The use of the derivation function is optional if either an approved RBG or an entropy source provides full entropy output when entropy input is requested by the DRBG mechanism. Otherwise, the derivation function shall be used."

The "derivation function" is what digests variable-length input into a fixed-length key. The derivation function is defined on page 59 and relies on a subroutine called BCC, which is defined on page 61. The BCC routine takes a sequence of blocks and digests it into a single block, essentially encrypting the blocks in CBC mode and returning the last block:

Note that BCC is used to derive bits for a key, so no key is available yet to use within BCC. Hence BCC just uses a fixed key consisting of sequential numbers (p. 60).

As for the argument about collision resistance, let:

• K be the static key used by BCC

• A be any block

• E be the block Block_Encrypt(K, A)

Then consider the 2-block sequence A E. If we compute BCC(A E):

• The chaining value starts at 0

• The next chaining value is Block_Encrypt(K, 0 xor A) == E

• The next chaining value is Block_Encrypt(K, E xor E) == Block_Encrypt(K, 0)

• BCC returns this value, which does not depend on A

But A was an arbitrary block, so we can find a large number of inputs for which BCC returns the same output. Hence BCC, considered as a hash, does not provide collision resistance.

Whether this weakness is actually exploitable is a separate question. The threat model would involve an attacker with the ability to influence the data CTR_DRBG receives from the entropy source. That is already a high level of access, so an argument about exploitability must carefully consider whether the weakness actually allows the attacker to do something they couldn't do already.

But consider that other generators such as Hash_DRBG or Fortuna use secure hash functions which do offer collision resistance. Why rely on the weaker hash used in CTR_DRBG?

Why Caliber Security Partners?

Caliber Security is a thirteen-year-old security services firm, we hire only senior-level and experienced consultants. Our services include web and mobile application security testing, as well as network penetration testing, wireless security testing, social engineering, staff augmentation, and contract-to-hire services. 

Please reach out to us if you have any questions or if we can be of any service to you. You can contact us through the web form or by email at info@calibersecurity.com.