Tuesday, May 22, 2012

A wide view of the Intel Digital Random Number Generator (DRNG)

Let's focus on two important lessons security history has taught us over the years:
  • Cryptography relies heavily on random numbers
  • Implementing cryptography in the right way is not easy
To point out and stress these concepts, I would like to recall a significant episode... Do you remember Debian/OpenSSL Fiasco in 2008? Briefly, due to some modifications to the code, as a side effect, the only "random" value that was used in the PRNG was the current process ID.

This resulted in the PRNG having only 32,767 different possible seed values (i.e. the default maximum process ID in Linux systems), that means... a lot of people using the same keys to perform sensitive operations! Or... in other words, as a famous quote by Robert Coveyou says: "random number generation is too important to be left to chance".

So, wouldn't it be nice if we could rely on a high quality standard implementation, that is also performing, reliable under worst case assumptions and secure against software attacks? Yes, of course. Is it possible? Well, lucky day... yes, it is!

The news is quite recent and comes from Intel, who developed a Digital Random Number Generator (DRNG) following the Cascade Construction RNG model (however this isn't Intel's first attempt to provide RNG). 



The input is taken from an entropy source in order to supply an entropy pool. This pool is then used to provide nondeterministic random numbers that repeatedly seed a Cryptographically Secure PRNG (CSPRNG). Finally, the CSPRNG generates cryptographically secure random numbers.

Intel's DRNG is implemented in hardware on the processor itself, so the entropy source is built-in and is, indeed, a reliable source of high-quality entropy.

The implementation consists of three logical components that correspond to the ones described above, except for the entropy pool that is replaced by a conditioner to improve the performances.

   
      
Here is how it is structured: 

  • The entropy source uses thermal noise over the silicon in order to generate streams of random bits, which are then fed to an AES-CBC-MAC based conditioner.  
  • The conditioner combines pairs of blocks of 256 bit from the entropy source and produces one block of 256 bit that will seed the AES-CTR based Deterministic Random Bit Generator (DRBG), that is the hardware CSPRNG.  
  • The DRBG provides a wider number of random bytes available from the hardware module: it generates long streams of bytes from the seed, thus improving the final number of random bytes being produced.

Note that the employment of block ciphers in this contest is not a novelty and it is a common approach in PRNG construction, as modern block ciphers are designed to perform good pseudo-random permutations.
Also, the hardware approach adopted by Intel gives additional advantages as the self-contained hardware module is isolated from software attacks on its internal state. 
   
How does a user interface to DRNG? A new Intel 64 instruction is introduced: RDRAND. Intel documentation provides all the necessary details to its usage, and also to determine whether the underlying platform supports the instruction (this can be done using the CPUID instruction).
   
Basically, RDRAND can be invoked to obtain a 16-, 32-, or 64-bit random integer value. For example, "RDRAND eax" stores a 32-bit random number in eax.
After calling it, the carry flag will either be 1 if a random value was available at the time the RDRAND instruction was executed, or 0 if it wasn't.
   
It seems that Intel is spending a lot of effort in providing crypto dedicated instructions (remember the AES instructions set?) and I hope this trend will bring us many other ones. I think that it will take some years to see this implementation spreading around and become popular, but I also think this may be the solution to many practical problems in everyday cryptography: good work, Intel!


4 comments:

  1. Nice post on RdRand! I've been studying the new Intel RdRand instruction for a while, especially the crypto-related aspects. Here's a web page with some (very!) preliminary information https://sites.google.com/site/intelrdrand/
    Any comments or criticism on that web page would be greatly appreciated!
    Intel staff have stated that there's an independent external review being conducted which will be published "soon" and will have more details of cryptographic relevance. I'm definitely looking forward to seeing that.
    Cheers, Patrick O'Keefe

    ReplyDelete
  2. Thank you, Patrick! Your webpage is a really good idea and I found the introduction to be very clear and readable. I also liked the references (I missed many of them!) and the glossary, that is useful to understand the background around the topic :) Great news by the way, I will look forward too!
    Giulia

    ReplyDelete
  3. That review is this one.. http://www.cryptography.com/public/pdf/Intel_TRNG_Report_20120312.pdf

    ReplyDelete
  4. Good news indeed :) I'm glad to see that the design is very robust. Thank you for sharing!

    ReplyDelete