Adventures in entropy, part 1

A while back, a couple of BitFolk customers mentioned to me that they were having problems running out of entropy.

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. 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. 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.

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. 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, so it doesn’t block, but it might not be as secure as random. I’m vastly simplifying how these interfaces work, but that’s the basic gist of it.

What to do when there’s no more 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 ^

So stuff slows down, who cares? It’s only applications that want high-quality entropy and they’re pretty specialised, right?

Well, no, not really. If you’re running a busy site with a lot of HTTPS connections then you probably don’t want it to be waiting around for more entropy when it could be serving your users. Another one that tends to use all the entropy is secure email – mail servers talking to each other using Transport Layer Security so the email is encrypted on the wire.

Use real hosting hardware ^

Most of BitFolk’s customers are using it for personal hosting, this problem is common to virtual hosting platforms (it’s not a BitFolk-specific issue), and BitFolk doesn’t provide dedicated/colo servers, so arguably I don’t need to consider this my problem to fix. If the customer could justify greater expense then they could move to a dedicated server or colo provider to host their stuff.

Tell the software to use urandom instead ^

In a lot of cases it’s possible to tell the applications to use 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.

Customers could get some more entropy from somewhere else ^

It’s possible to feed your own data into your system’s pseudo-random number generator, so if you have a good source of entropy you can help yourself. People have used some weird and wonderful things for entropy sources. Some examples:

  • 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.

The problem for BitFolk customers of course is that all they have is a virtual server. They can’t attach web cams and sound cards to their servers! If they had real servers then they probably wouldn’t be having this issue at all.

BitFolk could get some entropy from somewhere else, and serve it to customers ^

BitFolk has the real servers, so I could do the above to get some extra entropy. I might not even need extra entropy; I could just serve the entropy that the real machines have. If it wasn’t for the existence of the Simtec Electronics Entropy Key then that’s probably what I’d be trying.

I haven’t got time to be playing about with sound cards listening to static, webcams in boxes and things like that, but buying a relatively cheap little gadget is well within the limit of things I’m prepared to risk wasting money on. 🙂

Customers would need to trust my entropy, of course. They already need to trust a lot of other things that I do though.

Entropy Key ^

Entropy Keys are very interesting little gadgets and I encourage you to read about how they work. It’s all a bit beyond me though, so for the purposes of this series of blog posts I’ll just take it as read that you plug in an Entropy Key into a USB port, run ekeyd and it feeds high quality entropy into your PRNG.

I’d been watching the development of the Entropy Key with interest. When they were offered for cheap at the Debian-UK BBQ in 2009 I was sorely tempted, but I knew I wasn’t going to be able to attend, so I left it.

Then earlier this year, James at Jump happened to mention that he was doing a bulk order (I assume to fix this same issue for his own VPS customers) if anyone wanted in. Between the Debian BBQ and then I’d had a few more complaints about people running out of entropy so at ~£30 each I was thinking it was definitely worth exploring with one of them; perhaps buy more if it works.

How much entropy do I have anyway? ^

Before stuffing more entropy in to my systems, I was curious how much I had available anyway. On Linux you can check this by looking at /proc/sys/kernel/random/entropy_avail. I think this value is in bytes, and tops out at 4096. Not hard to plug this in to your graphing system.

Click on the following images to see the full-size versions.

Typical host server, no Entropy Key ^

Here’s what some typical BitFolk VM hosting servers have in terms of available entropy.

barbar.bitfolk.com available entropy, daily

That’s pretty good. The available entropy hovers close to 4096 bytes all the time. It’s what you’d expect from a typical piece of computer hardware. The weekly view shows the small jitter:

barbar.bitfolk.com available entropy, weekly

The lighter pink area is the highest 5-minute reading in each 30 minute sample. The dark line is the lowest 5-minute reading. You can see that there is a small amount of jitter where the available entropy fluctuates between about 3250 and 4096 bytes.

