Random Numbers, Linux’s Way

The primary contributors to randomness on Linux are the input devices (the keyboard and the mouse), the storage disk and the interrupts that occur while runtime. All of the information coming in from these sources is mixed up and added to the entropy pool, which is typically 4096 bits wide. The amount of available entropy can be found at `/proc/sys/kernel/random/entropy_avail`, which noticeably increases upon casually using the machine for some time, or even just moving the mouse around. Crudely, when an event occurs, it’s timestamp is paired with the device ID that caused this event, and this word is XOR-ed with the previous bits from the pool, and the so obtained word is added to the pool. This happens at `drivers/char/random.c`.

This isn’t so!

Linux provides two interfaces to the users to access entropy: /dev/random (blocking) and /dev/urandom (non-blocking). `/dev/random` is suited to high quality randomness needs, but when the available entropy goes down below a certain threshold,, it blocks until more entropy is gathered, i.e. it waits for more casual user activity and disk events. This can cause large setbacks if the machine is supposed to provide a crucial service to its users (like an HTTPS server that needs to serve private keys to tons of users connected to it).

`/dev/urandom` does not block. If the system is running low on entropy, it still keeps hashing the data from the entropy pool. This makes it less secure and unsuitable for generating SSH/SSL/GPG keys.

Every time a random number is generated, the kernel lowers it’s estimate of available entropy. From the random’s manpage,

[Linux’s PRNG] is designed for security, not speed, and is poorly suited to generating large amounts of random data. Users should be very economical in the amount of seed material that they read from /dev/urandom (and /dev/random); unnecessarily reading large quantities of data from this device will have a negative impact on other users of the device.

Servers are often headless machines–they don’t need a keyboard and a mouse attached to them. They’re operated remotely through ssh connections. This creates a problem: how do they gather reliable entropy? Sure, there are disk events and network events happening, but still, the entropy pool may run out because of the large amount of requests coming in. A solution is to deploy hardware random number generators. These devices usually gather the environmental noise and add it to the pool. Intel’s Ivy Bridge processors provide the RDRAND instruction that returns random numbers. Yet another way of handling this is the audio_entropyd and video_entropyd daemons, which collect randomness from an audio and video source respectively.

Related Articles:


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