Random Notes

From Noah.org
Jump to navigationJump to search


Random Notes

This is not a collection of random notes. This is a collection of notes about random numbers.

/dev/random and /dev/urandom

The file /dev/random is the direct interface to the Linux kernel entropy pool and cause reads to block when the entropy pool is empty. The file /dev/urandom is an unblocked interface to the entropy pool. It will reuse the entropy if it runs out. It does blend this through a pseudorandom number generator, so you shouldn't actually see repeated patterns in the numbers; however, these numbers are not considered as random the numbers from /dev/random. This random source may not be as secure for software that depends on random numbers for security.

/dev/random is a limited resource

The device /dev/random is better, but it is "slow" because it depends on a limited resource. It reads directly from the Linux kernel entropy pool to give you truly random numbers. The entropy pool generates truly random numbers by sampling data from the environment such as clock drift and timing of input from device drivers. This sampled data is blended and tested to ensure that it is truly random and without bias. This is an expensive operation, so the kernel constantly maintains a pool (cache) of random numbers which can be read from /dev/random. The problem is that once you have read all the random numbers from the pool further read operations must block until the kernel writes more random numbers into the pool. You see just how slow this is by running the following command:

dd if=/dev/random bs=1 | od -x

You should see a bunch of random hex digits dumped after which `dd` will block and then slowly print new random numbers as the pool gets filled. You may notice that if you move your mouse a lot that new random numbers will be printed more quickly. This shows that the kernel gets some of its environmental input from the mouse device driver.

You can see how many random bytes are in the pool by looking at the file /proc/sys/kernel/random/entropy_avail. If you watch this file (`watch -n 1 cat /proc/sys/kernel/random/entropy_avail`) you may see that the number goes up and down. This is because various services running in the background and even kernel device drivers also read from the entropy pool. In particular, services that use SSL will deplete the entropy pool. If you "waste" the entropy pool by running `dd if=/dev/random bs=1 | od -x` then you may slow down these services because they much block until more entropy is available. Also, if you have many processes running which all use SSL then they may slow each other down. The CPU load will be load, but load average will go up as more processes are forced to block waiting for more entropy.

One way to increase the speed of the supply to the entropy pool is to use a dedicated hardware random number generator. These devices provide a good entropy source much more quickly than what the kernel can obtain from the environment. The Ubuntu package rng-tools can be used to setup and control sources of entropy.

Another way to increase the speed of the supply to the entropy pool is to hack the kernel entropy pool to make it less random (less good). In general, you should not notice the difference, but be aware that you may compromise secure applications such as web services and anything that accepts SSL connections. This doesn't create a huge back door into these applications, but if you are dealing with valuable sensitive data then you shouldn't be playing around with mathematics that you do not understand. In other words, if lives, money, or your job is at stake then get a real hardware random number generator... To hack the kernel entropy pool you must install rng-tools. Then edit /etc/default/rng-tools and edit or insert a line for HRNGDEVICE to the following:

HRNGDEVICE=/dev/urandom

Finally, restart the `rngd` daemon:

sudo service rng-tools restart
 # or
sudo /etc/init.d/rng-tools restart

Doing this basically bypasses /dev/random with data from /dev/urandom. You can now read as much data from /dev/random as you want without blocking. Remember, this is a horrible thing to do. It will make security and statistics nerds go into a rage. I only show this because it is a good learning experience.

testing random numbers for randomness

There are a few Ubuntu packages which provide tools for testing how random your random numbers are, rng-tools and ent. The israndom package was removed from the latest Ubuntu package repositories.

sudo aptitude install ent rng-tools
# sudo aptitude install israndom

A more robust testing tool is `ent`.

dd if=/dev/urandom bs=1 count=1000000 | ent

That will give you some more robust statistical metrics of your random data. Interpreting these values is beyond the scope of this introduction.

The `rngtest` utility will test a given stream against the FIPS 140-2 randomness tests.

cat /dev/urandom | rngtest -b 10000

You can run `israndom` on the /dev/urandom device (the less random source).

israndom /dev/urandom

You may notice that is prints random as the last line. That may seem comforting; however, `israndom` is not a very good tool. It is useful for determining if your random input is good enough for a game, but it is not the best tool to use if you want to test your random numbers for use in security or statistics applications.

More reading

An old analysis of the Linux Random Number Generator (LRNG) written by Gutterman, Pinkas, and Reinman can be found here: http://eprint.iacr.org/2006/086.pdf

A truly random number generator

Most natural sources of random numbers, including radioactive decay, have a non-random bias, which may make the numbers unsuitable for many applications. Sources of natural randomness can be fed into a randomness extractor to remove bias to generate a stream of more mathematically perfect random numbers. A cryptographically secure pseudo-random number generator (CSPRNG) is often used as a randomness extractor. John von Neumann created one of the earliest randomness extractors.

Common sources of natural random numbers include Geiger counters recording the decay of radioactive elements, electronic amplifiers set to amplify thermal noise, cameras recording lava lamps, and the motion of a computer mouse moved by a human. None of these produce good random numbers without a little bit of extra work.

Here I present a very simple and cheap source of natural random numbers. This source requires almost no tools or expertise besides a screw-driver. What I have done is remove the sensor board from a USB mouse and attach it to the side of an Xmas tree bubble light. The bubbles from the light trigger the motion sensor of the mouse, which is fed into a custom Python program I wrote. In principle this is similar to Lava Lamp random number generators; however, the construction is significantly simpler.

Bubble lights consist of a sealed glass vial filled with Methylene chloride. The bottom of the glass vial is placed against a small incandescent light bulb. The heat from the bulb causes the Methylene chloride to boil and bubble. The bubbles float to the top of the vial where the vapor condenses back into liquid. The extremely low vapor pressure of Methylene chloride allows it to maintain a continuous process of boiling and condensation in a very small tube. The heat of a human hand is enough to drive continuous boiling. Other solvents with low vapor pressures would work, but Methylene chloride has the added advantage that it is relatively non-toxic and it is one of the few volatile solvents which is non-flammable, so it is safe to attach the bubble-lights to a tree, as opposed to hanging tubes of boiling gasoline or acetone on your Xmas tree.