Here’s a couple of the other host servers just to see the pattern:

corona.bitfolk.com available entropy, daily

corona.bitfolk.com available entropy, weekly

faustino.bitfolk.com available entropy, daily

faustino.bitfolk.com available entropy, weekly

No surprises here; they’re all much the same. If these were the only machines I was using then I’d probably decide that I have enough entropy.

Typical general purpose Xen-based paravirtualised virtual machine ^

Here’s a typical general purpose BitFolk VPS. It’s doing some crypto stuff, but there’s a good mix of every type of workload here.

bitfolk.com available entropy, daily

bitfolk.com available entropy, weekly

These graphs are very different. There’s much more jitter and a general lack of entropy to begin with. Still, it never appears to reach zero (although it’s important to realise that these graphs are at best 5-minute averages, so the minimum and maximum values will be lower and higher within that 5-minute span) so there doesn’t seem to be a huge problem here.

Virtual machines with more crypto ^

Here’s a couple of VMs which are doing more SSL work.

cacti.bitfolk.com available entropy, daily

cacti.bitfolk.com available entropy, weekly

This one has a fair number of web visitors and they’re all HTTPS. You can see that it’s even more jittery, and spends most of its time with less than 1024 bytes of entropy available. It goes as low as ~140 bytes from time to time, and because of the 5-minute sampling it’s possible that it does run out.

panel0.bitfolk.com available entropy, daily

panel0.bitfolk.com available entropy, weekly

Again, this one has some HTTPS traffic and is faring worse for entropy, with an average of only ~470 bytes available. I ran a check every second for several hours and available entropy at times was as low as 133 bytes.

Summary so far ^

BitFolk doesn’t have any particularly busy crypto-heavy VMs so the above was the best I could do. I think that I’ve shown that virtual machines do have less entropy generally available, and that a moderate amount of crypto work can come close to draining it.

Based on the above results I probably wouldn’t personally take any action since it seems none of my own VMs run out of entropy, although I am unsure if the 133 bytes I measured was merely as low as the pool is allowed to go before blocking happens. In any case, I am not really noticing poor performance.

Customers have reported running out of entropy though, so it might still be something I can fix, for them.

Where next? ^

Next:

  • See what effect using an Entropy Key has on a machine’s available entropy.
  • Assuming it has a positive effect, see if I can serve this entropy to other machines, particularly virtual ones.
  • Can I serve it from a virtual machine, so I don’t have customers interacting with my real hosts?
  • Does one Entropy Key give enough entropy for everyone that wants it?
  • Can I add extra keys and serve their entropy in a highly-available fashion?

Those are the things I’ll be looking into and will blog some more about in later parts. This isn’t high priority though so it might take a while. In the meantime, if you’re a BitFolk customer who actually is experiencing entropy exhaustion in a repeatable fashion then it’d be great if you could get in touch with me so we can see if it can be fixed.

In part 2 of this series of posts I do get the key working and serve entropy to my virtual machines.

Gating Twitter to IRC using Perl and Net::Twitter

The other day I had a strop about someone carrying on a Twitter conversation in IRC, since I didn’t have a Twitter account and had no idea what people were talking about. It was at that point that I floated the idea of gating the channel members’ tweets into the channel so I would still only have to look at IRC to follow what was going on. To me not really any more anoying or intrusive than announcing our blog posts, which the planet bot already does.

People were generally in favour of it, so I had a look around for libraries. I quickly found the very handy Net::Twitter Perl module and bolted on the Twitter bits to an existing quote bot skeleton.

The result is Twitfolk. It currently lives in #bitfolk on irc.bitfolk.com. The source is in SVN at https://svn.bitfolk.com/repos/twitfolk/.

PS. I am not a very good Perl programmer but it seems to work.

R. E. Perot, get gold card soul / My joy of life is on a roll

I thought I’d treat myself to some toys.

With FOSDEM and other events fast approaching I decided I should buy myself a new compact camera as the Konica DiMAGE I have now is just too big to carry around all the time.

