Entropy Problems For Linux In the Cloud

CalTrumpet writes "Our research group recently spoke at Black Hat USA on the topic of cloud computing security. One of the interesting outcomes of our research was the discovery that the combination of virtualization technologies and public system images results in a problem for random number generation on guest operating systems. This is especially true for Linux, since its PRNG uses only a small set of entropy-gathering events, and virtual Linux images often generate SSH host keys within seconds of their initial boot. The slides are available; the PRNG vulnerability material begins at slide 63."

Comments

Another advantage for TPM chips...

[Anonymous Coward]

TPM chips have their bad things, but one thing they do offer is a cryptographically secure RNG. Its completely understandable not to trust it 100% completely, but you can use the random number stream it puts out as a good addition to the /dev/random number pool.

Re:Another advantage for TPM chips...

[profplump]

Most of the RNG chips publish pretty good specifications on the design of their entropy source, the amount of real entropy it provides, and the circumstances in which that entropy level might be reduced. There could be implementation or production errors or course, just like there could be runtime or compiler errors with software, but the design is available for perusal and has been analyzed.

For example, the Intel 82802:
http://www.cryptography.com/resources/whitepapers/IntelRNG.pdf

Re:Another advantage for TPM chips...

[evanbd]

You don't need a mic. The resistor noise on the sound card inputs is present and of secure quantum origin, regardless of whether a microphone is plugged in. The microphone noise is louder, but it's much harder to determine how much secure entropy is present. Why trust it when you don't have to? There's plenty available for most purposes without it. The Turbid program does this in an efficient and secure manner (and they have a paper discussing the details, along with the relevant proofs, for the curious).

Re:Why is this done in software at all?

[ShadowRangerRIT]

First, the cost of computing truly random numbers is way too high for that, unless you are performing an iterative approach to random number generation (and then you have the problem of predictability). It could be done, but you'd be pumping a lot of hardware into computing values that would be thrown away 99.9%+ of the time.

Secondarily, if your PRNG algorithm is broken, you're stuck replacing the hardware. At least a bad software PRNG can be replaced.

That said, hardware PRNG is provided in many modern systems by a TPM. It lacks the performance problems associated with your solution, since it only generates random numbers on demand. It still has the problem of a potential exploit being discovered leading to expensive hardware upgrades, but to my knowledge that has not been a problem to date.

Re:Doesn't SSH use OpenSSL?

[morgan_greywolf]

OpenSSL has a cryptographically secure random number generator. I know not everything uses it but doesn't (Open)SSH?

No. By default, OpenSSH will use the system's pesudo-random number generator, but you can also make it use prngd or EGD (the Entropy Gathering Daemon) instead. Whether either are more "secure" than the kernel's built-in RNG I am not qualified to say.

Definition of Cloud skewed

[smueller]

This is not a "cloud" problem. This is a virtual server and image problem. Clouds have nothing to do with virtual servers. If you use a service like NewServers.com, you can get dedicated physical servers for your cloud, on-demand and at hourly prices.

Re:Definition of Cloud skewed

[julesh]

This is not a "cloud" problem. This is a virtual server and image problem. Clouds have nothing to do with virtual servers. If you use a service like NewServers.com, you can get dedicated physical servers for your cloud, on-demand and at hourly prices.

Expanding on the other answer you've, here's the basic problem:

I can take a virtual server, install an image with a well-known PRNG seed in it, and use it for a little while. While it's used the PRNG is updated by entropy in an unpredictable way, resulting eventually in a virtual server image that produces effectively random numbers. When I shut it down the entropy pool is stored in its disk image, and reread when I start it up again. There is a small problem, but it goes away after a little while.

That isn't the usage model for "cloud" servers, however. In a cloud environment, e.g. Amazon EC2, the servers are quite likely to run for only a few hours at a time (because you start them up when you need extra capacity, and stop them when you no longer need that capacity), so the image has no time to accumulate much entropy, and worst of all when you shut it down _the data on the OS image, including the entropy pool, is lost_. The basic model is that you have many servers, all sharing a read-only base disk image. The problem occurs each time you start up a new host, which can be quite frequently.

Now, you could modify your images to stick their entropy pools in permanent storage (e.g. Amazon S3), but then you'll need some mechanism to prevent two servers from starting up with the same entropy pool, which is a non-trivial problem to solve, and I'll bet that very few EC2 users have thought to do it (I certainly didn't when I trialled EC2 a few months ago).

Re:Big problem, but addressable

[CalTrumpet]

Actually, /dev/random and /dev/urandom have their own, separate secondary pools that are fed off of a main pool when entropy is "depleted" in the second level pools. This is an area of research for us as well, since Linux's entropy estimation algorithm fails in situations where the timing deltas of entropy gathering events (IRQs and disk IOs) are actually predictable, so it's possible that the second level pools are not being refreshed at appropriate times.

If you write to /dev/urandom, it goes into the primary pool by tradition. This is what the rc scripts do on bootup with the random seed file on disk.

BTW, it's absolutely the wrong solution to get entropy from another source on the network (for many reasons, but one is that you can't do a secure HTTPS handshake without, you guessed it, unguessable random numbers). The whole point here is that we are looking for a way for 500 Linux instances on EC2 to have different entropy pools before the kernel completes boot. The only possible solution is for the hypervisor (Xen for Amazon) to provide a simulated HW RNG that pulls entropy from a real HW RNG or from an entropy daemon in the hypervisor.

The best way to learn about Linux RNG basics is Gutterman et. al. Analysis of the Linux Random Number Generator. Several of the issues they describe have been addressed, such as their PFS concerns, but their description of the entropy pools is still accurate.

Old hat?

[GiMP]

Disclaimer: I work for a hosting company doing VPS/cloud hosting.

This is pretty old-hat. First, the host-keys issue inside pre-generated images is a very obvious one, although I'm not too surprised that companies aren't considering it. RNG issues aren't quite as obvious, but they're not super-secret either, anyone with any amount of background in security has been aware of this for a while.

In fact, questions regarding RNGs have even surfaced in the ##xen IRC channel (freenode.org) because it is a very important issue to some. In particular, those with the need for hardware RNG solutions have come seeking assistance.

I'm certainly not minimizing the issue, just noting that it isn't really a new one at all. More than anything, is that the average systems administrator has been slow to realize this, and developers even less so.

problem has been solved

[flok]

This problem has been solved: use EntropyBroker: a physical machine gathers entropy data and distributes this to the virtual machines. If I remember correctly KVM has a special driver for feeding the VM with entropdata from the host system.

Use Linux-VServer/OpenVZ or LXC

[Lennie]

Those just use process-namespaces and the same kernel and you are done with it.