Critique of NIST Entropy Source Guidelines (SP800-90B)

As I've pointed out in previous Diceware blogs, random number generation is a critical component of  cryptographic systems. The U.S. National Institute of Science and Technology (NIST) knows this too, and has published a guideline on the topic, NIST Special Publication 800-90.  This document was revised in 2012 and split into three documents:

• SP 800-90A covers deterministic random number generators (DRNGs), also known as pseudorandom number generators. 
• SP 800-90B covers criteria for entropy sources (ES), the devices from which we get unpredictable randomness.
• SP 800-90C discusses how to combine the entropy sources in 90B with the DRNG's from 90A to provide large quantities of unpredictable bits for cryptographic applications.

Note that 90B and 90C are still marked as drafts. 

Most people don't consider standards documents good bedside reading material (a mistake, because they are a wonderful cure for insomnia). But they exert a strong influence on systems design in the  long term.  I have an interest in random number generation for cryptography --Diceware suggests using ordinary six-sided dice as a slow, but dependable, high quality source of entropy-- so I have tried to plow through these documents. 

The good news and the bad news

Crypto system designers will find lots of useful information in the SP800-90 series, but there is one thing they won't learn: instruction on how to generate those all important random numbers. None of the documents discuss actual sources of entropy, just how to package them as hardware and software objects, and ways to test them.  Worse the packaging and testing advice does not even address all the problems than can arise.

As I see it, there are six classes of threats to cryptographic-grade random number generation:

1. Hardware problems.  This includes component failure, manufacturing variation and entropy sources that do not perform as advertised. 
2.  Data leakage. Most uses of  cryptographic grade random numbers require that the numbers generated be kept secret. An attacker might used data leaked from the random number generation process to compromise security.
3. Provisioning failure. This affects newly installed or reset systems. They must not use random numbers to generate crypto objects before enough randomness (entropy) has accumulated.
4. Bad system design and programming.  Even a small programming mistake can compromise security. 
5. Subversion. If an attacker can trick a cryptographic system into using numbers generated by an algorithm under the attacker's control instead of the "official" RNG, they can defeat security in ways that are undetectable and do not require any channel back to the attacker.
6. Backdoors. There are many ways a bad guy could incorporate circuitry or firmware in an entropy source that produces bits which appear to be random but are, in fact, predictable enough to that bad guy to allow a security breach.  Electronics manufacturing today is a transnational business. While the US government has a program to find entirely domestic sources for sensitive electronics, almost all commercial and consumer electronics contain components made in multiple countries.  

NIST to the rescue?

In my view, NIST has only addressed the first three threats in SP800-90. It proposes a series of statistical tests to look for threat 1 and limits threat 2 by designing DRNGs in ways that a leak of their current state does not compromise numbers generated in the past, anne by mandating unspecified  security boundaries around the RNG process. The availability of dedicated hardware entropy sources, coupled with proper software design, should deal with threat 3. One purpose of having a software spec is to address threat 4, but excessive complexity, opaque writing and feature creep in the spec often just confuse designers and programmers.

To achieve acceptable security, it is vital to address all six threats. If you are serious about cryptography you must have a healthy dose of paranoia. 

An entropy source is a potential single point of failure in a cryptographic system. And failures can be disastrous. For example, NISTs own Digital Signature Algorithm (FIPS-186) requires a random number be generated for every signature. If two different documents are signed using the same random number, the private key used for all signatures can easily be recovered, allowing an attacker to forge valid signatures to any document they wish. The private signing key for Sony's Playstation 3 software, a most valuable corporate asset, was compromised and made public in this way.

Minimalism wins

In my opinion, SP-800-90B goes wrong at the very beginning, with Figure 1, its Entropy Source Model.  It allows an entropy source to include a conditioning element between the digitizer of the physical noise source and the ES output. Raw output is supposed to be provided for validation, but not necessarily to the user. 

Better security would be afford by a minimalist Entropy Source, consisting of a physical source of noise and a digitizer, and nothing more. Ideally it should be an output-only device, with a DC power source as its sole input.  Any conditioning needed can and should be performed by the device consuming the random bits, not the entropy source. If one believes, as NIST evidently does, that conditioning algorithms can convert weak entropy sources into full entropy random numbers, there is no need for anything beyond the digitization in the ES. Even health testing should be restricted to situations where a hardware test has an advantage over software. For example, a entropy source that digitized amplified noise, might include a simple analog circuit that averaged the noise output.  Otherwise, health tests are best left to software. 

The natural variations in a physical entropy source provide a useful means of verification. A bias in 0 to 1 ratio that is traceable to how operating temperature affects the noise source could be tested and provides an additional level of confidence in the source.  A full entropy source is therefore less trustworthy since it is impossible to distinguish between it an a DRNG. The complex circuitry needed for full entropy conditioning or elaborate health testing within a ES also can provide a place to hide a back door DRNG  with constricted state. Input pins can prove a signal to open the back door by switching output from true entropy to the DRNG.

Adding elaborate health tests to entropy sources also increases the cost. It might well be better to include two independent simple entropy sources in a system rather than one with elaborate health testing built in. 

A entropy source module should be as simple and verifiable as possible.  The engineering involved in its design and verification is distinct from general digital electronics.  There needs to be a chain of custody from the design and verification, through manufacturing, installation and use. 

The specifications for an entropy source module should list elements that are not allowed. These might include:

• Any programmable element, such as a microprocessor or FPGA
• Digital storage sufficient to remember previously generated entropy
• Any clock with enough stability and range to provide predictable time of day information. (To prevent an attacker from knowing that weak numbers are generated at specific times.)
• Any unexplained circuitry
• Any technology designed to prevent reverse engineering of the module
• any input pins besides ground and DC power 

Things that are desirable include shielding, a tamper resistant package, revision codes, lot numbering and certification by the manufacturers that the unit is identical in design to units submitted for verification. 

SOC

The approach I am suggesting requires some modification for single chip devices, such as smart cards.  But even here the entropy source can be isolated to a region of the chip that can be inspected. While pins are expensive in complex integrated circuits, it may still be desirable to bring the output of the entropy source to a pin so it can be tested externally. Another approach might be to include a one-axis microelectromechanical (MEMS) accelerometer in the design. These can be easily tested externally and would allow entropy accumulation during shipment. In any case, nothing should be done to prevent verification of the entropy source design by x-ray or other reverse engineering means.

Conclusion

Random number generation is the Achilles' Heel of cryptographic systems, It's vital we get it right. The KISS principle -- keep it simple, stupid -- applies.