Random Numbers
In a security discussion over at MacInTouch, a reader named Lawerence asked how the random numbers used in encryption could possibly be random:
“How is that possible? Aren’t computers inherently deterministic? I suppose if you scanned in a blob of dust you could in theory generate a truly random number from that…”
There’s an old cryptography joke: Random numbers are too important to be left to chance.
It is extremely difficult to create a truly random number, but on a practical level we can. A good enough random number is one which cannot be predicted by another tool with a rate of success more than chance. That’s a much lower bar to hit than the unachievable ideal of random.
My son was an excellent source of high-entropy input
Numbers you can touch
Lawrence was onto something with the blob of dust idea. About 20 years ago Silicon Graphics (remember them?) had a Lava Lamp-based random number generator. It even had its own Lavarand.sgi.com website — sadly, only the Wayback Machine has it now. A good explanation of how it works has been copied Lava Lamp RNG.md. (There is an open source project that re-creates the functionality, LavaRnd, if you want to have a bit of fun with it.)
The Lava Lamp RNG is an example of one of the two major kinds of random number generation methods: Physical random number generation.
Physical RNG uses an unpredictable natural source of entropy, such as atmospheric noise, thermal noise, cosmic radiation or radioactive decay, as an input to create a random number.
For example, Linux’s /dev/random device uses environmental noise from device drivers to create its entropy pool. The source code comments by Linus Torvalds describe the challenge and Linux’s approach. Here’s an excerpt from his introduction:
Computers are very predictable devices. Hence it is extremely hard to produce truly random numbers on a computer — as opposed to pseudo-random numbers, which can easily generated by using a algorithm. Unfortunately, it is very easy for attackers to guess the sequence of pseudo-random number generators, and for some applications this is not acceptable. So instead, we must try to gather “environmental noise” from the computer’s environment, which must be hard for outside attackers to observe, and use that to generate random numbers. In a Unix environment, this is best done from inside the kernel. Sources of randomness from the environment include inter-keyboard timings, inter-interrupt timings from some interrupts, and other events which are both (a) non-deterministic and (b) hard for an outside observer to measure. Randomness from these sources are added to an “entropy pool”, which is mixed using a CRC-like function. This is not cryptographically strong, but it is adequate assuming the randomness is not chosen maliciously, and it is fast enough that the overhead of doing it on every interrupt is very reasonable.
(I’m also fond of random.org’s method: variations in the amplitude of atmospheric radio noise.)
The U.S.S. Make Stuff Up
The second method of getting random numbers is to generate pseudorandom numbers from an algorithm. To steal from Wikipedia’s description, a psuedorandom number generator creates “long sequences of apparently random results, which are in fact completely determined by a shorter initial value, known as a seed value”.
Minecraft is a notable example of a system using a pseudorandom number to generate its random worlds. When generating a world, Minecraft starts with a seed number; whatever goes in creates a random world. Normally Minecraft gets its random number from its Java runtime, but you also can provide your own number. If a friend uses the same number you did, the friend will get the exact same “random” world.
Pseudorandom number sound like a horrible idea. In practice, they can be highly secure, even for cryptographic purposes. The trick is to create a seed that can’t be predicted by an adversary.
The Yarrow random number generator is used by Mac OS X and iOS; it’s an open source, un-encumbered algorithm placed into public domain by its creators to improve encryption for everyone. (Go read that link, it’s useful.)
The astute reader will notice that the previous RNG method I described is really just a variation of this one: it just involves getting an unpredictable seed at a high enough rate you can build a pool of entropy to feed into an algorithm.
In computing, you can get all sorts of entropy sources. A Mac or PC has a mouse, keyboard, network ports, and thermal sensors. A mobile phone has motion sensors, light sensors, microphones, and several kinds of radios; if you can’t get a random seed out of that you’re not trying. Servers are more challenged; they don’t have users whose typing speed and mousing varies fractionally but significantly from second to second, or any of the many sensors a phone might use. Pretty much the only sensors a server has are the thermometers on its CPUs, RAM and drives, and its network ports. Harder to keep that entropy pool full.
Intel added a very good hardware RNG to its chips in 2011’s IvyBridge update. Electronic Design has a very good article about it, Understanding Intel’s Ivy Bridge Random Number Generator; also helpful is an IEEE article by the designers at Intel, Behind Intel’s New Random-Number Generator.
In a nutshell, it uses noise from a thermal source source to seriously perturb some transistors. This generates about 3 billion random 0’s and 1’s per second, and then Intel makes the bits jump through well-designed hoops. It’s a pretty darned source of entropy, especially if you combine it with noise from other sources.
(Intel first added hardware RNGs in 1999, but they were power-hungry analog components of an otherwise digital chip, which posed manufacturing headaches.)
Good enough is enough
This brings us full circle: We have ways to generate numbers that cannot be predicted by another tool with a rate of success better than chance. They’re random enough. Presuming the encryption algorithm is good, we’re reasonably confident we can feed it good random numbers and get a secure output.
Evidence it’s good enough: These computer-generated random numbers have the FBI sufficiently stymied they tried to circumvent Congress.
:-D
I originally wrote and published this at medium.com/@rmohns/random-numbers-101-19c98b8a7041