Understanding Intel's Ivy Bridge Random Number Generator

Random number generation is the Achilles heel of cryptography. Cryptographic algorithms – key generation, encryption and signing – need secret values that must be unknown to attackers, and the best way to create such a value is to choose it at random. But there is no way for software to create random numbers. All it can do is stretch out randomness from another source. That source might be the mechanical behavior of spinning discs, or temperature measurements, or network timing, or mouse and keyboard movements. Not all computers have mice, keyboards, temperature sensors or spinning discs. Embedded systems, virtual machines and servers with solid-state discs might have serious trouble gathering entropy.

Even when software can gather enough entropy, the random number generator (RNG) itself is notoriously difficult to test, and may contain subtle weaknesses that go unnoticed for years. These flaws can have serious consequences. For example, from September 2006 to May 2008, all OpenSSL keys generated on Debian and Ubuntu Linux systems were weak: server certificates, SSH login keys, email encryption and signing keys. Even using an ECDSA signing key on one of these systems would compromise it. This bug was caused by a one-line code change to OpenSSL's random number generator. Software-based RNGs are difficult to build and test, often hard to use, and still don't work everywhere. That's why security-oriented processors usually contain a dedicated hardware RNG, even though most general-purpose cores do not. Now Intel has included a hardware RNG on their "Ivy Bridge" processors, which were released earlier in 2012.

The Ivy Bridge Entropy Source

Each Ivy Bridge die contains one hardware RNG, shared by all the cores. The RNG begins with an entropy source (ES) whose behavior is determined by unpredictable thermal noise (Fig. 1). The core of Ivy Bridge's ES is an RS-NOR latch with the set and reset inputs wired together (red). When the R/S input is de-asserted, the latch becomes metastable, and its output eventually settles to 0 or 1, depending on thermal noise. The tricky part is consistently reaching that metastable state. This is accomplished by a negative feedback circuit (blue). This circuit adjusts the charge on a set of large capacitors, which is used as an extra input to the latch. The feedback nudges the latch slightly more toward 0 whenever it produces a 1 and vice-versa. The buffering circuit (green) detects when the latch has settled, and stores its output. After a delay it asserts and then de-asserts the latch's R/S input to produce another bit.

Figure 1. This circuit uses a trimmed 1-shot to provide an entropy source.

The ES produces its own clock signal, which ticks irregularly at around 3GHz. The rest of the RNG operates at 800 MHz, so the RNG's output is first sampled into that clock domain. Next, a series of health tests inspects the samples to make sure that the entropy source hasn't failed.

The Conditioning Logic

The output of the ES is fairly high-quality, but it isn't strong enough for cryptographic purposes. The output won't be entirely balanced. The feedback circuit introduces bias, and the entire circuit may be influenced be analog effects such as ringing. To solve this, the output is passed through a cryptographic conditioner (Fig. 2), which condenses many mediocre random bits into a few very good ones. Even "unhealthy" samples are sent to the conditioner, because they can't hurt the quality of its output.

Figure 2. The feedback circuit introduces bias so the output is passed through a conditioning pipeline to improve overall quality.

The conditioner produces a 256-bit seed value every few microseconds. But if all the cores on the chip are asking for random data, this won't satisfy the demand. Therefore, the seed value is fed into a NIST SP800-90A-based pseudorandom generator. This generator uses 128-bit AES in counter mode, and increases the amount of data that the generator can produce to around 800 megabytes per second.

Finally, the random data is put into an output buffer, where it can be retrieved, 64 bits at a time, by the RDRAND instruction. This instruction sets its destination register to a random value. RDRAND sets the processor's carry flag to indicate success. If the RNG fails (temporarily due to contention or permanently from a failed self-test), RDRAND instead clears the carry flag and outputs 0. Because the RNG itself signals failure by returning 0, the RDRAND instruction can never succeed with a 64-bit output of 0. This bias is generally small enough to ignore.

Cryptography Research's Review

