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?
OpenSSL has a cryptographically secure random number generator. I know not everything uses it but doesn't (Open)SSH?
In the article are they just talking about the kernel random generator? I wouldn't trust that thing, even the "secure" one.
The number of molecules in Cmdr Taco's nacho-warrior farts !! This can range from a few thousand on a mild day, to say 4 BILLION on a down and dirty day. I know, I know, and you don't want to know how I know.
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."
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.
"it's": expected adjective; found verb instead
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.
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.
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.
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.
If a random number generator is supposed to be random, won't one rng have the same chance to generate the same numbers as another in a given set?
Its a sign of failure when noone even bothers to mod you troll...
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?
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.
In Linux, it's not possible for one application to starve another of entropy. (At least, on my computer. I'm using Debian unstable). To check, try this: /dev/random
1. Open 2 xterm windows (or 2 ttys, or whatever).
2. In the first window, type: cat
3. Watch the gibberish on the screen.
4. Type the same thing in the second window.
5. Now, hit the ctrl and shift keys repeatedly, and move the mouse, to generate entropy.
6. You should see more gibberish in both windows, showing that neither one gets starved.
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
Did you post that wirelessly from the gay bar you frequent? Nice to know that since you're here too, you're calling yourself gay. Unless you meant that Slashdot is full of cigarettes, or a bundle of sticks.
On an even more off-topic note, what's with "Anonymous Cowardon"? Fix that shit, Taco! AC users don't have a friend icon to create a space between the username and the "on [timestamp]", so you need to add one in.
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
Why can't you just store 1 gig of "good" random numbers in each server?
After all, this is what they used in the "good old times", the famous RAND book...
http://www.rand.org/pubs/monograph_reports/MR1418/
Any serious answer?
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.
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
Faggot.
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?
honestly, not random at all
> 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?
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.
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.
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.
The kernel's estimates of provided entropy are pretty low though, so the event must be _very_ unrandom for the count to be too high.
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).
I've always though that received packet times and src/dst MACs should be included in the entropy pool, even if the estimated entropy is zero. Put it through a whitening algorithm then a cryptographic hash. Now it can be mixed in safely and improve the entropy (even if you don't trust it enough to actually count on it for randomness).
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.
If that's the only solution you can think of you aren't being very creative. Though it does seem like it would be a reasonable thing to do. You can also do stuff like mix in hardware serial numbers and addresses (motherboard, DIMMs, processor, network cards, hard drives) into the pool via userspace. They aren't really random (so they shouldn't increase the entropy count), but they will make sure each computer has a different state.
-Ross
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 ]