Monday, March 12, 2012

Randomness on Your Next Chip?

Generating truly random numbers is actually quite tricky. Intel has announced that its next generation of computer chips, Ivy Bridge will have a new instruction RDRAND which will quickly generate a random number for you right on the processor chip - nice huh. But how random will it be? That may depend on how you want to use the random numbers. One very demanding application is cryptography. Most cryptographic protocols require a very high quality source of random numbers. Is the output generated by Intel's new RDRAND instruction good enough for cryptography purposes? The devil is in the details and the most detailed source of information I could find is this Intel document: Bull Mountain Software Implementation Guide. According to that document the random number is generated in three stages:
1. A Hardware Entropy Source
2. A Conditioner which distills the entropy into high-quality nondeterministic random numbers
3. A deterministic random bit generator which is seeded from the conditioner

The entropy source uses thermal noise within the chip's silicon to output a random stream of 0's and 1's.
The conditioner takes pairs of 256-bit samples from the entropy source and algorithmically combines them into a single 256-bit number which is supposed to be even "more random" than the bits generated by the hardware.
The deterministic random bit generator or DRBG "spreads" that 256-bit conditioned number into as many as 511 128-bit samples.

The DRBG they used is called CTR_DRBG, which defined in section 10.2.1 of the following pdf document from NIST: Recommendation for Random Number Generation Using Deterministic Random Bit Generators. Intel uses the AES block cipher option.

Intel has filed a US patent application, number 20100332574, here's a link to the USPTO page for the application and a link to another patent web site, faq.org which I found a bit easier to use.

The Intel Bull Mountain document has a section titled "Guaranteeing DBRG Reseeding"
Some may furthermore feel it necessary, for standards compliance, to demand an absolute guarantee that values returned by RdRand reflect independent entropy samples within the DRNG
which goes on to list a couple of techniques
to guarantee that the random value returned is based on an entropy sample independent from the prior function invocation, and independent from the subsequent function invocation
which may enable one to circumvent the DRBG.

Here's another skeptical discussion of using RdRand in cryptography: RDRAND and Is it possible to protect against malicious hw accelerators?

Too bad, it might have been nice if the raw hardware entropy source was directly available, so that applications could test and manipulate it directly.

The Schneier on Security blog from September 2011 has extensive comments on the new Intel random number generator.

Intel’s Digital Random Number Generator (DRNG) from some members of the Intel team contains some nice slides explaining the architecture.

Conceptual Foundations of the Ivy Bridge Random Number Generator by Jesse Walker of Intel Labs provides slides discussing some of the theory.

I'm working on a web site dedicated to the Intel RdRand facility, currently there's a glossary and bibliography, I'm also working on an article about using RdRand in cryptography which I will post there.