Authors of the standard under review:  M. S. Turan, E. Barker, J. Kelsey, K. A. McKay, M. L. Baish, M. Boyle.
Source:  NIST Special Publication 800-90B, January 2018. DOI:  10.6028/NIST.SP.800-90B .

Annotation

NIST SP 800-90B defines an engineering and verification methodology for entropy sources used in cryptographic random bit generators (RBGs). The central object of evaluation is not the visual “randomness” of the stream or the average Shannon entropy, but the conservative min-entropy H_∞, which directly relates the output distribution to the probability of optimal guessing.

The document separates the source into a noise source, optional conditioning, and sanity tests; it establishes a data collection procedure, the choice between IID and non-IID branches, restart tests, statistical checks, and a set of min-entropy estimators. The cryptanalytic significance of this approach lies in the fact that entropy defects transform a strong mathematical scheme into a practically breakable implementation: keys, seeds, and one-time nonces become predictable or repeatable.

Keywords:  min-entropy, RBG, DRBG, NRBG, noise source, IID, non-IID, conditioning, health tests, ECDSA nonce, cryptanalysis.

1. Introduction and boundaries

The NIST SP 800-90 series treats RBGs as compositions: SP 800-90A defines deterministic mechanisms for DRBGs, SP 800-90B defines requirements for the entropy source, and SP 800-90C defines rules for constructing a complete RBG. Therefore, SP 800-90B is not a “randomness hashing” standard: it evaluates the origin of unpredictability before it enters the DRBG.

The key principle of the standard is that if physical or systemic noise doesn’t provide entropy, neither a hash function, cipher, nor DRBG can create it from deterministic data. Conditioning can reduce bias and concentrate existing entropy, but it doesn’t eliminate the lack of initial unpredictability.

Cryptanalytic fact

The Debian OpenSSL vulnerability (CVE-2008-0166) resulted from a change that made random value generation predictable; SSH, OpenVPN, DNSSEC, X.509 keys, and session key material were affected. This is a telling case: the cryptographic primitives may have been correct, but the space of actually achievable keys was dramatically reduced, requiring a replacement of the generated keys, not just a library update.

2. Entropy source model

Component	Purpose	Security border	Example
Noise source	Creates a non-deterministic physical or partially controlled system signal.	Primordial root of entropy.	Ring oscillator jitter, thermal noise, hardware TRNG.
Digitization	Converts the observed signal into fixed-bit-width symbols.	May introduce bias, correlations and saturation.	Select the least significant bit of the measured timer.
Conditioning	Deterministically reduces bias and prepares the output for use.	Does not produce min-entropy from deterministic input.	SHA-256, HMAC, CMAC, block cipher in permitted design.
Health tests	Detect degradation or failure in operation.	Early termination of unsafe data release.	Checking for long repetitions and abnormal character share.

SP 800-90B distinguishes between physical sources that use specialized hardware processes and non-physical sources that use system events, APIs, RAM, time, or user input. This distinction does not mean that every hardware source is automatically safe: its failure modes, environmental influences, and digital path must also be examined.

Conceptual interfaces

• GetEntropy(bits_of_entropy)  returns a bit string containing the requested estimated entropy and the execution status.
• GetNoise(number_of_samples_requested)  provides raw digitized samples for validation or external control; the interface can be disabled in production mode.
• HealthTest(type_of_test_requested)  initiates a health check and returns a boolean status.

3. Min-entropy and the attacker model

For a discrete variable X ∈ A = {x₁,…,xₖ} with probabilities pᵢ = Pr[X=xᵢ], the standard uses min-entropy—the negative binary logarithm of the probability of the most likely outcome. This is precisely an estimate of the strength of an optimal single guess.

H_∞(X) = -log₂(maxᵢ Pr[X = xᵢ]) = -log₂(p_max) Pr[successfully guess X in one optimal attempt] = p_max = 2^(-H_∞)

If a single bit produces 0 with probability 0.9 and 1 with probability 0.1, then its min-entropy is -log₂(0.9) ≈ 0.152 bits, although the stream varies and may appear “noisy” externally. For a uniform alphabet of size k, the maximum is log₂(k).

Why randomness tests are not enough

Tests of statistical randomness verify individual properties of a finite sample but do not prove cryptographic unpredictability. A predictable PRNG with an unknown seed can pass many statistical tests, whereas an attacker with knowledge of the state or seed can reproduce the entire stream. SP 800-90B therefore requires analysis of the design, raw data, dependencies, and conservative estimation.

