High-quality random numbers are essential for secure encryption.

Random numbers are used extensively in encryption. They can form the basis of critical security parameters (CSP) such as encryption keys used for transactions made over the public Internet.

Frequently, attackers trying to defeat the encryption will focus on finding or inducing exploitable patterns in the random numbers, which allow keys to be guessed more efficiently than using a brute force search. Attackers can adopt a host of different techniques such as varying the voltage and temperature to try and disrupt a noise source’s normal operation or using the output of a near identical random number generator (RNG) under their control to help predict the RNG’s output in the system under attack.

Poor quality random numbers used as encryption keys can jeopardize the security of all the messages or data processed using that key. When the RNG doesn’t provide prediction resistance, creating a new encryption key using the jeopardized RNG is insufficient and all future messages and data are at risk until the RNG is reseeded. Defining “poor quality” is fraught with difficulties, because to prove that a string of data is or is not random is a complex and lengthy exercise. Fortunately, looking at the problem from the reverse direction can provide an answer for what is a cryptographically acceptable random number.

The National Institute of Standards and Technology (NIST) recommends a method (specification SP800-90A/B/C) that’s suitable for embedding into an FPGA or SoC. SP800-90A defines a deterministic random bit generator (DRBG), which is a purely digital circuit based on the Advanced Encryption Algorithm (AES) algorithm. Hardware noise sources are considered and defined in SB800-90B, including test circuits, which can be used in the system to detect if their output is no longer random (e.g., due to tampering or a fault) and statistical tests to qualify a particular circuit for use as a hardware noise source. SP800-90C considers how the DRBG and noise source can be combined in the system. Combining a cryptographic algorithm-based DRBG with a physical noise source produces an RNG that offers the best of both worlds, prediction resistance based on the hardware noise source combined with guaranteed statistical properties of the encryption algorithm.

An RNG core comprises the circuitry to accomplish this task. It includes a complete AES core as a critical part of the design. One standard mode of use for the AES algorithm is called counter (CTR) mode. In this mode, the value from a counter is encrypted using a secret key to produce what is effectively a random 128-bit block of bits. Data is then encrypted or decrypted by XORing it with the random bits. The combination of the counter and AES unit in AES-CTR is acting like a DRBG. It produces a sequence of random numbers whose values are completely predictable to anyone who knows the key, but extremely difficult to determine without the key. If the key for the AES unit is taken from a physical noise source (seeding the DRBG), we have the essential basis of the CTR-DRBG scheme specified in SP800-90A.

The system in SP800-90A goes further and provides no less than three other sets of inputs as well as the physical noise (called the entropy).

The Nonce input is used along with the entropy input when constructing a seed for the RNG. The Nonce makes sure the calculated seed doesn’t depend only on the entropy and is guaranteed to change in every instantiation. The Nonce data can be a simple counter or derived from timestamps, but must be different for each use and secured from tampering.

The personalization string input is another optional input used when instantiating the RNG. This might be a serial number that’s different for each machine. This ensures that two copies of the RNG will behave differently and defends against attackers who obtain their own copy of a product containing the RNG to make predictions of how the RNG in the target copy will behave.

The additional input provides a mechanism for including additional entropy to the DRBG. For example, it’s usually easy to find a set of signals in a design which look as if their values will be essentially random, but harder to qualify them as a noise source to the extent needed for SP800-90B. Using the additional input, these bits can be “stirred into the soup” on the basis that even if they do no good, at least they’ll do no harm. This provides an extra layer of protection if the main entropy source was compromised.

The DRBG combines the various inputs in a complex, but totally deterministic way. It relies on the AES algorithm’s security properties to ensure that an attacker will be unable to predict or reverse engineer the system outputs, provided the attacker doesn’t have access to all the inputs (including the AES key).

The system’s deterministic nature is essential to the operation of the final significant block in the system, known as the health check. When initiated, it isolates the RNG from any other signals, loads test data, and compares the output against a set of known answers. The health check is initiated automatically following reset and on request, for example if another part of the system detected an attack. If the health check fails, called a catastrophic error, then the logic is designed to lock-up to stop any unreliable data from being output. The system needs to be reset after a catastrophic error by cycling the power supply or reconfiguring the FPGA.

In addition to the DRBG circuitry described, a source of entropy is required. In a purely digital system, a common choice is a free running ring oscillator which clocks a counter. The counter’s least significant “n” bits are used as an n-bit seed. The ring oscillator’s frequency can’t accurately be determined externally because it’ll differ slightly with thermal variations and noise on the power supply voltage. If the ring oscillator is left running for a considerable time and the counter is relatively small (a few bits), the counter value will be largely random. An obvious problem with this and many other physical noise sources is that random values may be required more frequently than the physical noise source can supply them. The DRBG allows multiple random numbers to be generated between periodic re-seeding from the physical noise source.

The RNG might sound complicated (which it is), but an encryption algorithm is only as strong as the key presented to it. So the RNG is an essential component of the security system.

Paul Dillien has worked with Algotronix Ltd. covering sales and marketing for the past six years. He previously worked in the FPGA industry, and is the author of The FPGA Market report. Paul is a Chartered Engineer and has worked in strategic and tactical marketing roles for leading U.S. and UK semiconductor companies and has specializations in competitive analysis and negotiation.