How Random is Random Enough For Cryptography?
Source: Paul Dillien
How can one create a random stream of bits suitable for use in encryption and embed this solution in an FPGA?
Random numbers in cryptography are key (pun intended). They can be a weak point in a crypto system and, consequently, are frequently the target of attack. So I've been trying to get my head around the subject of randomness.
I was always taught that thermal noise from a diode junction was random, but now -- it seems -- not random enough. Cryptographers inhabit a twilight world where they are always trying to think up possible attack methods by the bad guys and then figuring out ways to defeat them. And it's a good thing that they do, as most people (me included) rely on secure communications for transactions like on-line banking and shopping. But I digress...
Many of the top gurus of cryptography work at the National Institute of Standards and Technology (NIST). This organization published specifications of how to make an apparently random stream of bits suitable for use in encryption. The solution in its specification SP800-90A is to take the bit stream and encrypt it in a machine called a Deterministic Random Bit Generator (DRBG) to create a Random Number Generator (RNG). That makes sense to me.
First I'll briefly describe the system operation, and then talk about embedding the RNG into an FPGA. At this point, I need to unravel some of the terminology used and try to explain the process.
Any encryption system needs a key and an input data stream, at which point things start to get more complicated. The "more or less random" bit stream that is used to seed the encryption is called the Entropy Input. To ensure that each RNG output is different, the Entropy is combined with an input called Nonce. The Nonce must change or increment for each cycle through the DRBG. Fair enough, as you need to frustrate an attacker who may have collected data from many runs to try to predict what the next output stream will be.
But just in case the Entropy itself has been compromised, there is an option to use a third variable called the Personalization String input. The clever thing is that if this input is derived from, say, a serial number, then it ensures that an attacker monitoring apparently identical machines gets nowhere.
So why stop there? The specification also includes an optional Additional Input. The idea is that this could be derived from a second (independent) source of entropy in a "belt and suspenders" fashion.
My head was hurting by this point, but then I read about the Health Check (which sounds like something from a video game...). A Health Check is initiated either as a routine confirmation that all is well, or because the user suspects that an attacker may have tampered with the RNG. The block isolates all the external inputs to the DRBG and then applies a predefined stimulus to it. The output is verified against a set of Known Answers. Should it fail for any reason, the Health Check outputs a catastrophic error message and locks out the RNG to prevent the output of any compromised bit streams.
Fortunately, it's straightforward to embed an RNG into just about any FPGA. Designers can use an RNG IP Core along with a simple ring oscillator and counter as the source of Entropy (no diode needed!). The usual rules apply to building an encryption system, because the designer must ensure that the sensitive data inside the FPGA cannot be accessed at any pins of the device (think JTAG). Simulating and verifying a circuit that is designed to be random might sound like a nightmare. Thankfully, being fully deterministic, the RNG core ships with a full test bench for verification. The test bench is also important if the final crypto system is to undergo approval at an external test house. I can only imagine the problems of testing a bit stream for the property of randomness.
An FPGA implementation will be all digital, so it will be robust and not succumb to tampering by an attacker who tries to vary the voltage or temperature. The self-oscillation frequency may vary, but that shouldn't affect the quality or randomness of the output bit stream.
One neat aspect of using an IP core with an embedded AES encryption engine is that this circuit block can double up for other jobs in many applications. It can multiplex to provide the encryption and decryption of the data stream and save significant FPGA real estate. Where it's required to transmit encryption keys over an insecure link, another option is to use the AES crypto engine in a keywrap application.
Poor quality random numbers need not be the weakest link in an encryption system, and using a standards-based solution will help designers sleep better at night.
| }
|