NIST’s Random Bit Beacon is a Game Changer

The US government just unveiled a machine that can generate truly random 1s and 0s. They plan to offer it as a public Internet service. This is big news because so many of our data security defenses rely on randomness, and it's hard to achieve. The role of randomness in security is often overlooked but it's critical.

The best-known use of randomness is cryptography. Every encrypted or digitally signed message depends on a randomly generated key. Every https Internet link uses SSL/TLS that requires the web server to generate a random session key to encrypt your password, credit card number, etc. If encryption keys are less than truly random, they can become predictable, potentially allowing eavesdroppers to decrypt secure messages. For example, if even one bit of a 256-bit key is predictable, the strength of AES-256 encryption is cut in half.

Other security mechanisms depend on randomness too. One-time passcodes for 2-factor user authentication displayed on phones, tokens, and text messages must be highly unpredictable. Attack simulation tools using Monte Carlo algorithms require random numbers. Big data sampling employed in threat detection tools requires them. Machine generated passwords must be unpredictable.

Randomness is like pornography; it’s hard to define, but most of us think we know it when we see it. 1011010010110 looks pretty random but 1111111111111 does not. Academics and standards bodies have developed various randomness tests. Most subject a large sample of bits (e.g., 1GB) to statistical analysis, for example to determine whether a particular binary substring appears more or less often than one would expect by pure chance. (For example, about half the bits should be zeroes.) Another technique is to subject the sample to various compression algorithms, on the theory that random bit streams are less compressible.

Most computers lack randomness. Instead they use a Pseudo Random Number Generator (PRNG) which is a mathematical function that takes an initial seed value and generates an endless string of bits from it. For example, the Mathematica software package uses a simple cellular automaton called Rule 30. The seed is typically derived from a fluctuating machine measurement such as clock drift, disk drive interrupts, or mouse jitter. This is called an entropy source. Advanced servers may have a Hardware Random Number Generator (HRNG) that includes a stronger entropy source, usually based on stochastic physical phenomena such as thermal noise, photoelectric effect, or particle decay. But even today’s best HRNGs don’t deliver true randomness.

Security researchers have sought better entropy sources for decades, but it’s a notoriously hard problem. Cats walking on keyboards has been suggested facetiously, and one university is even experimenting with the unpredictable movements of naked mole rats. A popular random bit generator on the Internet uses an array of lava lamps.

Now the National Institute of Standards & Technology (NIST) says they have the capability to generate true random bits. Mentioned almost in passing in the December Scientific American, a NIST device using Bell’s Theorem from quantum physics generated 1,024 truly random bits in ten minutes. While that’s not fast enough for commercial applications, it proves that a True Random Number Generator (TRNG) is possible in principle. The article claims “these bits were certified to be random to better than a part in one trillion” and that NIST is “working now to incorporate [their TRNG] into a public randomness beacon… broadcast over the Internet [to] be used in security applications by anyone who needs it.”

The quantum mechanics underlying NIST’s TRNG theoretically enables them to generate bits that are truly, absolutely random by any measure and thus wholly unpredictable. Step aside, lava lamps!

If NIST’s beacon becomes available at scale on the Internet, then truly random bits will be freely available for use in cryptographic keys, passcodes, and other security systems. A longtime holy grail of data security will be in our hands at last.

The more suspicious among us may wonder if NSA or other entities may wish to sabotage the beacon, introducing non-random bits as a way to backdoor encryption, but we can cross that bridge later. For now, let’s cheer NIST’s accomplishment and help them bring it to fruition.

UPDATE 5/29/2019: NIST published a draft protocol for Randomness Beacons that attempts to address concerns about malicious tampering. The NIST document and Taproot Security's feedback on it can be found here.

Michael McCormick is an information security consultant, researcher, and founder of Taproot Security.