4. Validation procedure

Validation combines design documentation and empirical data. A minimum of 1,000,000 consecutive samples is required for sequential acquisition of raw noise; if necessary, concatenation of series of at least 1,000 samples each is permissible. If a conditioner not included in the NIST-reviewed designs is used, at least 1,000,000 of its consecutive outputs are also collected.

1. Describe the noise source, digitization, environment, probable failures, and claimed entropy rate.
2. Obtain sequential raw data and restart data matrix.
3. Justify the IID hypothesis or choose a conservative non-IID branch.
4. Estimate min-entropy using applicable methods.
5. Apply restart tests and reduce the stated score if necessary.
6. Consider conditioning, determine the credited output entropy and introduce operational health tests.

Restart tests

The standard requires 1000 source restarts and 1000 sequential samples after each, forming a matrix M[1000][1000]. Rows and columns are tested separately: rows identify the repeatability of an intra-process start, columns identify the dependence of a specific position on the initial state, environmental parameters, or hidden state.

M[i][j] = j-th sample after i-th restart, 1 ≤ i, j ≤ 1000

The cryptanalytic purpose of a restart check is to identify a scenario in which a device returns identical or highly correlated seeds after power-on. Boot times, power resets, virtualization, and early initialization often reduce the diversity of system events, so checking only a long, continuous workflow is insufficient.

5. IID and non-IID branches

Branch	Premise	Grade	Risk of misuse
IID	There is a technical justification for independence and identical distribution; the sequential set, rows and columns of the restart matrix do not provide evidence against IID.	In IID data, the key estimator is the most frequent value.	Ignoring memory, periodicity, or state influences overestimates entropy.
non-IID	IID not declared or confirmed.	A set of raters is applied; the result is the lowest applicable rating.	The score is usually lower, but better matches the attacker exploiting dependencies.

The phrase “no evidence against IID” is not a mathematical proof of IID. This is why choosing an IID branch requires both engineering justification and statistical results; when in doubt, it is cryptographically more correct to use non-IID analysis.

IID checks

Section 5 constructs permutation testing: the original order statistics are calculated, the data are shuffled iteratively using the Fisher-Yates algorithm, and the statistical values ​​are compared. The excursion, number and lengths of directed runs, increases/decreases, runs relative to the median, mean and maximum collisions, periodicity, covariance, and compressibility are analyzed; chi-square tests for independence and goodness-of-fit are also applied, as is the length of the largest repeated substring.

6. Min-entropy estimators

Appraiser	What structure does it reveal?	Cryptanalytic interpretation
Most Common Value	Dominant symbol.	The attacker always chooses the most common value.
Collision	Frequency and distance to repetitions.	Excessive collisions indicate a narrowed effective space.
Markov	Dependence of the next bit on the previous one.	Exploits first-order memory.
Compression	Regularities that make a flow compressible.	A structured sequence carries less new information.
t-Tuple and LRS	Frequent blocks and longest repeated substrings.	Detect local repetitions and patterns.
MultiMCW, Lag, MultiMMC, LZ78Y	Predictability across windows, lags, contexts, and vocabulary structure.	Model predictor strategies with different memories.

In the non-IID branch, it’s impossible to choose the “best” result: the declared score is limited by the minimum scores of the applicable evaluators. This expresses the cryptanalytic worst-case principle: a single effectively exploited dependency is enough for the actual guessing difficulty to be significantly lower than the average score.

H_claim ≤ min(H_MCV, H_collision, H_Markov, H_compression, H_t-tuple, H_LRS, H_predictors, …)

7. Air conditioning

A conditioner is a deterministic function capable of reducing bias and producing a compact stream suitable for seeding DRBGs. The paper separately considers conditioners built on proven cryptographic mechanisms and alternative solutions that require a separate study of the conditioned output.

Critical limitation: hashing a repeated string does not transform it into a source of randomness. If the input is fully known to the attacker, the result of SHA-256, HMAC, or AES is also precomputable; a correct construction can only redistribute existing entropy and should not be credited beyond what is physically present in the input samples.

H_∞(f(X)) ≤ H_∞(X) for a deterministic function f Rule of thumb: The length of the reported output should not be interpreted as the amount of entropy obtained.

8. Continuous health tests

