Entropy

From BitFolk
Jump to navigation Jump to search

A brief explanation of entropy as it relates to computing

Where we say entropy, we could in layman's terms say “randomness”. Computers need entropy for a lot of things, particularly cryptographic operations.

Crypto

You may not think that you do a lot of cryptography on your computer, and you personally probably don't, but for example every time you visit a secure web site (https://…) your computer has to set up a cryptographic channel with the server.

Cryptographic algorithms generally require a lot of random data and it has to be secure random data. For the purposes of this discussion, “secure” means that an attacker shouldn't be able to guess or influence what the random data is.

Why would an attacker be able to guess or influence the random data if it is actually random? Because it's not actually random. The computer has to get the data from somewhere.

Psuedo-random number generators

A lot of places it might be programmed to get it from may seem random but potentially aren't. A silly implementation might just use the number of seconds the computer has been running as a basis for generating “random” numbers, but you can see that an attacker can guess this and may even be able to influence it, which could weaken any cryptographic algorithm that uses the “random” data.

Modern computers and operating systems generate entropy based on events like electrical noise, timings of data coming into the computer over the network, what's going on with the disks, etc. fed into algorithms — what we call pseudo-random number generators (PRNGs). A lot of data goes in and a relatively small amount of entropy comes out, but it's entropy you should be able to trust.

Entropy and virtual servers

That works reasonably well for conventional computers and servers, but it doesn't work so well for virtual servers. Virtual servers are running in an emulated environment, with very little access to “real” hardware. The random data that conventional computers get from their hardware doesn't happen with emulated virtual hardware, so the prime source of entropy just isn't present.

When you have an application that wants some entropy and the system has no more entropy to give, what usually happens is that the application blocks, doing nothing, until the system can supply some more entropy.

Where Linux gets its entropy

Linux systems have two ways for applications to request entropy: there’s /dev/random and /dev/urandom. random is the high-quality one. When it runs out, it blocks until there is more available. urandom will supply high-quality entropy until it runs out, then it will generate more programmatically using the kernel's PRNG. It doesn't block, but it might not be as secure as random.

We're vastly simplifying how these interfaces work, but that's the basic gist of it.

Are you starved of entropy?

Whether or not your VPS is starved of entropy will depend strongly on how much demand for entropy you're placing on it. Running busy HTTPS sites or exchanging a lot of email over Transport Layer Security will certainly require more entropy. If your pool of entropy runs out, these applications typically block until more is available. In extreme cases this has been seen to lead to application-level timeouts, e.g. being unable to send email.

How much entropy do you have anyway?

You can have a look at how much entropy is currently available like so: 

$ cat /proc/sys/kernel/random/entropy_avail
3589

This value is in bits, and tops out at 4096. It is not hard to plug this into your monitoring system. You could do something like this to watch it on the terminal for a while: 

$ watch -n 1 cat /proc/sys/kernel/random/entropy_avail

Note that creating a process on Linux requires some amount of entropy, so if you put a command like this in a tight loop you may deplete your entropy pool just by reading it! The following Python code watches the available entry from a single process so doesn't deplete entropy and gives a more realistic picture: 

#!/usr/bin/env python

import time

while True:
    with open('/proc/sys/kernel/random/entropy_avail', 'r') as f:
        print(f.read().rstrip())
    time.sleep(1.0)


What to do if you're regularly running out of entropy?

If you’re running applications that want a lot of high-quality entropy, and your system keeps running out, there’s a few things you could do about it.

Nothing

Maybe you don't care if some crypto-using process has to block for a few seconds occasionally.

Switch to real hardware

You could stop using virtual servers and rent or buy real hardware. Even if it doesn't come with a built-in random number generator, it should be receiving enough hardware interrupts to keep Linux happy.

Tell the software to use urandom instead

In a lot of cases it’s possible to tell the applications to use /dev/urandom instead. Since urandom doesn’t block, but instead generates more lower-quality entropy on demand, there shouldn’t be a performance problem.

There are obvious downsides to this:

  • If the application author wanted high-quality entropy, it might be unwise to not respect that.
  • Altering this may not be as simple as changing its configuration. You might find yourself having to recompile the software, which is a lot of extra work.

You could force this system-wide by replacing your /dev/random with /dev/urandom, for example by symlinking them together.

Wait for virtualisation software to correctly provide entropy to guests

The real fix is for virtualisation software to provide entropy to guests from the real host, in the same way they provide all other hardware like disks, network, timers, etc. Unfortunately at the moment no software appears to do this.

Get some entropy from somewhere else

Using software like rngd it is possible to read data from a pipe and feed it into your /dev/random, so if you have access to a good source of entropy, you can distribute it around.