I’m no camera expert and certainly not a very good photographer so I don’t need anything particularly special. pidgin recommended the Panasonic FX series and looking around the review sites the current favourite seems to be the DMC-FX33, so that’s what I got.

It arrived today (well, yesterday) and I’m really impressed by how tiny and cute it is!

Panasonic DMC-FX33

I haven’t yet had chance to really play with it but in my limited testing it seems to work well enough, and it’s certainly small and light enough to carry around most of the time.

I was also going to stick up a photo of the new server I’ve bought for BitFolk and am currently testing, but it appears to have been shipped with faulty RAM, or maybe even a faulty motherboard.

The BIOS event log shows single-bit errors corrected over the last week which must have been the burn-in period, and I can induce more of them by running memtest86. It seems the supplier did not check the BIOS event log (ECC RAM corrects single-bit errors so they were probably otherwise undetectable) before shipping.

It doesn’t seem like just a case of a bad stick or two though, as the errors appear across the whole memory space, which is why I think it could be the motherboard. I’ll get it sorted out eventually but it’s going to delay things massively and being out of capacity is costing me money.

So anyway, that’s really annoyed me and left me without anything good to say, so I’ll save it for another day!

Dear Lazyweb, help me set up my audio

In times past, when I had a desktop computer, I’d always have to be in that one place to use it, so attaching speakers to it was a reasonable way to play music while I worked. These days I only have a laptop for my personal computing needs, and all my data is on a fileserver here at home.

Unfortunately, playing music through a laptop speaker is less than acceptable. It got so bad that I just went to attach my old desktop’s speakers to my laptop, and found that one of them was dead. Clearly I need to revamp my audio setup.

So how should I do this? What I want is to be able to direct the audio from my laptop to come out of speakers in the room I am in, whether I am playing music/video from the fileserver’s samba share (common), or watching a dvd (not so common). Initially this needs to work in my bedroom, but should be easily expandable later to other places I use the laptop, such as the lounge.

I currently have no audio hardware (no hifi, no amp, no speakers) so am really starting from scratch. I’m not an audio buff and was previously happy with the quality of audio produced by decent powered computer speakers.  It’d be nice if I don’t have to attach more wires to my laptop also. There is a 100M switched ethernet network linking upstairs and downstairs so anything that isn’t going to move about can be plugged into that.

My budget is let’s say 500 UKP. Possibly more for a solution that is really good, will last ages and can be easily transported to any future accomodation.

Any suggestions? Thanks!

New fileserver for home

specialbrew's disks

Recently my fileserver, becks, was not only getting filled to capacity but was also undergoing some severe performance problems. It’s by no means a poorly-specced machine (not for home use anyway) but my use of rsnapshot has grown so much in the last 6 months that it was no longer up to the job.

Read on for the saga of its replacement.

Continue reading “New fileserver for home”

New ducti

My new ducti walletLast year sometime I bought a Triplett ducti wallet. It has served me admirably, but in the last month or two the clear tape on the outside started to peel back. With the underside of it being sticky it was getting fluff all on it and starting to look a bit scruffy.

I mailed ducti UK to ask if they had any tips for cleaning it (it does come with a repair patch, but I feel this is really all just show). They promptly mailed back with some suggestions, but also told me that if I posted it back with £5 then they would send me a brand new one, as part of their lifetime trade in policy!

So that’s what I did, and on Friday my replacement wallet arrived, with a free wallet chain thrown in! Thanks ducti!

Optimus Keyboard: What a joke

Optimus MiniPreviously I blogged about the Optimus Keyboard, and how it would supposedly be available February 1st and cost “about as much as a good mobile phone.”

Well the site now tells us that the first product will be available May 2006, the Optimus Mini. The Optimus Mini has 3 keys. It will cost $100. Now that’s what I call the difference between marketing and reality.

Somehow I don’t think I’ll bother.