The standard requires initial, continuous, and, if necessary, on-demand checks. These do not replace the initial entropy assessment: their purpose is to detect observable failure symptoms with a high probability and quickly stop use of the defective source.

Test	Idea	Failure scenario
Repetition Count Test (RCT)	Signals if the same symbol is repeated in too long a continuous series.	Stuck ADC, constant output, failed oscillator.
Adaptive Proportion Test (APT)	In a fixed-length window, limits the excessive number of occurrences of the selected character.	Strong distribution shift, sensor saturation, change in environment.

The threshold is configured using the acceptable false alarm probability α and the stated worst-case entropy level. A design error is to interpret passing the RCT/APT as proof of a good RNG: a narrow test set may miss complex correlations, predictable initialization, or malicious source control.

9. Historical cryptanalytic examples

Debian OpenSSL, 2006–2008

A defect in a Debian-specific OpenSSL change made the generator predictable and compromised many types of key material. According to SP 800-90B, this is an example of a system source where trusting the API or the fact that the crypto library was called is insufficient: the actual variability of inputs and the consequences of errors in the entropy accumulation pathway must be investigated.

PlayStation 3 and repeat nonce ECDSA

In 2010, fail0verflow demonstrated that Sony used a constant nonce in ECDSA signatures for PlayStation 3 firmware. This is not an elliptic curve attack: repeating the secret key k in two signatures makes the private key algebraically derivable.

s₁ = k⁻¹(z₁ + r·d) mod n s₂ = k⁻¹(z₂ + r·d) mod nk = (z₁ – z₂) · (s₁ – s₂)⁻¹ mod nd = (s₁·k – z₁) · r⁻¹ mod n

Here d is the private key, zᵢ is the message hash representation, and (r,sᵢ) are the signatures. This example demonstrates the limiting case of zero or reusable nonce entropy: two signatures are sufficient to compromise a trusted key.

Practical conclusion for Bitcoin

ECDSA signatures in Bitcoin also depend on a secret one-time nonce. The repeatability or predictability of the nonce allows the private key to be recovered from published signatures; therefore, the implementation must use a reliable entropy source or a deterministic nonce according to RFC 6979, with a properly protected private key and hash function. SP 800-90B addresses the foundation of this chain—the quality of the source used to generate keys, seeds, and other secret values.

10. Practical implementation profile

1. Formulate a threat model: failure, spoofing, temperature/power supply effects,
virtualization, re-initialization, system API compromise.
2. Export raw samples prior to conditioning in an isolated test mode.
3. Collect ≥ 1,000,000 consecutive samples and a 1000 x 1000 restart matrix.
4. Document the IID hypothesis; if unprovable, select the non-IID track.
5. Run SP 800-90B estimators and declare a conservative minimum.
6. Design RCT/APT and failure responses: output blocking, logging,
secure recovery, re-initialization.
7. Seed the DRBG only when sufficient entropy credit is available; reseed according to policy.
8. Conduct regression tests for hardware revisions, firmware updates, and operating conditions.

For reproducible analysis, NIST publishes an implementation of  SP800-90B Entropy Assessment , which implements the min-entropy estimation methods described in the publication. This tool is not a substitute for engineering reasoning: the results are meaningful only if the raw data is correctly collected, the character width is known, and the source is accurately described.

Conclusion

NIST SP 800-90B transforms the question “Does a stream appear random?” into a verifiable discipline: from the physics or systemic origin of noise—through raw samples, dependency analysis, and conservative min-entropy—to the monitoring of exploitable failures. This is especially important for a cryptanalyst: a successful attack often doesn’t break AES, SHA-2, or ECDLP, but rather exploits a small seed space, repeated nonce, state correlation, or a failed restart.

Literature

NIST SP 800-90B – entropy sources: https://seckey.ru/nist-sp-800-90b-entropy-sources/

1. MS Turan et al.  Recommendation for the Entropy Sources Used for Random Bit Generation . NIST SP 800-90B, January 2018. DOI:  10.6028/NIST.SP.800-90B .
2. NIST.  SP800-90B Entropy Assessment , source code for min-entropy estimators:  github.com/usnistgov/SP800-90B_EntropyAssessment .
3. Debian Security Advisory DSA-1571-1: OpenSSL predictable random number generator, CVE-2008-0166.
4. fail0verflow. Report on ECDSA nonce defect in PlayStation 3, 27C3, 2010.