Research paper.  Based on NIST Special Publication 800-90A Revision 1, Elaine Barker and John Kelsey, June 2015.

Abstract:  This paper considers the architecture of deterministic random bit generators (DRBGs) standardized by NIST SP 800-90A Rev. 1: Hash_DRBG, HMAC_DRBG, and CTR_DRBG. The requirements for entropy, seed, nonce, personalization, additional input, reseeding, and protection against state compromise are analyzed. The central cryptanalytic thesis is that the formal security of the design does not compensate for a predictable seed or repeatable nonce of the application protocol: in both cases, the secret key can become computable.

1. Status and subject of the standard

SP 800-90A Rev. 1 specifies deterministic mechanisms for generating pseudorandom bits based on approved hash functions or block ciphers. Published in June 2015, it replaces the 2012 edition and is part of the SP 800-90 series, along with SP 800-90B (Entropy Sources) and SP 800-90C (Constructing a Full RBG).

DRBG is not a physical source of randomness. After initialization, it deterministically unfolds a secret seed; security depends simultaneously on the correctness of the algorithm, the unpredictability of the seed, the secrecy of the state, and operational discipline.

2. DRBG model

The functional model contains an entropy source, an internal state, and the operations  Instantiate,  Reseed,  Generate and  Uninstantiate. The consuming application requests bits, and the DRBG updates the operating state to avoid re-emitting the same sequence.

Let  EntropyInput be the data from the entropy source,  Nonce be the changing value,  PersonalizationString be the domain context,  AdditionalInput and be an optional value at the generation stage. Conceptually, the initial state is derived as

seed_material = EntropyInput || Nonce || PersonalizationString
state_0 = Instantiate(seed_material)

The exact processing depends on the chosen design: either direct Hash/HMAC/AES operations are used  Hash_df.  Block_Cipher_df Concatenation itself is not a universal implementation formula, but merely reflects the standard’s input model.

3. Entropy and the power of protection

The standard uses min-entropy as a conservative measure of unpredictability:

H_min(X) = -log2( max_x Pr[X = x] )

For the stated  S bit strength, the entropy input to instantiate and reseed must carry at least  S a bit of entropy; acceptable levels are 112, 128, 192, and 256 bits. Practical implication: a 256-bit string obtained from a counter, time, or weak PRNG is 256 bits long, but may have only a few bits of min-entropy.

Category	Normative meaning	Risk of violation	Cryptanalytic example
Entropy input	Secret input with estimated entropy corresponding to the DRBG strength	Seed iteration and full output reproduction	Debian OpenSSL (2006–2008): A bug eliminated a significant portion of the entropy, leaving a small space of possible keys; public lists of weak keys made their detection virtually trivial
Seed privacy	The seed and derived working state must remain secret.	The observer reproduces keys, nonces, and tokens	Predictable Java generators in early Android Bitcoin wallets resulted in duplicate/predictable ECDSA nonces and compromised private keys
Reseed	Input of fresh entropy until seedlife is exhausted and according to system policy	Long-term compromise after state leak	When compromising the memory of a process without reseed, the attacker continues to simulate future exits until the state changes.

4. Seed, nonce, and domain separation

Seed

A seed is a secret input that defines part of the internal state. Its entropy limits the actual strength of the entire subsystem: with ,  H_min(seed)=k an attacker can, in principle, consider a space of order  2^k, regardless of the AES key length or SHA-256 output.

Nonce at instantiate

A nonce in SP 800-90A is a value that changes between initializations and is virtually never repeated; it can be random, a counter, a timestamp, or a combination. It is  not  necessarily secret, and it does not replace the entropy input. In a typical scenario, the server transmits a monotonous launch identifier as a nonce, but obtains the seed exclusively from a trusted entropy source.

Personalization string

The personalization string links an instance to a destination and prevents dangerous state overlaps with identical inputs. A useful scheme:  service=signer; host-id; process-id; boot-counter; purpose=ecdsa-nonce. It does not add entropy, so it should not be considered as a substitute for a source of randomness.

Additional input

The additional input is mixed during Generate and/or Reseed according to the algorithm. This is convenient for contextual stream separation and for introducing fresh, unpredictable data, but predictable query fields do not create entropy.

A critical distinction.  The nonce in the DRBG interface is intended to distinguish initializations. The nonce of a cryptographic protocol (e.g., ECDSA  k or AEAD nonce) has its own semantics. For ECDSA, it must be secret and one-time; for GCM, the nonce typically need not be secret, but must not be repeated for a single key.

