QuintessenceLabs just released our latest product qRand, which uses our quantum random numbers to feed the entropy pool of a Linux system. This product is very important especially on virtual machines and this blog post explores some real-world examples why this matters.

What does this mean and why does it matter?

Random numbers are incredibly vital to every operating system. They are used everywhere. Even a simple task like starting a program uses random numbers (ASLR) and obviously every cryptographic operation (such as SSL/TLS encryption, SSH or PKI) relies fundamentally on random numbers.

As every program on a computer is completely deterministic, how can you generate random numbers? Well, that’s where the entropy pool comes in. Every operating system (we’ll focus on Linux here) maintains a pool of really high entropy random bits. This pool is fed from random sources like your mouse movement, and the kernel makes sure that these random bits are really random (entropy is high). The pool has space for 4096 random bits with the highest entropy possible.

Entropy matters a lot: if you were to generate a 2048 bit long private key from an entropy pool that only has 20 bits, your 2048 bit private key may be 2048 bits long, but would be “only as good” as a 20 bit key.

Coming back to the entropy pool in Linux… The kernel maintains that pool: and if you draw random bits from it, the entropy goes down, but if the operating system finds good random events (such as mouse movements, …) the pool gets filled up and the entropy level goes up.

You can see for yourself the entropy level in Linux with the command “cat /proc/sys/kernel/random/entropy_avail”, which gives you a number (in bits) how much estimated entropy is in the pool.

When an application needs random numbers (such as for generating a private key, initiating an SSL/TLS connection, …) it has two options:

• It can read from /dev/random

o Reading from /dev/random gives you directly data from the entropy pool, which is really high entropy random data, but the problem is that once this entropy pool is empty, there is nothing the system can give you anymore and therefore it will “block” and not return any data until it finds more data.
o This means in practice that the application that needs random data will wait potentially forever and look like it hangs

• It can read from /dev/urandom

o Reading from /dev/urandom will never block as /dev/urandom will use a deterministic random number generator that is seeded from the entropy pool, but it doesn’t need the entropy pool to produce then good random numbers afterwards.
o Different Linux versions use different algorithms how to produce the random numbers.

So, applications that do not want to use this “simple” deterministic random number generator from the Linux kernel have to rely on /dev/random, but as you’ve seen above: once the entropy pool is empty there won’t be any more random data, resulting in performance issues.

This is exactly the problem that qRand solves. It constantly monitors the amount of entropy in the entropy pool, and adds true quantum generated random numbers (based on a quantum physics effect called ‘quantum tunneling’) when needed, to make sure that you don’t have to rely on the output of a system you don’t trust.  With qRand you can be assured you get the best possible random numbers that can be produced.

Who needs this?

As we’ve seen above, the entropy pool gets filled by the operating system from “random” sources such as mouse movements. When that runs out, it either blocks, or uses deterministic approaches to generate random bits, with lower entropy. There are many situations where the entropy is hard to be filled by the operating system. Especially on virtual machines, this is a big problem as you don’t have a monitor or a keyboard or a mouse and no environmental interface to draw randomness from.

If you don’t want to rely on these sources of randomness, and want to avoid the performance issues of blocking, you can now instead use entropy generated from a true quantum source. This is exactly what qRand provides.

Practical tests: is this problem real?

Well, to answer that question, we can do a quick experiment: fire up a virtual machine from Amazon EC2 and see what the entropy pool does.

We worked with an Ubuntu Linux instance T2.micro in us-west-2a and obtained the following entropy level (measured in bits) profile over time:

Remember, the entropy pool can hold 4096 random bits, and it is generally accepted that you are in trouble if entropy_avail values are below 300-400… In our experiment the entropy level on the virtual machine started around 200 and then constantly bounced between 0 and 150. Wow… nothing was happening on this system.

In spite of this, the system appeared to be running fine. As a next step, we tried to read some random bytes from /dev/random, but this immediately blocked and just kept running forever. You can see when we requested the random numbers below (when the entropy_avail dropped to between – and 60).

From this moment entropy_avail varied between 0 and 60, even though /dev/random didn’t actually return any random bytes!

After almost 8h, we decided to put the system out of its misery and fired up qRand. My request for random bytes was then completed immediately.

ubuntu@ip-172-31-41-147:~$ dd if=/dev/random of=rand bs=1K count=2 iflag=fullblock
2+0 records in
2+0 records out
2048 bytes (2.0 kB, 2.0 KiB) copied, 27620.7 s, 0.0 kB/s

As you can see , the full operation took almost 8h (27620 sec). But it only actually succeeded once we started qRand – and at that time it ran almost instantly.

We then re-did this experiment with qRand running from the start:

ubuntu@ip-172-31-41-147:~$ dd if=/dev/random of=rand bs=1K count=2 iflag=fullblock
2+0 records in
2+0 records out
2048 bytes (2.0 kB, 2.0 KiB) copied, 0.0317628 s, 64.5 kB/s
ubuntu@ip-172-31-41-147:~$

The operation was completed in 0.031 sec, and the chart below shows that the value of entropy_avail that the system reports as this is now nicely filled up and always stays above 3000 (this was the threshold we set for qRand).

So now we have a virtual machine that will behave beautifully and can always produce high quality high-entropy random numbers from /dev/random at any time.

Problem solved – thanks to qRand. You can find out more if you are interested here.  In the meantime, I’d love to hear your own experiences with entropy performance and blocking.

Andreas Baumhof, Vice President of Quantum Technologies