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.
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?
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.
$_ = "wftedskaebjgdpjgidbsmnjgcdwatb"; tr/a-z/oh, turtleneck Phrase Jar!/; print
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.
So, I was mostly just giving him shit because of his name. If you want a more serious debate, here's my best shot: The instructions you described are all relatively easy to define a generally useful specification. My main point was that every application has differing standards of randomness that are required. Do you need real quantum-mechanical randomness, or just a CSPRNG? How many bits of random data do you need, and how frequently? I'm assuming that the request is for real quantum-mechanical randomness. I find it hard to imagine defining a good spec for such hardware component, especially since the vast majority of applications don't actually require quantum-mechanical randomness, and the ones that do are likely to have very specific requirements. Anyways, besides the fact that it's tough to come up with good requirements for such a feature, I bet it's really tough to implement as well. I know just barely enough about about hardware implementations to be dangerous, so someone who knows for real, please correct me if I'm wrong. Anyways, circuits that exhibit quantum-mechanical randomness are, as far as I know, essentially the same as circuits that cause metastability in transistors. Because of the need to control for such problems, implementing such circuits on the same die as a normal digital circuit would likely be very expensive in terms of both die area and yield.
I think of some primitive post-human civilization struggling to industrialize amid the ruins of the heat-dead universe.
....
There's little solid matter left. Nobody really knows why; the legends tell of ancient, sprawling empires releasing great monsters that consume worlds and deliver energy to fuel their eons-old wars in the cold between the stars. Several human colonies survived the Last Scourge. One even knew something of their people's history. This colony of merchant-scholars thrived in an old space-borne city drifting about a great lightyears-long dust cloud inexplicably left untouched by the wars. The city was old, very old, built by a generation of master engineers who etched their likenesses in the great canvases of the city's impervious white construction. Quiet machinery lurked untouched in the mysterious depths of the undercity, seen only by outcasts wandering alone through those vast echoing chambers.
The city provided everything the civilization needed. Somehow (so much seemed like magic to them that even the usually-curious humans grew bored of speculation) their reservoirs filled with water, their air recycled, and their waste disappeared down bottomless shafts. All of their needs were filled, but they craved expansion and exploration. They were able to harvest some limited chemical energy from the food supplied by the city, and build using scrap. Still, entropy was a problem in the dust cloud of Linux.
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.
I'm glad he cleared that up for me.
I want this account deleted.
As has been so often said, the generation of random numbers is too important to be left to chance. :-)
Ian Ameline