5. Three approved designs

Design	Cryptographic basis	State	Practical profile
Hash_DRBG	Approved hash function; Hash_df if needed	V,  C, reseed counter	Simple hash-oriented construction; does not require a block cipher key
HMAC_DRBG	HMAC on an approved hash function	K,  V, reseed counter	Clear keyed construction; widely applicable where a proven HMAC implementation already exists
CTR_DRBG	AES or TDEA in counter mode; optional derivation function	Key,  V, reseed counter	Effective on platforms with hardware AES; requires careful key and counter management

Hash_DRBG

Generation is constructed through sequential hashing of the state, conditionally:

W = Hash(0x03 || V)
V = (V + W + C + reseed_counter) mod 2^seedlen
returned_bits = Hashgen(V, requested_bits)

A historical lesson: a cryptographic hash function doesn’t save an implementation if the initial seed is predictable. In Debian OpenSSL, the cryptographic primitives themselves weren’t broken; the disaster arose at the level of random data generation.

HMAC_DRBG

The state is updated with delimiting bytes  0x00 and when data is present  0x01:

K = HMAC(K, V || 0x00 || provided_data)
V = HMAC(K, V)
if provided_data != empty:
    K = HMAC(K, V || 0x01 || provided_data)
    V = HMAC(K, V)

This diagram demonstrates why HMAC_DRBG cannot be replaced with a home-made one  HMAC(seed || counter) without a complete state update protocol, request constraints, and testing. Home-made generators often lose performance after state compromise and do not properly handle concurrent requests.

CTR_DRBG

CTR_DRBG encrypts increasing values  V ​​under the current one  Key, then updates the pair  (Key,V):

V = (V + 1) mod 2^outlen
block = AES_Encrypt(Key, V)
returned_bits = leftmost(concatenated_blocks, requested_bits)
(Key, V) = CTR_DRBG_Update(provided_data, Key, V)

Not only the CTR mode is important, but also the subsequent state update. A bug like “AES-CTR with constant key and counter after restart” creates a repeatable stream, which is analogous to a reuse keystream: the XOR of two ciphertexts reveals the XOR of the plaintexts.

6. Key material

Keys should be extracted from the DRBG output only with a strength no greater than the instance strength and the actual seed entropy. For a 128-bit symmetric key, a reasonable target is a DRBG with 128-bit strength and at least 128-bit min-entropy during initialization; for a 256-bit target, an appropriate algorithm, entropy source, and policy are required.

key_material = DRBG_Generate(L, additional_input=purpose_context)
key = leftmost(key_material, L)

You can’t use the same raw stream as the key, IV, and nonce for different protocols without domain separation. It’s better to create independent instances or include an explicit purpose string in the personalization/additional input:  purpose=tls-ticket-key,  purpose=db-encryption-key,  purpose=ecdsa-nonce.

7. Nonce in protocols

ECDSA: Secrecy and Uniqueness k

In ECDSA, the signature over a message with a hash  z uses a secret one-time nonce  k:

r = x(kG) mod n
s = k^{-1}(z + rd) mod n

If the same key  k is applied to two signatures with the same  r, the private key is recovered:

k = (z_1 - z_2) (s_1 - s_2)^{-1} mod n
d = (s_1 k - z_1) r^{-1} mod n

This isn’t a hypothesis, but a practical cryptanalytic fact: replaying the ECDSA nonce in a number of Android Bitcoin wallets allowed for key extraction and theft of funds. The DRBG here must be generated  k from an independent context, and the implementation must prevent replays during crashes, forks, and snapshot rollbacks. An alternative is a deterministic RFC 6979 nonce derived from the private key and the message hash.

AEAD/GCM: Nonce Uniqueness

For AES-GCM, replicating a nonce with the same key destroys the confidentiality of the CTR stream and weakens authentication. A practical example is incidents with TLS/network devices, where resetting a counter after a restart or faulty multithreading led to IV replays. Therefore, for GCM, a deterministic nonce construction consisting of a fixed identifier and a strictly monotonic counter is often preferred.

gcm_nonce = fixed_field || invocation_counter
# invocation_counter: unique to this AES-GCM key

A random DRBG nonce is acceptable only if the collision probability is controlled and failures are handled correctly. For a 96-bit uniform nonce, the estimated probability of at least one match after  q messages is approximately:

Pr[collision] ≈ q(q - 1) / 2^97

8. Compromise of state

The standard distinguishes between  backtracking resistance  and  prediction resistance . The first property means that compromising the current state should not allow the reconstruction of previously unobserved outputs; the second requires fresh entropy such that knowledge of the past state does not allow prediction of the future output.

Prediction resistance cannot be achieved by simply hashing the old state: it requires accessing a live entropy source when requesting generation. After a process’s memory leak, the practical procedure should include stopping secret distribution, destroying the instance, reinitializing from a healthy entropy source, and revoking potentially compromised keys.

9. Reseed, seedlife and parallelism

Each mechanism has a limit on the number of Generate calls between reseeds; once the seedlife is reached, an instance must be reseeded before further generation. Reseed is not a cosmetic upgrade: it is the threshold beyond which a new entropy contribution is made and the ability to resist prediction after a previous compromise is restored.

In multiprocess systems, copying state after  fork()a fork, restoring VM snapshots, and cloning containers are dangerous. After a fork, the child process must reinitialize or reseed the DRBG; otherwise, the parent and child may generate identical keys, tokens, or ECDSA nonces.

10. Assurance and testing

Control	What to check	Practical meaning
Known-answer tests	Test vectors Instantiate, Generate, Reseed, Uninstantiate	Detecting regressions in algorithm implementation
Health testing	Self-testing before/during operation, failure handling	Do not continue to release keys if the mechanism is faulty.
Validation	Compliance through CAVP/CMVP where applicable	Checks the implementation, but does not replace the source entropy and integration audit
Journaling	Fact reseed, errors, instance ID – no seed/state logging	Diagnostics without disclosing classified material

11. Historical context of Dual_EC_DRBG

Rev. 1 eliminated Dual_EC_DRBG, leaving Hash_DRBG, HMAC_DRBG, and CTR_DRBG. This decision has methodological significance: standardization does not eliminate cryptanalytic verification of parameters, the origin of constants, and the actual threat model.

The Dual_EC_DRBG controversy stemmed from concerns that special relationships between elliptic parameters could create a hidden ability to predict the output. Even without constructing such an attack in a specific system, this episode demonstrates that parameter transparency and the ability to independently verify are essential to trusting a generator.

12. Engineering policy

1. Obtain entropy input only from sources that have been assessed and tested against a specific policy; do not consider timestamp, PID, or MAC address as entropy.
2. Choose HMAC_DRBG or Hash_DRBG for a hash-oriented infrastructure; CTR_DRBG if you have a high-quality AES implementation and need high performance.
3. Separate assignments through personalization and additional input; do not use a single instance without context for all secret classes.
4. After fork, rollback, VM snapshot and backup restoration, force reseed/instantiate again.
5. For ECDSA, avoid repetition  k; for GCM, ensure uniqueness of the nonce per key, preferably with a rollback-proof counter.
6. Do not log seed,  K,  V,  Key, raw entropy and output intended for keys.
7. Conduct vector tests, concurrency tests, restart/fork/snapshot tests, and entropy source error path audits.

Final Provision

SP 800-90A Rev. 1 defines a mature scheme for deterministic entropy unfolding, rather than a mechanism for creating entropy out of thin air. For the key material, the min-entropy seed and protection of the internal state are critical; for the nonce, the semantics of the specific protocol are critical. Cryptanalytic incidents involving ECDSA nonce replay and weak system RNGs confirm the general principle: a single error in the randomness lifecycle can nullify the security of strong mathematical primitives.

Sources

NIST SP 800-90A Rev. 1: DRBG for key material and nonce:  https://cryptouch.ru/nist-sp-800-90a-rev-1-drbg-for-key-material-and-nonce/

1. NIST SP 800-90A Rev. 1.  Recommendation for Random Number Generation Using Deterministic Random Bit Generators . Elaine Barker, John Kelsey, June 2015. DOI: 10.6028/NIST.SP.800-90Ar1.
2. NIST SP 800-90B.  Recommendation for the Entropy Sources Used for Random Bit Generation .
3. NIST SP 800-90C.  Recommendation for Random Bit Generator (RBG) Constructions .
4. NIST. Notice on removal of Dual_EC_DRBG from SP 800-90A Rev. 1, 2014–2015.
5. RFC 6979.  Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) , 2013.
6. NIST SP 800-38D.  Recommendation for Block Cipher Modes of Operation: GCM and GMAC .