Most cryptosystems rely on access to true random data. For public key schemes like RSA, you need to generate two random primes to generate your keys. For symmetric schemes, your key is a large random number. As well, for various block cipher modes, you will need random IVs (CBC) and nonces (CTR). For Diffie-Hellman and ElGamal, you need to generate large random numbers. These random numbers build up to your shared secret.
Generating random numbers involves a lot more than just using your 'rand(3)' function though. NIST and NSA have written about the nuances of this in a suite of standards, SP 800-90.
Cryptographic vs. Statistical Randomness
Statistical randomness doesn't always deal with hiding how a number is generated. Pseudorandom number generators (PRNGs) fall into this category. When using a function like the C standard library's 'rand()', you're generating pseudorandom numbers. Generally, this function is not designed to resist analysis of its outputs. An attacker could guess the internal state of the PRNG by observing its outputs. Many times the number of observations is tiny: often just hundreds of samples.
Knowing the internal state at any point would make it possible to guess the outputs. This is not suitable for cryptographic purposes.
Cryptographic random numbers are special. An attacker should not be able to guess a random number by knowing how you generated the number. So, to avoid the problems of statistical PRNGs, you need to be a bit clever.
Real Entropy
Finding entropy that is suitable for cryptographic use is a science on its own. Most entropy sources rely on measuring some sort of random physical phenomenon. There's a good chance that an entropy source in an embedded device is measuring thermal noise. This usually involves indirect measurement, something like:
- variability in silicon clock domain crossings,
- PLL lock jitter,
- mixing outputs from free-running oscillators,
- transistor avalanche noise or zener diode breakdown noise.
Acoustic noise, radioactive isotope decay and background radio noise are all used, too. Most of the time these need special hardware and equipment. As such, people will generally skip them.
All these sources have limited throughput on their own. For a good quality TRNG you might only get a few thousand bits per second after whitening the output. That amount of entropy would slow down generating and testing p and q values for a new RSA key. As well there can be a certain amount of determinism to the ouputs from the RNG. We need to make these numbers more random before we can use them.
Stretch Your Entropy Further
Cryptographic PRNGs, called Deterministic Random Bit Generators (DRBGs) in NIST terminology, will let you stretch your entropy further. DRBGs rely on common cryptographic primitives. For example, CTR-DRBG uses a block cipher in CTR mode, oftentimes AES. Some DRBGs rely on HMAC or hashing a particular set of inputs.
For CTR-DRBG, entropy seeds the counter and the nonce for a block cipher in CTR mode. The DRBG generates its output by encrypting a random input. The CTR-DRBG finally mixes part of its output with its key. The remaining output is a usable pseudorandom number. Repeat this until you have all the bytes you need.
The security proof follows from the security proof for your block cipher and CTR mode. The output from the AES block cipher should be indistinguishable from random data. With CTR, the counter gets incremented by 1 for every iteration. As such, each block of CTR-DRBG output should differ from any other block. If it didn't, this would mean CTR mode is insecure. Thus, because of these properties, we can be sure that our DRBG outputs are random enough.
One final detail about DRBGs: you must mix entropy in to the DRBG every so often. This makes the internal state of the DRBG even harder to guess.
NIST provides in-depth guidelines on how to build and use DRBGs in SP 800-90A Rev. 1. Don't try this at home though.
Embedded Systems
Many embedded systems provide some form of symmetric crypto acceleration. For example, embedded Intel Atom and and AMD Jaguar/Puma cores both provide AES-NI instructions. Cavium Octeon CPUs have a similar set of coprocessor instructions. Many other CPUs provide acceleration through external AES engines. For example:
- Marvell 88MC200 and Kirkwood SoCs
- Broadcom BCM58xx Secure Applications Processors
- VIA x86 CPUs (PadLock)
- Maxim Semiconductor MCUs like the MAX32631
all provide accelerator-based AES acceleration. But, using these for a DRBG can be costly. Encrypting a single block might incur interrupts in the worst case. You can use many of these devices in poll mode, which might decrease some pain. Setup cost for some of these AES engines can be high. Whether to use these to serve your DRBG needs has to be a careful engineering decision.
The good news is that many devices also provide hardware accelerated DRBGs. The bad news is that there's no way you, as the end user, can guarantee there are no back doors in these features. After the debacle with Dual_EC_DRBG and the revelations of the NSA BULLRUN project, cryptographers are right to be dubious, too.
We'll talk more about entropy, DRBGs and other such things in future blog posts. These are the key building blocks to a good cryptographic system. But like anything in the world of cryptography, the devil is in the details. If you have a TRNG and need a DRBG, I highly recommend looking at what mbedTLS offers for your DRBG needs.