Some good sources of entropy:

  • A sound card listening to electro-magnetic interference (“static”).
  • A web camera watching a lava lamp.
  • A web camera in a dark box, so it just sees noise on its CCD.

That sounds like a massive hassle doesn't it?

Make use of BitFolk's entropy service

BitFolk provides a networked source of entropy in order to solve this problem for customers who feel they don't have enough high-quality entropy available. This is just a variant of the previous "get some entropy from somewhere else" solution, provided in a simple way. The remainder of this article will focus upon BitFolk's entropy service.

Apparently it is not obvious, and we need to point out that the entropy service is only for the use of BitFolk's customers.

BitFolk's entropy service

How it works

BitFolk has several Simtec Electronics Entropy Keys connected to different hosts.

Entropy Keys are very interesting little gadgets and I encourage you to read about how they work. For the purposes of this article though, the keys are generating entropy from random electron flow, and there's a daemon reading entropy from each key over USB and serving it out on a TCP port.

For remote hosts to make use of the entropy they run a different daemon, ekeyd-egd-linux. ekeyd-egd-linux contacts BitFolk's entropy server, acquires some entropy and feeds it to the kernel of the machine it's running on, to be later served out of /dev/random.

Setting it up

You will need to install ekeyd-egd-linux. On Debian it can be found in the ekeyd-egd-linux package available since lenny-backports, or source is available from Simtec.

On Debian-like systems you will find the configuration in /etc/default/ekeyd-egd-linux, and you will want to change the following items: 

START_EKEYD_EGD_LINUX=YES
HOST=entropy.lon.bitfolk.com
RETRYTIME=30

There is a WATERMARK setting in the file which determines how low the kernel's entropy pool will go before ekeyd-egd-linux will ask the entropy service for more. You should set this as high as you feel you need to, but please do not set it above 4000. The default on Debian is 1024.

Start the daemon and that is it, you're done.

How to tell it's working

A graph of available entropy on a BitFolk virtual machine, showing the point at which use of the entropy service is configured.

To the right is a graph of available entropy on a BitFolk virtual machine. This was done with WATERMARK=4000 to demonstrate the point.

You should find it very difficult to deplete the entropy pool now, whereas before you could probably do so just by using something like: 

$ watch -d 0.25 cat /proc/sys/kernel/random/entropy_avail

Is this entropy good enough?

The entropy keys are designed to test the entropy they're generating and discard it if it isn't of high enough quality. No need to trust that yourself though. You can test your own entropy using a tool like rngtest.

rngtest accepts a data stream on its standard input and tests it against the Federal Information Processing Standards (FIPS) 140-2 U.S. government computer security standards. These specify requirements for cryptography. 

$ rngtest -c 200 -t 10 < /dev/random
rngtest 2-unofficial-mt.13
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: bits received from input: 1460032
rngtest: FIPS 140-2 successes: 73
rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=116.260; avg=142.945; max=164.808)Kibits/s
rngtest: FIPS tests speed: (min=49.413; avg=54.600; max=55.126)Mibits/s
rngtest: Program run time: 10000361 microseconds
rngtest: bits received from input: 2940032
rngtest: FIPS 140-2 successes: 147
rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=114.373; avg=143.186; max=164.808)Kibits/s
rngtest: FIPS tests speed: (min=49.413; avg=54.612; max=55.285)Mibits/s
rngtest: Program run time: 20103900 microseconds
rngtest: bits received from input: 4000032
rngtest: FIPS 140-2 successes: 200
rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=88.812; avg=138.282; max=164.808)Kibits/s
rngtest: FIPS tests speed: (min=44.773; avg=54.569; max=55.446)Mibits/s
rngtest: Program run time: 28319689 microseconds
Warning Warning: Running rngtest will deplete your entropy and will hammer BitFolk's entropy service, so please do not do it too often or for too long!

From the above you can tell a few things:

  • The test was told to run over 200 blocks. Each block is 20,000 bits of data.
  • /dev/random took nearly 30 seconds to supply 200 blocks, keeping up a rate of about 140kibit/s.
  • All 200 blocks passed the FIPS 140-2 tests.

Observe the same tests run on /dev/urandom: 

$ rngtest -c 200 -t 10 < /dev/urandom
rngtest 2-unofficial-mt.13
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: bits received from input: 4000032
rngtest: FIPS 140-2 successes: 200
rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=21.724; avg=41.491; max=45.740)Mibits/s
rngtest: FIPS tests speed: (min=49.158; avg=90.462; max=98.317)Mibits/s
rngtest: Program run time: 134760 microseconds

