Random Number Generator – That’s No Bull

Aside from Bull Mountain being a geographical point in the US (there is actually more than one place called Bull Mountain, by the way), it is the "Code Name" for Intel's latest innovation in the generation of super-robust Random Numbers. It is based on the RdRand instruction that is new on the next generation platform (not yet launched.) 

One might ask.. "Why all the excitement over an instruction on a platform that we don't have access to yet?"  Well, it's darn exciting and important technology, that's why (as in the title of this blog.)  Seriously though, even if most of us don't have access to the hardware in order to test out its awesomeness we have tons of resources to aid in the implementation and basic testing of it.  Read on.

The Bull Mountain Software Implementation Guide was recently made available on the Manageability and Security Community.  Oddly enough, however, this is not the first time we have revealed what it is and how to implement it.  It has been documented in the Intel® AVX web page under section 8.6 for quite a long time and it is also referenced in the Intel® 64 and IA-32 Architectures Software Developer’s Manual.  Don't have hardware yet to test your implementation?  Don't worry, there is a Software Developer Emulator that supports the RdRand instruction out there on our "Whatif" website.  Note, that through emulation, you will NOT be able to test actual results and performance - that must be done on actual hardware.  Lastly, we've all heard about Red Hat, Black Hats, and White Hats, right?  How about Dead Hats?  You can learn about 802.11i and 802.16e cryptography stuff here - oh and it has an online Polynomial Divider.  Well that was a little random, wasn't it?

Two days ago I ran across another blog out on the Internet regarding Bull Mountain, and the writer referred to it as a "True Random Number Generator."  Well, unfortunately, as well intentioned as this person was, Bull Mountain is NOT a True Random Number Generator.  I guess he didn't really read the Implementation Guide that he was blogging about.  No worries.  Let's discuss now, what Bull Mountain is.

First, let's cover, briefly, what a Random Number Generator (RNG) is.  It is a utility or device that produces a sequence of numbers on an interval such that values appear unpredictable (hopefully!)  Each value must be statistically independent of the previous value, the overall distribution of  number chosen from the interval are uniformly distributed and the sequence is unpredictable.  Additionally, we would like the RNG to be fast in returning a value and it should be highly scalable (it should produce a large number of requests within a short time interval.)  It should also be secure against attackers who might observe or change its underlying state in order to predict or influence its output or interfere with its operation.

With respect to the taxonomy of Random Number Generators, here are a few of the different types:

1. Pseudo-Random Number Generators (PRNGs):  uses a deterministic algorithm, typically implemented in software, computes a sequence of numbers that "look" random.  They require a seed and the same PRNG will always produce the exact same sequence of "random" numbers.  Not really so random, right?  PRNGs are largely considered to be cryptographically insecure - this is a problem that researchers have worked on to solve by creating "Cryptographically Secure PRNGS" (CSPRNGS). 
2. True Random Number Generators (TRNGs):  Does not use a mathematical model to deterministically generate numbers that "look" random.  Rather, TRNGs extract "randomness" (entropy) from a physical source of some type and then uses that to generate random numbers.  The physical source of entropy might be key strokes or mouse movements, for example.  The key challenge for TRNG designers is to find a reliable source for entropy as the resulting value sequences generally fail to meet desired statistical properties with rigor.  It's good that TRNGs use non-deterministic methods; however they have other shortfalls.
3. Cascade Construction RNGs:  Used in modern operating systems such as Linux and cryptographic libraries, takes input from an entropy source in order to supply a buffer or pool of entropy.  The entropy pool is then used to provide nondeterministic random numbers that periodically seed a cryptographically secure PRNG (CSPRNG).  This CSPRNG provides cryptographically secure random numbers that appear truly random and exhibit a well-defined level of computational attack resistance.  One key advantage here is performance.  Sampling entropy sources can be slow since it often involves device IO of some type and some time for a real-time sampling event to occur.  CSPRNGs are fast since they are processor-based and avoid IO and entropy source delays.

Finally, what IS Bull Mountain, the technology??

Mostly, Bull Mountain follows the Cascade Construction RNG model, using a processor resident entropy source to repeatedly seed a hardware-implemented CSPRNG.  Unlike software approaches, it includes a high-quality entropy source implementation which can be sampled quickly to repeatedly seed the CSPRNG with high quality entropy. It represents a self-contained hardware module that is isolated from software attacks on its internal state resulting in a solution that achieves Random Number Generation objectives with considerable robustness: Statistical quality, highly unpredictable random number sequences, high performance, protection against attacks.

The Digital Random Number Generator (DRNG) is unique in its approach in that it is implemented in hardware on the processor chip itself and is available to software running at all privilege levels (even to VMs!!)

Bull Mountain also  leverages a variety of cryptographic standards to ensure the robustness of its implementation and to provide transparency in its manner of operation.  These include NIST SP800-90, FIPS-140-2, and ANSI X9.82. 

About the RdRand Instruction

1. Retrieves a hardware generated random value from the DRNG and stores it in the destination register given as an argument to the instruction.  The size of the random value (16-,32-, or 64-bits) is determined by the size of the register given. 
2. The Carry Flag (CF) must be checked to determine whether a random value was available at the time of the instruction execution.
3. There are no hardware ring requirements.
4. Determine programmatically whether a given Intel platform supports RdRand, use the CPUID instruction to examine bit 30 of the ECX register.  A value of 1 indicates that the processor supports the RdRand instruction.
5. For code examples, refer to the Bull Mountain Implementation Guide.  The Implementation guide has many coding examples on how you would "roll your own" implementation, should you wish to.  Eventually you should be able to implement it via a function call from your favorite Cryptographic Library.

Well this is all for now!  I hope you are as excited about this this new capability as we are!

Please feel free to contact us through our Manageability & Security Community forum in regard to this post.