Some Notes on Randomness

Judging the ‘quality’ of random data is indeed a complex statistical problem. The dieharder suite has been designed around this issue, which consists of a number of tests that establish a criteria for an RNG to be good, and fail if it isn’t met. The tests differ significantly from each other; some of these may be easier to pass than the others.

A PRNG needs to be initialized using a ‘seed’, which may be taken from the machine-available sources of entropy (/dev/random, /dev/urandom on Linux). Since it works on deterministic algorithms, for the same seed, the PRNG produces the same results on each run. So, if the seed is compromised, the adversary may be able to predict the sequence produced by the PRNG. Since /dev/random and /dev/urandom are char devices, their concurrent reads from multiple applications will preserve the uniqueness of the data received by each application. This implies that if multiple PRNGs are being initialized at the same time, each of these receives a unique seed.

The OpenSSL PRNG, on Unix-like OSes it seeds itself using data obtained by reading /dev/urandom, /dev/random and /dev/srandom (on OpenBSD), spending 10 ms on each (openssl/crypto/rand/rand_unix.c). For the PRNG to be cryptographically secure, its initial seed must not become known. This, in case of OpenSSL, implies that the external devices it reads from must be reliable sources of randomness.

For machines that lack /dev/random as an option, Entropy Gathering Daemon can be used. It is a perl script which runs in the background, calling the programs available on the machine and using their results to slowly fill its entropy pool (egd.pl:175 – 321). OpenSSL can be configured to use EGD as a source of randomness. A virtual machine running on QEMU can also be fed from EGD but this is slow due to EGD’s way of working and is being investigated. Also, if EGD is not running in the `–bottomless` mode, it often blocks when being used with QEMU. So, it is not advisable to be used as of now.

Another source of randomness could be the hardware random number generators. These claim to be cryptographically secure and unpredictable, and are often very fast. But these are only as reliable as their manufacturer. Certain Intel processors provide an instruction that they claim returns reliable random numbers. But a recent revelation indicates that this instruction may have been rigged because of influence from the NSA. Therefore, depending on an HWRNG as the only source of randomness would be a bad idea. A better option is to just add this data to the main entropy pool along with data from other sources.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s