As you would expect, /dev/urandom is massively faster (~41Mibit/s). It also appears to be just as good. This is misleading though: we only tested 200 blocks, which isn't a very big sample.

Here's 1,000 blocks: 

$ rngtest -c 1000 -t 10 < /dev/urandom
rngtest 2-unofficial-mt.13
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: bits received from input: 20000032
rngtest: FIPS 140-2 successes: 998
rngtest: FIPS 140-2 failures: 2
rngtest: FIPS 140-2(2001-10-10) Monobit: 1
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 1
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=21.949; avg=44.291; max=47.095)Mibits/s
rngtest: FIPS tests speed: (min=54.496; avg=96.286; max=98.826)Mibits/s
rngtest: Program run time: 631376 microseconds

Across 1,000 blocks, urandom on kernel 2.6.32-5-xen-amd64 tends to produce between 0 and 3 failures.

/dev/random (real entropy) across 1,000 blocks: 

$ rngtest -c 1000 < /dev/random
rngtest 2-unofficial-mt.13
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: bits received from input: 20000032
rngtest: FIPS 140-2 successes: 1000
rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=6.404; avg=37.715; max=164.651)Kibits/s
rngtest: FIPS tests speed: (min=28.987; avg=54.162; max=97.314)Mibits/s
rngtest: Program run time: 518242891 microseconds
Even the entropy service can't keep your pool topped up in the face of rngtest.

Zero failures, but it took ages (~518 seconds). The entropy pool was depleted the whole time as well. Don't do this often!

Just in case you were wondering what a really poor source of entropy looks like: 

$ rngtest -c 1000 < /data/Software/OS/Linux/Ubuntu/ubuntu-8.04-rc-desktop-i386.iso
rngtest 2-unofficial-mt.12
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: bits received from input: 20000032
rngtest: FIPS 140-2 successes: 460
rngtest: FIPS 140-2 failures: 540
rngtest: FIPS 140-2(2001-10-10) Monobit: 463
rngtest: FIPS 140-2(2001-10-10) Poker: 469
rngtest: FIPS 140-2(2001-10-10) Runs: 478
rngtest: FIPS 140-2(2001-10-10) Long run: 361
rngtest: FIPS 140-2(2001-10-10) Continuous run: 317
rngtest: input channel speed: (min=1.693; avg=9.122; max=18.626)Gibits/s
rngtest: FIPS tests speed: (min=13.489; avg=83.432; max=250.967)Mibits/s
rngtest: Program run time: 234040 microseconds

Isn't getting my entropy over the network more risky than just using Linux's own PRNG?

Possibly. There are three concerns with acquiring entropy:

  1. Is the entropy source of high enough quality?
  2. Has the supplied entropy been observed by an attacker?
  3. Has the supplied entropy been tampered with by an attacker?

Concern #1 can be mitigated by performing your own quality tests on the supplied entropy as discussed above. The other two concerns aren't so easy to dismiss. An attacker with control of BitFolk's network could easily observe the streams of entropy, and possibly even mount a man-in-the-middle attack to supply you with fake entropy of their own making. Just because it might pass quality tests doesn't mean that it hasn't been pre-generated.

At the moment BitFolk is not providing an easy way around this. There is an argument that an attacker with control of BitFolk's network can already do far more sinister things than observe or tamper with your entropy.

However, should any customer wish to go this far, BitFolk will be prepared to provide access to the entropy service over a stunnel tunnel on a case by case basis. This would provide both encryption and authentication at the expense of much more onerous setup. Please contact support if interested.

Will people down the pub laugh at me for being paranoid enough to use an Entropy Key instead of Linux's PRNG?

Possibly. You need to decide for yourself if using the entropy service is worth it for you.

Some problems with urandom are:

  • Some software developers apparently think it isn't good enough (else why did they hard code /dev/random?). Packages like openssh and gnutls.
  • Some software can't be told to use /dev/urandom.
  • Symlinking random to urandom will affect the whole system.

You may not consider these to be actual problems.

What if BitFolk's entropy key or the host it's on dies?

BitFolk has several entropy keys and the entropy service is load balancing them. You should monitor your own entropy though if it's important to you.

I started using BitFolk's entropy and it caused a total protonic reversal

"There's something very important I forgot to tell you! Don't cross the streams… It would be bad… Try to imagine all life as you know it stopping instantaneously and every molecule in your body exploding at the speed of light."

—Egon Spengler

Sorry to hear. The entropy service comes with no warranty; not even for merchantability or fitness for a particular purpose. You should check that it's doing what you want yourself.

More information

Retrieved from "https://tools.bitfolk.com/w/index.php?title=Entropy&oldid=818"