Original Authors: Elaine Barker, John Kelsey (NIST).
Document: NIST Special Publication 800-90A Revision 1, June 2015.
DOI: 10.6028/NIST.SP.800-90Ar1 .
Annotation
NIST SP 800-90A Rev. 1 defines a normative architecture for deterministic random bit generators (DRBGs) designed to generate cryptographically pseudorandom data after initialization with entropy seeding. The standard specifies three families—Hash_DRBG, HMAC_DRBG, and CTR_DRBG—and decouples the cryptographic strength of the expansion mechanism from the quality of the entropy source. The work systematizes the state model, seeding and reseeding requirements, prediction resistance and backtracking resistance properties, algorithmic constructs, validation issues, and applied cryptanalytic lessons.
Keywords: DRBG, entropy, min-entropy, HMAC_DRBG, Hash_DRBG, CTR_DRBG, PRNG, reseed, forward security, backward security, cryptanalysis.
Introduction
Cryptographic systems often fail not because of weaknesses in AES, SHA-2, or elliptic curves, but because the key, nonce, salt, or ephemeral scalar were predictable. A DRBG is not a “source of true randomness”: it is a deterministic mechanism that expands a secret entropy seed into a large stream of pseudorandom bits. Its output is computationally indistinguishable from random only if certain conditions are simultaneously met: sufficient seed entropy, secrecy of the internal state, correctness of the primitive, and a leak-free implementation.
SP 800-90A covers requirements for the use of DRBG, precise specifications based on hash functions and block ciphers, implementation aspects, and quality assurance. The entropy source and the composition of the full RBG are specified in SP 800-90B and SP 800-90C, respectively; therefore, compliance with 90A alone does not prove the security of the device as a whole.
Terms and threat model
| Term | Meaning for analysis |
|---|---|
| Entropy input | An input with an estimated lower bound on unpredictability; its secrecy is critical during instantiation and reseed. |
| Seed | The material from which the initial working state is derived; the seed length and the number of entropy bits are different values. |
| Internal state | A collection of secret and service values; compromise of the operational state is the central threat. |
| Instantiate / Generate / Reseed / Uninstantiate | Life cycle: initialization, issuance, updating with fresh entropy, safe destruction of state. |
| Security strength | The target adversarial performance level is 112, 128, 192, or 256 bits; the entire chain, including entropy and the underlying primitive, must support it. |
Mini-entropy
The standard uses the worst-case unpredictability—mini-entropy. For a discrete variable X with probabilities p_i:
\[H_\infty(X) = -\log_2 igl(\max_i p_i igr).\]
If the most probable value occurs with probability 1/256, then H∞ = 8 bits, even if the distribution has many other outcomes. This metric prevents optimistic estimates of the average entropy and directly links the quality of the seeding to the difficulty of enumeration.
Cryptanalytic Fact: Debian OpenSSL
Incident CVE-2008-0166 demonstrated that the mathematical strength of RSA and TLS does not compensate for a generation flaw: an erroneous modification of OpenSSL in Debian made generated cryptographic values predictable. SSH/OpenVPN/DNSSEC keys, certificates, and TLS session material were affected; after fixing, not only a patch was required but also regeneration of the compromised keys. This is a practical illustration of the requirement of SP 800-90A: the security of DRBG is determined by both the mechanism and the source of randomness.
Functional architecture
During instantiate, the mechanism receives an entropy_input, optionally a nonce, and an optional personalization_string; the result is the initial state. During each Generate, additional_input is allowed, the requested number of bits is emitted, and the working state is immediately updated. Reseed introduces fresh entropy into the new state, and Uninstantiate is required to reset the internal secrets.
entropy_input + nonce + personalization_string
│
▼
Instantiate ──► state_0
│
additional_input ─► Generate ──► output_1, state_1
│
fresh entropy ─────► Reseed ──► state'_1
Separating mechanisms by purpose is a sound engineering measure: separate instances for generating keys, nonces, and other domains limit the consequences of state routing errors. Personalization also prevents unwanted state overlaps with identical entropy input.
Sowing and life cycle
To achieve the stated strength S, the source must provide at least S bits of entropy, and the seed and entropy_input must be protected as secrets. The nonce does not replace entropy: it serves to distinguish instances and must have a negligible probability of replay. Personalization_string and additional_input do not have to be secret, so they cannot be mistakenly counted as contributing to entropy.
Reseed is a cryptographic boundary for recovery after a compromise: fresh entropy, unknown to the attacker, makes the subsequent flow unpredictable again. Each mechanism has a limit on the number of Generate calls in a single seed period; when this limit is reached, the implementation must request a reseed rather than continue working with the expired state.
Practical example
The hardware signature module can take noise input from a validated source, instantiate HMAC_DRBG-SHA-256, include the module identifier and download counter in personalization_string, and reseed regularly. If the entropy source is temporarily unavailable, the correct outcome for an operation with a prediction resistance requirement is failure, rather than replacing the entropy with the current time.
Directions of resistance
| Property | Compromise model | Practical meaning |
|---|---|---|
| Backtracking resistance (backward security) | The enemy received the state after time T. | It shouldn’t restore previously undisclosed outputs. Updating state after Generate mitigates the damage from late leaks. |
| Prediction resistance (forward security) | The enemy has obtained the state before time T. | New outputs after receiving fresh entropy should not be predictable. Requires reseed before issuing when requested. |
The terms “forward/backward security” are used ambiguously in engineering literature; for precision, the NIST definitions should be followed: prediction resistance refers to the future relative to the leak, while backtracking resistance refers to the past. Simply hashing the old state does not create prediction resistance: if the attacker knows the state and all subsequent deterministic inputs, they simulate the flow.
Historical example: nonce in ECDSA
In ECDSA, a one-time secret scalar k associates a signature with a private key d. Repeating k for two messages yields equations from which d can be recovered:
\[s_i = k^{-1}(z_i + rd) mod n,\qquad k = (z_1-z_2)(s_1-s_2)^{-1} mod n,\qquad d=(s_1k-z_1)r^{-1} mod n.\]
This class of attacks demonstrates the cost of randomness: even the robustness of the discrete logarithm on an elliptic curve doesn’t save a signature with a weak, repeating, or predictable nonce. The DRBG must be seeded well, and the application must correctly convert the output to a scalar without statistical bias.
Three DRBG mechanisms
| Mechanism | Base and condition | Advantages | Engineering risks |
|---|---|---|---|
| Hash_DRBG | One-way hash function; working values V and C, reseed counter. | Simple reliance on the strength of the approved hash; no secret block cipher key. | A correct choice of hash for the required strength and precise implementation of arithmetic/length are required. |
| HMAC_DRBG | HMAC; secret Key and V, reseed counter. | A conservative keyed design suitable for software crypto libraries. | Key/V memory protection, Update correctness, and additional_input handling are critical. |
| CTR_DRBG | CTR-style block cipher; Key and counter V, AES or historically TDEA. | Efficiency where AES is hardware accelerated; clear block output structure. | Key and V cannot be repeated/incorrectly updated; the variant without a derivation function imposes particularly strict requirements on the full-entropy input. |
Hash_DRBG
Hash_DRBG generates a seed from the entropy, nonce, and identity, then outputs V and a constant C via Hash_df. Upon output, it uses Hashgen(V) and updates V using the hash value, C, and reseed_counter. The goal is to ensure one-way state evolution, so that knowledge of the current V prevents any practical reversal of the computation to the previous V.
# Pseudocode scheme (not a ready-made library implementation) seed_material = entropy_input || nonce || personalization_string V = Hash_df(seed_material, seedlen) C = Hash_df(0x00 || V, seedlen) returned_bits = Hashgen(V, requested_bits) V = (V + Hash(0x03 || V) + C + reseed_counter) mod 2^seedlen
The real cryptanalytic meaning is that Hash_DRBG does not “create” entropy. If the seed_material is brute-forced, the attacker will repeat Hash_df and the entire stream; the hash only expands the hidden input and ensures computational one-wayness of the state transition.
HMAC_DRBG
HMAC_DRBG stores Key and V, initializing them to fixed values, after which Update mixes the seed_material with multiple HMAC calls. On Generate, the stream is obtained by iterating V = HMAC(Key, V); then Update changes both secrets. This scheme is convenient for logged and testable code, since its state is compact and the entire update is expressed using HMAC.
# Schema Update(provided_data)
K = HMAC(K, V || 0x00 || provided_data)
V = HMAC(K, V)
if provided_data is not empty:
K = HMAC(K, V || 0x01 || provided_data)
V = HMAC(K, V)
An example use case is generating ephemeral TLS keys within a process where SHA-256/HMAC and protected memory are available. Leaking K,V via a memory dump is still dangerous: protecting the past depends on a correctly executed state update, and protecting the future depends on a subsequent reseed with entropy unknown to the attacker.
CTR_DRBG
CTR_DRBG generates blocks as AES_Key(V), incrementing V, and then updates Key and V via CTR_DRBG_Update. The variant with Block_Cipher_df compresses and normalizes the input material to seedlen; the variant without a derivation function is only allowed with full entropy requirements and does not use a nonce during instantiation.
# Simplified Generate fragment
if additional_input:
(Key, V) = CTR_DRBG_Update(Block_Cipher_df(additional_input), Key, V)
while len(temp) < requested_bytes:
V = (V + 1) mod 2^blocklen
temp += AES_Encrypt(Key, V)
(Key, V) = CTR_DRBG_Update(processed_additional_input, Key, V)
return leftmost(temp, requested_bytes)
A practical counterexample is to treat CTR_DRBG as a regular AES-CTR with a constant key and a resettable counter. Repeating the (Key,V) pair repeats the block stream; the standard prevents this by mandating a state update, and the implementation is required to prevent snapshot/VM rollbacks to the old state without a reseed.
Convert to range
The output of a DRBG is a bit string; the application protocol often requires a uniform number in [0, n − 1]. A simple r mod n operation creates a bias if 2^L is not a multiple of n: some residues have one more preimage. Rejection sampling is preferred: take an L-bit x and repeat the selection until x < T, where T is the largest multiple of n not exceeding 2^L.
\[T = \left\lfloor rac{2^L}{n} ight floor n,\qquad r=x mod n\quad ext{at }x<T.\]
For ECDSA, this is important when mapping random bits to the range 1..n−1. The bias doesn’t usually mean instant key recovery, but it does violate the uniform nonce model and creates statistical material for specialized cryptanalysis, especially when some bits are leaked together.
Validation and operation
SP 800-90A requires documentation, validation testing, and continuous monitoring of the implementation’s health. The minimum set includes known-answer tests and separate checks for Instantiate, Generate, Reseed, and Uninstantiate; a partial pseudo-random result cannot be returned on error. Internal state must be reset upon instantiation destruction and protected no less securely than the data for which the stream is generated.
The following checklist is useful for production:
- Use a system-provided CSPRNG or a validated DRBG instead of a home-made generator.
- Choose a single target security strength and match entropy, hash/AES, and key lengths to it.
- Ensure safe reseed after startup, fork, VM/snapshot restore, and events that can clone state.
- Use domain separation: separate instances or unique personalization strings for different purposes.
- Do not log entropy_input, seed, Key, V and additional_input if the latter may be sensitive.
- Check request limits and correctly handle “reseed required” and catastrophic entropy source errors.
- Apply rejection sampling to ranges where the modular transformation introduces bias.
Dual_EC_DRBG as a lesson in standardization
In Revision 1, the previously approved Dual_EC_DRBG was removed from the specification. NIST cited a public loss of confidence and concerns that the parameters could allow for prediction of secret keys; NIST’s historical archive notes that cryptographers had identified a potential parameter issue during the development of the guidelines. This episode is important not as an argument against standardization, but as evidence of the need for open cryptanalysis, verifiable parameter provenance, and cryptographic flexibility.
The practical implication is that a mechanism should be selected not based on formal “approval” in isolation from context, but on the combination of design transparency, implementation quality, cryptanalytic maturity, availability of hardware primitives, and migration capability. This is why SP 800-90A retains several independent DRBG families: a vulnerability in one class should not paralyze the entire infrastructure.
Final Provisions
SP 800-90A Rev. 1 is a fundamental standard for deterministic entropy expansion, but it is not a recipe for “randomness from nothing.” Its central thesis is cryptanalytically rigorous: a secure DRBG requires a simultaneously hidden and sufficiently entropic seed, a strong underlying primitive, proper state evolution, timely reseed, and a leak- and replay-free implementation.
For the cryptographer and auditor, the most important boundaries are between components: 90A specifies the mechanism, 90B specifies the provability of the entropy quality, and the application is responsible for the lifecycle, range transformations, and state persistence. Historical incidents with predictable keys and nonce replication confirm that an audit of randomness generation is an audit of the root of trust of the entire cryptosystem.
Sources
NIST SP 800-90A Rev. 1: DRBG cryptographic analysis: https://paytu.ru/nist-sp-800-90a-rev-1-drbg-cryptographic-analysis/
- E. Barker, J. Kelsey. Recommendation for Random Number Generation Using Deterministic Random Bit Generators . NIST SP 800-90A Rev. 1, 2015. DOI: 10.6028/NIST.SP.800-90Ar1 .
- NIST. NIST Removes Cryptography Algorithm from Random Number Generator Recommendations , 2014.
- CERT/CC. VU#925211: Debian and Ubuntu OpenSSL packages contain a predictable random number generator , 2008.