Slashdot Mirror
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."
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.
How about getting signed entropy from a trusted server on the network/internet? How about putting that microsecond-accurate system clock to use?
Why can't the CPU contain a register which holds a random number which is updated with every clock cycle?
Generating SSH keys involves interaction via at least keyboard and possibly mouse at a terminal. Surely that basic permise is enough to provide enough entropy for the pseudo-random generator. Also, the date and time (as sources of random) can't be virtualized of course.
"I bless every day that I continue to live, for every day is pure profit."
All this complaining over random numbers is silly. All you really have to do is use 5. It's just as random as any other number, and it's easy to generate a 5.
-Taylor
Worldwide Military budgets: $2100 billion. Worldwide Space Exploration budgets: $38 billion. Really, world? Really?
Generating SSH keys involves interaction via at least keyboard and possibly mouse at a terminal.
SSH host keys are often generated automatically when the init script notices there aren't any.
Java code that does cryptography or generates UUIDs (in the hope that they will be a truly universal key for something) operates under similar problems. JavaScript is even worse; all it has is the time, perhaps the user's window-size (not very random if maximised) and mouse-movements, and the built-in random() method, which is not expected to be of cryptographic quality.
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.
My blog
CONFIG_HW_RANDOM_VIRTIO enables it. It's been there for quite a while.
We could easily support it in KVM but I've held back on it because to really solve the problem, you would need to use /dev/random as an entropy source. I've always been a bit concerned that one VM could starve another by aggressively consuming entropy.
lguest does support this backend device though.
AC, let me guess... you work for a cloud computing company, but not in marketing :-)
I'd like some evidence that cloud computing is a fad. Tens of thousands of companies, in dozens of industries, do not list "computing hardware, availability, and capacity management" as a core competency, making them prime cloud customers.
Seems to me this could be solved via the "Guest Additions" module that most virtualization packages recommend you install in the guest OS. Use the GA to inject some entropy from the host system into the guest system's entropy pool. The host CPU's TSC register would probably be an excellent source.
Whether either are more "secure" than the kernel's built-in RNG I am not qualified to say.
Well, it depends on the hardware, as the kernel has drivers for various hardware RNG featured on some CPUs or virtualized source of randomness provided by the host.
"Sufficiently advanced satire is indistinguishable from reality." - [Tips: 1DrYakQDKCQ6y52z6QbnkxHXAocMZJE61o ]
If you "need" cloud computing, then you're bright enough to install an entropy daemon on one of the machines and maybe even slap a hardware-based RNG on it (probably worth sourcing a VIA or similar just for this purpose, to be honest). It's not hard.
Anything else, your "randomness" really doesn't matter and the standard entropy will be just fine.
Troll!? Whoever modded me troll has to have a look at the Avogadro's number and its relationship with this thread.
Like Web 2.0, it has at least one or two specific meanings. The problem is getting specific -- a little knowledge is a dangerous thing, and managers can be very fuzzy (clouded?) about "cloud computing" if they don't understand the difference between calling Gmail a "cloud app" and calling Amazon Web Services a "compute cloud".
Don't thank God, thank a doctor!
Yes. Because no one on the Internet has any use for gathering venture capital or selling products.
It IS an overused term, but you're not testing some product or how people are using it, you're really just testing the security models of various operating systems to determine which are more ready to support those concepts that people grouped together and called "cloud computing". There were a lot of various concepts that were grouped together that comprised the "Net 2.0" concept too...and that cliche was just as derided for being overused. And yet, websites that aren't all ajaxed up or don't use css seem pretty old-fashioned these days.
That said, the question I have is how ready for those "cloud computing" concepts is Windows, really? How much of that security model is using the proper approach to securing a transaction instead of just shutting down that path altogether?
Cloud computing is real, and some of the biggest computers in the world are devoted to it. Climate modeling is a very difficult problem and we still don't have it nearly right.
.sig withheld by request
Care must be taken when joking on Slashdot. It's not your fault, but you probably should have linked to Avogadro's Number in your first post. Even dead simple jokes must be sufficiently documented to avoid getting modded down.
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.
Or you could plug in a microphone.
Assign all of he virtual servers a unique 256 bit ID. XOR that with 256 bits of input of any USB device that measures the real world, and send it through a hash algorithm. USB devices are easy for virtual servers to access.
Perhaps better, have a 256 bit seed for each server as above, but have the host server distribute 256 bits at startup time using a microphone run through a hash algorithm.
Interesting idea, though I would recommend HTTPS (pre-shared self signed cert would be sufficient for in-house use). If predictability is the problem you're trying to avoid, you want to skirt the packet sniffers.
By the way, why write to /dev/urandom, and not /dev/random? Doesn't /dev/urandom act as a front for /dev/random except when the entropy pool is empty (at which point it goes pseudo-random). Just curious.
I won't join Slashcott. OTOH, If Beta goes live, I just won't be back until it's fixed. Sorry Dice.
I did a system wipe and rebuild (re-installs CentOS from scratch) and SSH'ed in and... got no warning. The system's SSH keys were identical as the previous build. Needless to say I generated a local set and uploaded them.
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.
/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.
If you write to
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.
Umm... what?
Either we've had an honest misunderstanding here due to my not being entirely clear (which I'd be more than happy to straighten out), or you're a clueless moron. Unless you're willing to clarify why you consider me a "troll", I have no choice but to assume the latter.
I'm glad he cleared that up for me.
I want this account deleted.
The host CPU's TSC register would probably be an excellent source.
Actually, if 636086 reads the xen mailing lists then it's probably a subtle joke.
There's a simple random number generator based on a radioactive source on-line. That can be accessed through a Java app, and the hardware info needed to build one of your own is on line. There are commercial random number generators. USB, even. A serious data center should have a few of these.
No, seriously. The TSC counts raw host CPU clock ticks. I/O interrupts and CPU cache misses on the host should effectively de-correlate it with anything going on in the guest VMs. On a host with many guest VMs it only gets better, since the patterns of host I/O interrupts and guest VM timeslices will be even less predictable.
As long as it is not relied on as a continuous source of high quality entropy (i.e. it should be used to seed the pool, just like things like mouse movement etc. are used now), it ought to be a significant improvement.
...and if you're worried about someone running a guest VM and using the host TSC value as the basis for some sort of attack on the RNGs of other similar VMs running on the same host, just run the TSC value through a hash function on the host side, before passing it to the VM. As long as the hash function is effectively one-way, you can't glean any information which might be useful in an attack on "sister" VMs.
try scaling that up, and see where it ends up...
comment first, facts later. http://chem.tufts.edu/AnswersInScience/RelativityofWrong.htm
Running nmap against the same host but the physical OS (currently FC-11) gives:
This would seem to indicate that "cloud" TCP/IP sessions may be vulnerable but session hijacking.
Cheers,
Dave
They that can give up essential liberty to obtain a little temporary safety deserve neither safety nor liberty.
Ben
As has been so often said, the generation of random numbers is too important to be left to chance. :-)
Ian Ameline
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.
A book of random numbers is great for statistics. If that's your use there's no need to do anything else, and RAND's book is still a good choice.
But the value of random numbers in things like cryptography is that they are unpredictable. If everyone is using the same list the numbers are entirely predictable and therefore useless. A typical example is the hybrid cryptosystem used in public-key encryption -- the computer picks a random number for use as the secret key for the shared-secret cypher, encrypts the data with that key, then encrypts the key itself using the much slower and more restrictive public-key algorithm. If you could guess the random number used as the key in step 1 you wouldn't need to break they encryption in stages 2 or 3 to read the message because you'd already have the password.
Cloud computing is real[...]
Point was it is not well defined. Its like "architecture" or "web 2.0" or "beautiful": everybody knows exactly what it means - but everybody has a different idea of what it is...
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.
www.vanheusden.com - home of Multitail, HTTPing, CoffeeSaint, EntropyBroker, rsstail, bsod, listener, nagcon, nagi
Dang, you're right. Thanks for the post.
I won't join Slashcott. OTOH, If Beta goes live, I just won't be back until it's fixed. Sorry Dice.
If I'm not lost in the intertubes, where are my 'oblig. xkcd/Dilbert' karma whores?
**TODO** [X] Steal someone elses sig.
DiceOMatic. Complete with USB camera interface.
Andrew Yeomans
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.
If we're talking about a VM, what's wrong with setting up a point-to-point link with the host machine and accessing an entropy source over that, with no HTTPS handshake necessary?
> The nice thing about Linux is that you can develop whatever entropy-producing process you want /dev/urandom to add more entropy to the pool.
> and write its output to
Anyone know, what OOTB processes/programs and/or events do in fact seed /dev/random?
is that it doesn't exist. It's a farce, a meaningless buzzword, just like web 2.0.
A more appropriate word would be servers.
You miss the point. We aren't talking about servers, and any ordinary server-provision system wouldn't have the problem highlighted in TFA. We are talking about servers that are initialised on-demand, with a pay-by-the-hour pricing model, so that individual OS installations typically only run for a few hours at a time before being shut down and essentially wiped back to the base installation image. That's a model that's different enough from traditional virtual hosting that it warrants a different name, and while I think "cloud computing" is a _ridiculous_ name, it's the name the model's ended up with.
well... i screwed up and got my threading mixed up so I thought you'd replied to a different post. d'oh.
All I was saying is that based on recent discussions on xen-devel concerning TSC synchronisation when physical CPU's are scheduled into virtual CPU's in a VM, the value might as well be a random number for the amount of use that it is. I assumed you were making a joke about that, but obviously you were replying to a different post than I thought you were.
As part of cloning the image just do this:
dd if=/dev/urandom of=/target/var/lib/urandom count=1 bs=4096
There. Fixed it for you. Works better if the VM server has a high volume entropy source, but even if not it is still pretty damn good.
Except this is somewhat harder to do if you're running a service where you provide virtual machines that run OS images from unknown sources, that could be running basically any OS/distribution the user wishes, with the image using practically any file system that has ever been designed. Sure, if you limit your service so it can only run images that are based on ext3 and conform to the linux file system standard you can do this. But that's not the business most of these services (e.g. Amazon EC2) are in.
I am by no means a cryptography expert, but I do remember hearing a while back that the radio "static" that you hear at "empty" radio frequencies are signals from outer space (and likely also from other stray terrestrial sources); the same for those "static" TV signals. Could those be used to collect entropy? It should be a cheap and fairly easy solution...
...should be importing it explicitly (eg to create important crypto keys) from an external source, such as random.hd.org (mine) or random.org or whatever.
Rgds
Damon
http://m.earth.org.uk/
As others said, you can get enough random data from a soundcard, hardware RNG, or other relatively simple** solution. Making true random data available to each virtual machine regardless of when it booted or what image it used is as simple as making your VMs boot with a specific kernel, patched to connect use the host's entropy rather than its own.
I was assuming that the TSCs are not synchronized tightly enough between host and guest(s) to be correlated, at least not in the low order bits. Perhaps this was a bad assumption. (Though I have to believe that it is still a lot more "random" than most other things accessible to the guest.)
My apologies to #1103839; your post was rude, but I should not have responded in kind.
At least I injected some humor into the thread (if unintended)!
But this headline should have read "Rotten news, Public Images Limited."
There's a Starman, waiting in the sky / He'd like to come and meet us, but he hasn't got the time.
Those just use process-namespaces and the same kernel and you are done with it.
New things are always on the horizon
You could have the central-entropy host run a UDP service that generates new random data per outgoing packet and only respond to requests from the cloud's expected IP range. Ideally the central-entropy host would be co-located with the cloud elements and behind a firewall.
For the specific case of EC2, the deployer should patch /var/lib/urandom/random-seed (as well as the SSH host-keys, etc) on each image from a secure system outside the cloud before boot; but I haven't actually done that, I'm not sure how easy it is with the current API.
Something like this would be workable, if the actual server managing the cloud of virtual ones was running the book, and seeding the VMs with random numbers... but in effect the solution is probably what other people are suggesting, when you design a system, you have to have it use an external "entropy server"..
The best thing about downloading random numbers from the Internet is that if you ever lose them, the server you got them from probably still has a copy.
True... B^>
I realise that I didn't mean quite what I said, but rather that gathering entropy for such tasks shouldn't just rely on scraping up whatever happens to be on your box at start-up. For example, you can collect more, with care, from HTTP hits on a busy server (with guards against being spoofed such as only using microsecond-scale jitter between hits).
Rgds
Damon
http://m.earth.org.uk/
Um, the article is discussing multiple virtual machines with identical disk images so "hardware support" is moot.
Ok I think I wasn't explicit enough.
I said :
drivers for various hardware RNG featured on some CPUs or virtualized source of randomness provided by the host
What I mean :
can optionally use real hardware support to fill its own entropy pool. (lots of CPU have it). Thus the pool is far less likely to get depleted.
they will tend to give out similar result, because each has similar simulated environment and simulated event from which entropy pool is filled.
Running software entropy source in a simulated environment is asinine. A source of entropy should by definition be un-predictable. A simulated environment IS indeed fully predictable. (Just run the same simulation twice)
They load a driver like the VirtIO mentionned a couple of pools bellow. And the host will simulate a CPU with a RNG inside the virtual machine. Thus the clients can get true (or at least better) random numbers, as they recieve real actual numbers through the virtual simulated RNG generated out of real random numbers produced by the virtual host (with optional hardware support on the host, so the production keeps up if there's a lot of demand from multiple client machines).
Got it ?
No PRNG.
Virtual machines has an emulated "(pseudo-)hardware support" which passes actual random number produced by the real host using actual hardware support.
The number are truly random.
This is already available and used since some time.
TFA has no value as "Oh my god, Linux is going to break appart now".
TFA should only be used as an alarm to advise admin who didn't start using such more secure entropy systems yet that, well, they should seriously consider starting to use the "(pseudo-)hardware support".
I hope I made my self more clear.
"Sufficiently advanced satire is indistinguishable from reality." - [Tips: 1DrYakQDKCQ6y52z6QbnkxHXAocMZJE61o ]
BTW:
All my explanation is about situation with fully virtualized clients (the emulators emulates a complete hardware machine for each client).
But with linux, there's also other situations, where the machine is only partially virtualized with operating system level virtualisation.
In that situation each virtual machine is a separately compartmented stack of user space software, but all running on the same single copy of kernel (which might by modified in order to be able to manage several such compartement).
This is available on linux with Linux VServer and OpenVZ (both use special kernel modules to manage virtual compartments), and a special "Linux-on-Linux" mode of QEMU (fully user-space software, it just passes kernel and library calls from software run inside the emulator to the actual system).
In these situation, there are several virtual machine clients, but all running on 1 single host kernel. If that kernel can produce random number, all host get true random numbers. If that kernel has (true) hardware support for a hardware entropy source, all virtual client get benefit from it. (without needing a driver for a virtual source like in my previous explanation)
"Sufficiently advanced satire is indistinguishable from reality." - [Tips: 1DrYakQDKCQ6y52z6QbnkxHXAocMZJE61o ]
Point is, it would help to read the post you're replying to (and possibly calibrate your sarcasm meter).
.sig withheld by request
I missed the joke. Wish I could disappear in a cloud now.