Intel asked Cryptography Research to review the design of the RNG (download Analysis of Intel's Ivy Bridge Digital Random Number Generator). The summary is that the Ivy Bridge RNG is very conservatively designed, and the few concerns we identified do not materially affect its security.

The entropy source itself is mathematically sound. The capacitors in the tuning circuit need to be large; a pulse from the 1-shot must change them by less than the amplitude of the thermal noise in the circuit in order to consistently make the latch metastable. When they are at least this large, the ES circuit is robust against variations due to process, voltage and temperature.

We found that real-world data from the ES roughly matches these mathematical predictions. This means that in some cases, either the latch or the feedback circuit is not operating exactly the way that the model supposes. Still, the quality of ES's output is appropriately high, and even our pessimistic measurements on the worst samples are above its design goals.

The health-testing logic is ad-hoc, but it is sufficient to catch any simple patterns that might occur if the ES fails. The output of the ES is sampled down from about 3GHz to 800 MHz before the health tests run, and the sampling might hide some patterns from the health tests. Even so, if the ES's quality slips below its conservative design goal of 0.5 bits of entropy per output bit, then the health tests will almost certainly notice this failure.

The conditioner normally condenses 512 bits of ES output into 256 bits of reseeding data. Since the ES is expected to produce at least half a bit of entropy per output bit, these 256 bits should be almost completely random, but with a very small safety margin. Fortunately, when the RNG first starts, the initial seed is condensed from 32 kilobits of input, giving it a much wider safety margin. This strong seed is carried forward as the RNG runs, so the system remains strong even if it receives no additional entropy.

Finally, the seed is passed to a pseudorandom generator, which generates the RNG's final output. Under normal load, the generator reseeds every time it produces an output, so its output should be almost completely statistically random. Under very heavy load, it can generate multiple blocks of output between reseeds. In this case, the generator has 256 bits of state, and finding patterns in it is as hard as breaking 128-bit AES.

Conclusion

Intel's new RNG simplifies and improves cryptographic random number generation on servers and embedded platforms, where it is otherwise a challenge. It is carefully and conservatively engineered, and Cryptography Research recommends its use without reservation. Still, conservative system design will incorporate other sources of entropy if they are available. In all cases, users should confirm that the RDRAND instruction returns a carry flag of 1 to ensure that the RNG is reporting proper operation.

References

C. E. Shannon, "A Mathematical Theory of Communication," Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, 1948.
E. Barker and J. Kelsey, Recommendation for Random Number Generation Using Deterministic Random Bit Generators, NIST Special Publication 800-90A, January 2012.
B. Schneier, Security Pitfalls in Cryptography, Counterpane Systems, 1998.
DSA-1571-1- openssl -- predictable random number generator," Debian, 13 May 2008. [Accessed 1 February 2012].
A. K. Lenstra, J. P. Hughes, M. Augier, J. W. Bos, T. Kleinjung and C. Wachter, "Ron was wrong, Whit is right," IACR eprint archive, vol. 064, 2012.
D. Bleichenbacher, On the generation of one-time keys in DL signature schemes, IEEE P1363 Working Group Meeting, November 2000.
D. J. Johnston, "Mircoarchitecture Specification (MAS) for PP-DRNG," Intel Corporation (unpublished), V1.4, 2009.
C. E. Dike, "3 Gbps Binary RNG Entropy Source," Intel Corporation (unpublished), 2011.
C. E. Dike and S. Gueron, "Digital Symmetric Random Number Generator Mathematics," Intel Corporation (unpublished), 2009.
M. Dworkin, "Recommendation for Block Cipher Modes of Operation: The CCM Mode for Authentication and Confidentiality," NIST Special Publication 800-38C, May 2004.
Z. Rached, F. Alajaji and L. Campbell, "Rényi's Entropy Rate For Discrete Markov Sources," 1999.
NIST, "NIST Special Publication 800-22rev1a," 11 August 2010. [Accessed 2 February 2012].
M. Hamburg, P. Kocher. M. Marson, Analysis of Intel's Ivy Bridge Digital Random Number Generator