Random number generators

Bruce Schneier has a new blog post:

It’s about a new research paper on the weaknesses of random number generators such as the one use for “/dev/random” and “/dev/urandom” in linux.  Check Schneier’s post for the abstract of the paper, and a link to the full paper.

Thus far, I have only skimmed the paper, so I won’t be explaining it here.  But I shall use this post to explain why it is important.

LUKS encryption

The main use of random numbers is in cryptography.

I use an encrypted LVM on both my desktop and my laptop.  So everything is encrypted except a small “/boot” partition.  When I boot the computer, I am asked for a passphrase that is used to decrypt the disk (the LVM).

So here’s how that works.  When I first created the encrypted LVM, it was encrypted using a random key obtained from “/dev/random”.  My passphrase, in turn, encrypts the random key and that encrypted random key is in a LUKS header for the partition.

When I boot my computer, software (in the “initrd”) reads the encrypted random key, asks me for my passphrase, and uses that to decrypt that random key.  Once the random key is known, that is use to setup a process that automatically encrypts/decrypts data as it is written to disk and read from disk.  So the random key obtained from “/dev/random” is an important part of the process.

GPG

When I create a new GPG public key, “/dev/random” is used for a source of randomness in generating that key.  So my public key is actually random.  My passphrase for that key is used to encrypt the random key, and the encrypted version is what is saved as my private key in my GPG keyring.  In order to use my private key, I must provide that passphrase to allow the GPG software to decrypt the private key.

When I send an encrypted email, the GPG software uses a random key, which is normally called “the session key.”  The message is encrypted, using symmetric encryption methods, with that session key.  The session key, in turn, is encryped using public key cryptography — it is encrypted with the public key(s) of the recipient(s) of the email.

Secure web connections

When I connect to a secure web site, the communication is encrypted.  The encryption uses a random key generated for just this web connection.  That random key is called “the session key”.  Public key cryptography is briefly used at the beginning of the web session, so that the web site and my browser can agree on the session key to be used.  The public key cryptography uses the key contained in the security certificate (X.509 certificate) from the web site.

SSH

Communication with “ssh” is somewhat similar to secure web connections and to GPG (or PGP), in that it uses a random session key for the actual connection, and uses public key cryptography for server and client to agree on a session key.

The risks of a weak “/dev/random”

Ideally, “/dev/random” will generate completely random and thus unpredictable data.  But let’s suppose, for the moment, that it is not as random as it should be.

The worst possible case is if the output of “/dev/random” is completely predictable.  In that case, an attacker can predict which session keys I am generating, and can monitor any communication using those predictable session keys.

A more likely problem is that the output is not completely random.  So an attacker cannot determine what session key I am using.  But the attacker can narrow down the range of possible session keys.

For 256 bit encryption a completely random key and a robust encryption algorithm, an attacker would need to use trial and error methods.  And that would require testing 2^{256} possible keys.  If the session key is not completely random, the attacker might be able to reduce the possibilities to a far smaller range of likely keys, making it more likely that he can succeed in discovering the session key used.

 

Advertisements

Tags: , ,

About Neil Rickert

Mathematician and computer scientist who dabbles in cognitive science.

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

%d bloggers like this: