Russell: Sources of Randomness for Userspace [LWN.net]

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 5:31 UTC (Fri) by drag (guest, #31333) [Link] (25 responses)

None of those sources strike me as particularly random. For example if I order 30 or 40 Linux machines from Dell for desktops or something then I would be getting nearly identical machines.. same ram, same cpu, same everything. Even the Mac address would be fairly predictable and easy to fine. I suppose you need to get a seed from somewhere, though.

I am curious how safe haveged is for cryptographic purposes.
http://packages.qa.debian.org/h/haveged.html
http://www.issihosts.com/haveged/

With modern Linux systems if you don't have a keyboard/mouse hooked up it can be a very significant problem to generate enough data for /dev/random. What makes the problem worse is that the modern use of virtualization means that many people are running VMs that suffer a acute shortage of random data. This can lead to a lot of performance issues.

I ran into this while trying to generate some RSA keys for IPsec stuff on various machines running modern kernels. On my local machine the key was generated instantly. On other machines not so much.

All the systems running on top of KVM had severe problems generating keys. On Fedora it just failed straight away. On Debian the keys just blocked.. it would of taken several hours to generate a key that was instantly generated on my laptop using the same system. I was able to work around this problem by connecting to their consoles via spice and literally rubbing my hand over my keyboard until it had enough 'random' data to generate the key. Very irritating. One system in particular was very difficult to deal with. It was running on real hardware, but it simply couldn't generate the 'randomness' that it needed and it was remote so I couldn't just rub the keyboard down.

I've looked into various solutions and the best one I've seen is to purchase a USB random data generator. Other ones like pulling random data from audio or video seemed cool, but I couldn't really get quality data.

Havege was dead simple to use and it seems 'good enough'. It uses the randomness generated by modern system processors. More or less executes some code to strain the cpu in a particular fashion then measures the time it takes to run it.

Now... the only very significant problem I see for it is when it's on virtual machines.

I found this:
http://polarssl.org/trac/wiki/SecurityAdvisory201102

> This issue affects machines running within environments where the RDTSC call has been disabled or handicapped. Currently, the problem seems to be limited to some commercial cloud server providers.

> If affected, this means the RNG produces predictable random and as such security is severely compromised.

I read somewhere that this means that using RDTSC instructions in certain VMs returns 0x0 or some other predictable number, which destroys havege's algorythm's effectiveness. Does anybody know a good way to test these cpu instructions effectiveness in a VM to know if haveged can be safely used?

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 7:12 UTC (Fri) by alankila (guest, #47141) [Link] (20 responses)

There are a few things that I find difficult to understand about this.

Firstly, a freely oscillating circuit inside the CPU to generate random bits doesn't seem complicated to me. It should extract true randomness as fast as you could move bits from the CPU to memory. Why hasn't it been done?

Lacking a CPU instruction, virtual systems could just have a random driver to help them along. They would receive data from the host, using whatever combination of true random / pseudorandom generation as necessary. It's in all likelihood of low complexity problem, an afternoon's hack. Why hasn't this been done?

It only takes in the hundreds of bits range of true randomness to properly seed a random number generator, after which it can be run for significant periods (probably years?) without leaking the prng state. In fact, if you unpredictably flip the bits in the prng state based on true random inputs, the problem seems entirely solved to me, as no amount of reading the prng output reveals anything consistent about its state. Am I missing something, again? (Hypothetical answer: people simply are really paranoid about randomness of their random numbers. But is such paranoia justified?)

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 8:19 UTC (Fri) by drag (guest, #31333) [Link] (4 responses)

> Firstly, a freely oscillating circuit inside the CPU to generate random bits doesn't seem complicated to me. It should extract true randomness as fast as you could move bits from the CPU to memory. Why hasn't it been done?

I think a few Intel CPUs implement some form of hardware entropy generation. I don't know the feature very well. There is Via Padlock, which will do this, but I don't have one of those systems. There are a few examples besides that.

Otherwise a USB device can be purchased that features a entropy generator:
http://www.entropykey.co.uk/

I think there are a few problems. One of which is that generating entropy is a lot harder then it sounds like it should be. Another problem is that for many interested parties who would want a good source of entropy there is a number of certification requirements that they have to deal with and for hardware manufacturers it likely expensive and irritating to deal with.

I know from my work with embedded devices used in various places we could not take advantage of the Via padlock system due to it not being up to certification requirements.

(these certifications are largely a bureaucratic matter based mostly around documentation and provability of correctness using certain specific tests. It's very possible to have a secure system that doesn't match government requirements (thus being illegal), but have a insecure one that does. (thus being legal))

> It only takes in the hundreds of bits range of true randomness to properly seed a random number generator, after which it can be run for significant periods (probably years?) without leaking the prng state. In fact, if you unpredictably flip the bits in the prng state based on true random inputs, the problem seems entirely solved to me, as no amount of reading the prng output reveals anything consistent about its state. Am I missing something, again?

I don't know. This does not seem to be a solved problem. I don't know the details, but I know if it is a solved problem then I wouldn't be having these problems with /dev/random and there wouldn't be any reason to have /dev/urandom. It seems that it would be a simple thing to have a PRNG generator in the kernel then to eliminate all the problems people have with dealing with large numbers of SSL connections and such things. It would simplify matters massively.

Haveged seems like a decent solution, but like that advisory said that 'HAVEGE' depends (which is what haveged is based on) on RDTSC to be functioning. Now I know the deamon itself sources the data from the algorithm and then feeds it through PRNG and it could be doing other things for random data, so the actual daemon may not have the same weakness that the algorithm does.

> (Hypothetical answer: people simply are really paranoid about randomness of their random numbers. But is such paranoia justified?)

It can be justified based on the circumstances. Well funded corporate espionage is real. 'Hackivism' is real. Military security concerns are real. Professional organized computer criminals are real. People trying to pursue and defeat governments attempts to monitor and document their activities is real. It's easy to half-ass things and have it work fine, but it's very difficult to be able to prove if it's actually working correctly.

I don't have any strong reason to care right now and probably just symbolic linking /dev/urandom to /dev/random would be perfectly fine for my purposes... however I would like to know the right way to do things and I don't have the expertise to figure it out for myself. :(

Ivy Bridge first Intel processor with digital hardware random number generator

Posted Mar 30, 2012 13:17 UTC (Fri) by jhhaller (guest, #56103) [Link] (2 responses)

There have been analog random number generators in chipsets before, but they were relatively slow (few hundred kilobits per second), compared to about 3 gigabits per second. See IEEE Spectrum article, including a reference to lavarand, the lava-lamp based random number generator.

Ivy Bridge first Intel processor with digital hardware random number generator

Posted Mar 30, 2012 15:17 UTC (Fri) by jhardin (guest, #3297) [Link] (1 responses)

I've always wondered why a 4- or 8-bit register incremented on every clock cycle wouldn't be a simple yet good enough source of entropy? How often is it going to be read?

Ivy Bridge first Intel processor with digital hardware random number generator

Posted Apr 2, 2012 12:52 UTC (Mon) by jzbiciak (guest, #5246) [Link]

That was a fine source of randomness for, say the MIPS TLB random replacement, especially since page faults are "far apart," typically.

What about the kernel entropy pool though? First off, where are you sampling this counter to give you data to mix into the pool? Interrupts? With periodic interrupts, you can probably only trust the LSB of the counter to be truly random. That leaves you generating only hundreds or thousands of bits per second.

In any case, on most modern CPUs, we have this freerunning counter already. On x86, it's called the TSC. Of course, it appears RDTSC can get mucked up by virtualization.

Russell: Sources of Randomness for Userspace

Posted Apr 1, 2012 3:56 UTC (Sun) by lordsutch (guest, #53) [Link]

Intel's Ivy Bridge CPUs (coming Real Soon Now…) will include RdRand on-die, providing all the random numbers you'd ever need.

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 12:46 UTC (Fri) by man_ls (guest, #15091) [Link] (11 responses)

(Hypothetical answer: people simply are really paranoid about randomness of their random numbers. But is such paranoia justified?)

I would say people are not paranoid enough, given the consequences. A bad random generator can easily go unnoticed and can cause real problems. How can I be sure that PHP's openssl_random_pseudo_bytes is really random? How can I be sure that my implementation is not removing randomness?

A couple of examples. There was this incident a couple of months back, not to speak about Debian's fiasco with SSH keys.

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 16:13 UTC (Fri) by alankila (guest, #47141) [Link] (10 responses)

All of these problems seem to relate to the fact that people don't just read a bit of /dev/urandom and be happy. The reason why I don't recommend reading from /dev/random is the very low data rate. I have in memory an incident where I had to build ghostscript to not read image dithering data from /dev/random...

It seems to me that this ball should be just dumped into kernel's turf and require that urandom provide "industrial strength" random numbers at rates that make the thing usable for almost all applications.

My instincts say that random numbers *can't* be this hard. I think adding complexity to what should be simple is just making things worse.

True randomness

Posted Mar 30, 2012 16:41 UTC (Fri) by man_ls (guest, #15091) [Link] (9 responses)

Why, random numbers are incredibly complex. Try asking someone to give you a few random numbers and check them for patterns. Or just try to play rock-paper-scissors with the random strategy. I have won some of these rps simulators, and boy is it exhausting!

How do you find random numbers in Nature? You can expect to find noise from many sources, but there are many different types of noise: white, brown, pink. Each one has its own characteristics; you would have to use a filter for each of them if you want good, old white noise, or you are losing entropy bits. Even with a source of white noise, you have to normalize it and remove any non-random components that may appear (either from the noise source or from your equipment). And even if you make sure that you are getting random values using all the tests you know, someone may come along and find a regularity you did not think of, and put your "random" source to shame.

With pseudo-random number generators (which cause, as you will know, a state of sin) you can never be sure either. Sure, the period can be huge, but that only speaks about repeating values. The big question is again: what hidden regularities are there in any algorithm that we don't know about?

/dev/urandom is a nice trick, but in fact you are only brushing the problem under the carpet: is the kernel's PRNG implementation good enough for you? Does it get entropy from any sources, or is it just going through the PRNG sequence? In fact it may be even worse than your own algorithm, since you may be trusting it to be secure (getting some entropy from somewhere) when in fact it is not. So, /dev/urandom is not good enough to be happy for cryptographic applications. And crypto is not so esoteric these days: any programmer worth their salt should be able to hash passwords (pun intended but not deployed).

For me, haveged is a great concept because it should make /dev/urandom quite secure (and make you really happy), but I share drag's reservations about VMs.

True randomness

Posted Mar 30, 2012 16:53 UTC (Fri) by alankila (guest, #47141) [Link] (4 responses)

While this all sounds appropriately cryptic,
dark and foreboding, it seems more relevant
to ask if there are any practical
attacks against urandom. It seems
to me that the existing entropy
could be used to fully replace
urandom's seed several times per second.

True randomness

Posted Mar 30, 2012 17:09 UTC (Fri) by man_ls (guest, #15091) [Link] (2 responses)

See, the problem about randomness (and probably why you perceive my message as cryptic and foreboding) is that it can only be defined in the negative. The complete absence of patterns is basically impossible to prove; it can only be suspected.

But I see you like your solutions simple and your answers straight. Your hypothesis is easy to test:

  $ cat /dev/random

and see how quickly it fills out. For me it is barely enough to reseed urandom (32 bytes) once a minute, while using it; if I leave it alone it seems to take quite longer.

As to practical attacks against /dev/urandom: I hope that there are none because then I fear all my communications (and most in the world) would be vulnerable. But perhaps the NSA (or other sinister organizations) have a few of their own.

True randomness

Posted Mar 31, 2012 16:47 UTC (Sat) by alankila (guest, #47141) [Link] (1 responses)

I just tested this. It seems that entropy collection takes very long time indeed. What a pity. Apparently there's just a kernel buffer that contains gathered entropy, and consuming that entropy allows me to see that it will be replenished rather slowly. So the statistic munin graphs me is not the rate of entropy generation, but merely the amount of available entropy.

Somehow this multi-gigahertz multi-core machine and all its myriad peripherals together are not harvested for more entropy than about 10 bits per second.

True randomness

Posted Mar 31, 2012 16:52 UTC (Sat) by man_ls (guest, #15091) [Link]

Right, that is where haveged should help. Whether it works well in virtualized machines remains to be seen.

True randomness

Posted Mar 31, 2012 15:25 UTC (Sat) by man_ls (guest, #15091) [Link]

While this all sounds appropriately cryptic, dark and foreboding,

By the way, the foreboding part is not just theoretical. See precisely this week's security QotW:

I believe that what the "top official" was referring to is attacks that focus on the implementation and bypass the encryption algorithm: side-channel attacks, attacks against the key generation systems (either exploiting bad random number generators or sloppy password creation habits) [...]

Guess who employs thousands of cryptographers precisely to study these vulnerabilities. If the NSA had found a vulnerability in /dev/urandom (or ten) they would probably not publish them. "No known attacks" in cryptography seems to be a meager consolation, but in RNGs it is doubly so.

True randomness

Posted Mar 31, 2012 2:18 UTC (Sat) by bluss (guest, #47454) [Link] (3 responses)

Why not use an encrypted stream with a random key?

Read a relatively short key off /dev/random, then generate a stream of bytes by encrypting /dev/zero using that key. With AES-NI you get more than 300 MB/s using AES-256 and this *should* be good enough.

True randomness

Posted Mar 31, 2012 8:58 UTC (Sat) by man_ls (guest, #15091) [Link] (2 responses)

Because you would be leaking key material like crazy. Even if you used a correct stream mode you would transform the business of running a PRNG into a known plaintext problem, which is about the easiest in cryptography.

True randomness

Posted Mar 31, 2012 13:15 UTC (Sat) by intgr (subscriber, #39733) [Link] (1 responses)

> Because you would be leaking key material like crazy.
> you would transform the business of running a PRNG into a known plaintext
> problem, which is about the easiest in cryptography.

Sorry, but this is nonsense. In practice, every cryptographic protocol transmits some known (e.g. predictable) plaintext. If a cipher is vulnerable to a known plaintext attack at all, the cipher is simply broken.

In fact, a stream cipher (or a block cipher in CTR mode) in its most basic form, *is* a PRNG -- put a key in and it spits out a pseudorandom keystream. Most cryptographic PRNG systems (Yarrow, Fortuna, CryptGenRandom) do use a cipher this way to generate the output stream -- because ciphers have well-known security properties.

True randomness

Posted Mar 31, 2012 14:29 UTC (Sat) by man_ls (guest, #15091) [Link]

Sorry about the confusion, I should have refreshed these things before answering. (This goes to show how non-trivial this random number generation business is.) The original suggestion was to just encrypt /dev/zero which had all the faults described above, because it was not using an IV and key material would be leaking. Correct block cipher modes (not "stream modes" as I said) such as CRT use an initialization vector, use the result of one operation to XOR the next value, and use a counter instead of /dev/zero. All these things are done to avoid a plaintext attack.

Once you take care of these issues, then you have a cryptographic PRNG system. Even so you have to pick a correct cipher to avoid a plaintext attack. And even with good ciphers apparently there are attacks based on the regularity of the input.

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 14:29 UTC (Fri) by fuhchee (guest, #40059) [Link] (1 responses)

"virtual systems could just have a random driver to help them along."

See virtio-rng.

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 16:19 UTC (Fri) by alankila (guest, #47141) [Link]

Thanks for the pointer. I just checked and saw that my kvm-based virtual machines already had about the same amount of random entropy gathered as the host (140 bytes/s or so). So presumably this rate is normal or the problem is already solved.

Justified paranoia re. RNGs

Posted Mar 30, 2012 15:47 UTC (Fri) by hmh (subscriber, #3838) [Link]

Yes, a very high level of paranoia is justified when dealing with RNGs that are going to be used in crypto.

Depending on the type of cryptography (and mode of operation) being used, a flawed RNG will allow an attacker to derive some key material or even the entire key at once.

That does mean you need a strong RNG at all times to be safe, not just when generating persistent keys. In practice, it means you have to avoid like the plague any crypto that depends on the quality of the RNG on *both* sides to avoid disaster...

I will leave it to an expert to explain which classes of crypto algorithms and modes of operation are more resistant to bad RNGs.

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 9:49 UTC (Fri) by flok (guest, #17768) [Link]

For infrastructures with lots of virtual machines I would like to suggest my EntropyBroker application which distributes entropy data between machines. It can interface to a real source of random data and/or obtain from a sound or videocard or interrupt device.
http://www.vanheusden.com/entropybroker/

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 10:51 UTC (Fri) by awoods (subscriber, #21721) [Link]

I managed to improve the entropy-pool problem on a couple of Xen systems I looked after once that needed the entropy for its VM's by using an inbuilt TPM chip, which many motherboards seem to have.
A daemon (I think is came from rng-tools) can read this entropy data and feed it to the pool.
Had no problems with encryption operations blocking after that.
For high-security systems one would definitely want to validate the quality of the TPM RNG data which no doubt varies from manufacturer to manufacturer, but for the purposes I needed at the time it worked perfectly.

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 12:02 UTC (Fri) by ewan (guest, #5533) [Link] (1 responses)

On my local machine the key was generated instantly. On other machines not so much.

Too obvious to suggest just generating the keys locally and copying them to the servers?

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 12:41 UTC (Fri) by drag (guest, #31333) [Link]

> Too obvious to suggest just generating the keys locally and copying them to the servers?

This is the first thing I tried, however it requires too much effort compared to other approaches. Since I am working with different distros the small differences in locations and how the keys generated makes it more difficult then it should be. In this particular case Redhat/CentOS uses NSS enabled version of Openswan.

That's not to say that it cannot be done. I did it, but it does nothing to address the fundamental problem.

Some interesting discussion of what "randomness" entails

Posted Mar 30, 2012 13:55 UTC (Fri) by fmyhr (subscriber, #14803) [Link]

in comments on
http://www.schneier.com/blog/archives/2012/03/can_the_nsa...

Particularly comments by Robert T and Clive Robinson.

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 18:38 UTC (Fri) by rahvin (guest, #16953) [Link] (13 responses)

After reading the comments posted so far I have a couple questions.

Like a previous question I have to wonder why the kernel random number generator hasn't been hammered into as bulletproof a generator as possible (maybe it has and I'm just misreading the comments)?

And more importantly, with as important as randomness is to encryption why on earth there isn't a true hardware random number generator (an oscillating circuit or micro machine or something) in every CPU, or separately mounted to every single motherboard?

It would seem to me that this is so bloody important that I'm astonished it's not already been addressed in such a manner that there is a solution that's been tested and verified for a decade. Without valid randomness encryption is darn near worthless. So I'm absolutely astounded that this hasn't been addressed completely a long time ago.

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 18:54 UTC (Fri) by drag (guest, #31333) [Link]

> Like a previous question I have to wonder why the kernel random number generator hasn't been hammered into as bulletproof a generator as possible

Well I think that one of the reasons why /dev/random is so slow to generate new data is because they tried to make it as 'non-deterministic' as possible.

This sort of stuff wasn't always a issue with Linux. Older kernels would generate a lot more /dev/random, so much so that it was rarely a problem. However people found severe flaws with it and the amount of data produced and type of data that Linux sourced to generate the entropy was severely cut back.

Combine modern kernels with virtual machines and mostly idle servers then it sometime can get acute.

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 19:21 UTC (Fri) by rwp (guest, #75755) [Link] (2 responses)

Personally, I would trust the randomness of a software algorithm that I could read and review to the output of a completely opaque hardware chip. Software requires environmental input, of course, which should also be observable.

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 21:43 UTC (Fri) by khim (subscriber, #9252) [Link] (1 responses)

This argument can be used to discourage AES-NI, but unfortunately it does not fly when we are discussing RNG. Software literally can not create randomness. It's deterministic - that's the whole point. Sure, different pieces of hardware have different reliability WRT to predictability, but some hardware is always needed.

As this point we are down to the randomness generated by Ethernet, Keyboard and Mouse and I fail to see where the idea that Ethernet (especially emulated one in VM) can generate better randomness then dedicated hardware comes from.

Russell: Sources of Randomness for Userspace

Posted Apr 3, 2012 12:46 UTC (Tue) by rwp (guest, #75755) [Link]

Yes, of course. True randomness requires environment input. My point is that randomness you can use also requires trust, and trusting an opaque source doesn't cut the mustard. This is why using lava lamps to create random seeds makes so much sense - it's not just someone being cute. If I want to make a truly random seed today, I don't use my computer at all. I observe some external random event(s) and type in the results.

After seeding, I want my prng to be software, not hardware.

Russell: Sources of Randomness for Userspace

Posted Mar 30, 2012 22:15 UTC (Fri) by wahern (subscriber, #37304) [Link] (8 responses)

Nobody should be using /dev/random, not even for generating keys. It basically just uses a bunch of haphazard heuristics to know when it has been "drained" of entropy. These hueristics work about as well as the OOM killer (i.e. they appear to work most of the time but are easily broken, the authors know this, and nobody actually cares because it doesn't really matter given the express tradeoffs.)

Use /dev/urandom because it's going to be _at least_ as strong as /dev/random. Both fundamentally use the same cryptographic primitives for mixing entropy, and that's all that matters. If that's broken, it hardly matters that you've blocked for three seconds waiting for some disk activity. Everybody but Linux has a /dev/random that doesn't block, including OS X, FreeBSD, and OpenBSD.

Linux doesn't use carefully constructed PRNGs like Fortuna or Yarrow--for various reasons, including Linux's epic case of NIHS--but their stubbornness has paid off in the sense that they've goaded researchers into breaking it and it hasn't happened yet. So in that sense, it is quite bulletproof.

Russell: Sources of Randomness for Userspace

Posted Mar 31, 2012 2:08 UTC (Sat) by wahern (subscriber, #37304) [Link] (7 responses)

I hasten to add, I'm not arguing it's "safe" because nobody has broken it yet, but because researchers have actually taken the opportunity to try to break it and have so far been unsuccessful. (The difference being, I could concoct some random algorithm and challenge people to break it, and in two weeks claim "nobody has broken my ultra secure PRNG" when nobody has even bothered; then I could throw in something lame like, "and I did some statistical analysis which showed a random distribution, so it must be secure." This is how commercial companies and bloggers sell their snake oil.)

Also, over the years the maintainers (like Ts'o) have improved things when actual issues were pointed out.

That's not to say it won't be broken tomorrow, or that it's as good or better than, say, Fortuna.

Russell: Sources of Randomness for Userspace

Posted Mar 31, 2012 10:30 UTC (Sat) by drag (guest, #31333) [Link] (6 responses)

Well.

What do you use for generating your keys?

Russell: Sources of Randomness for Userspace

Posted Apr 2, 2012 0:44 UTC (Mon) by wahern (subscriber, #37304) [Link] (5 responses)

On Linux, just /dev/urandom. If someone is generating enough keys of enough importance that he feels the carnal urge to use /dev/random, yet somehow can wait around for seconds or minutes to generate each and every key, then something is amiss. If someone provides a CA or some such service, then ensuring that the system has a hardware RNG (like recent Intel and AMD chips plus many of their chipsets over the years, Via chips for years, Hi/Fn crypto chips, and even AMD's Geode embedded lineup) is far more important and provably useful.

Consider that Fortuna, designed by two experienced cryptographers, specifically forswore guesstimates of entropy (as /dev/random uses) because its highly suspect. Some of the same authors who designed Fortuna previously designed Yarrow, the main difference being that while Yarrow tried to conservatively incorporate the practice of entropy guesstimating, Fortuna discards it entirely. Entropy guesstimating doesn't give cryptographers the warm fuzzies; it gives them the willies, and Schneier and Ferguson eventually did something about it.

The only practical difference between /dev/random and /dev/urandom is immediately after a reboot, and without any PRNG state having been saved. For example, right after a fresh install. Anytime after the pool has been seeded with any considerable amount of entropy, the two are identical, except one blocks haphazardly. Anytime afterward, if there's a concern that someone could deduce the seeding material from the output of /dev/urandom, then /dev/random is already screwed because they use the same cryptographic primitives used in similar ways.

Instead of using /dev/random, just make sure the pool is as well seeded as possible immediately after startup. Even better, use hardware that has a built-in RNG, and especially in the case of Linux (since RNGs generally aren't high on the list of devices Linux keeps up-to-date with) make sure Linux uses it.

Also, I see no reason to ditch /dev/urandom in favor of different kernel modules or user-land generators. The reason being that in most cases the security of your PRNG--excluding pathological brokenness--is far less important than running a tight ship, from a sysadmin standpoint. Any PRNG is useless if your box is hacked. So better to keep your software footprint to a minimum.

Russell: Sources of Randomness for Userspace

Posted Apr 2, 2012 5:00 UTC (Mon) by drag (guest, #31333) [Link] (4 responses)

Well I disagree on urandom vs random. There are a few reasons:

* On my VMs they were literally starved of entropy as indicated by /proc/sys/kernel/random/entropy_avail. I am not sure what that value means but when it's 32-128 I can't imagine that repeating what is available 400 times via reading from /dev/urandom is anywhere close to good enough, even for casual usage. It seems to me that blocking is a valid sanity check.

As a example I have a virtual machine, which is not used for much, it has been booted for over 2 days and the entropy_avail is at 152. Seeing how things like SSH keys are generated at first boot up then it has to be a disaster from a correctness standpoint for running Linux virtual machines.

If the entropy_avial was always at over 2000-3000, which is going to be typical on real hardware with a human user, then urandom is certainly going to be as good as /dev/random. Depending on urandom seems to me to be playing russian roulette since it isn't going to help your application know that Linux's entropy pool is in a terrible state.

* I am loath to change defaults for a a number of real reasons (not all good). In Debian ipsec key generation stuff goes to /dev/random and retries over and over again until it gets enough data. With CentOS the same ipsec keygen program just bails out with a error immediately if it can't generate a key with /dev/random. Taking a educated guess; I expect that Redhat systems displays this behavior due to regulatory and/or certification purposes.

The solutions to this seems to be:

A) Don't trust Linux in a VM to generate keys for you unless you have validated the configuration for correctness. (such as using the entropy network daemon as mentioned above in a same manner, or using virtio_rng)

B) If you actually have a reason to care about correct keys then use hardware generator and make sure Linux and/or your software is taking advantage of them. This can present a number of unique challenges and depending on the industry you are in can be very expensive, but you have to do what you have to do.

(on a side note: What I am playing around with now certainly does not justify this level of paranoia, but I absolutely want to know how to do things right if I do have a need in the future.)

Russell: Sources of Randomness for Userspace

Posted Apr 2, 2012 6:13 UTC (Mon) by Cyberax (✭ supporter ✭, #52523) [Link] (1 responses)

You don't need more than 16 bytes of entropy, really. You only need enough entropy to seed the PRNG.

Russell: Sources of Randomness for Userspace

Posted Apr 6, 2012 14:18 UTC (Fri) by nix (subscriber, #2304) [Link]

Note that every exec() sucks more data out of the pool, to seed the AT_RANDOM auxv entry.

Russell: Sources of Randomness for Userspace

Posted Apr 2, 2012 7:20 UTC (Mon) by dlang (guest, #313) [Link]

> I am not sure what that value means but when it's 32-128 I can't imagine that repeating what is available 400 times via reading from /dev/urandom is anywhere close to good enough, even for casual usage.

you do not understand what urandom does

urandom does not repeat the data from random, it uses random data if it's available, and if it's not it devolves into a PRNG, which is still pretty secure (as long as it had enough randomness at some point in the past to randomize it's initialization)

Russell: Sources of Randomness for Userspace

Posted Apr 5, 2012 20:20 UTC (Thu) by samroberts (subscriber, #46749) [Link]

Unless its changed a lot since I last read the source, /dev/random and /dev/urandom are the same, they both use a PRNG to output values based on an internal state that is updated as the devices are read or written.

The only difference is that the kernel keeps a wild-assed guess about how many bits of entropy are in the pool. This is information that is impossible to know, it can merely be guessed, though it also does a bit of checking for obvious statistical non-randomness. Since its possible to have 0 entropy data that is indistinguishable from random, this check is a pure heuristic.

What /dev/random does differently is that when you read, it checks its current guess as to the entropy, and won't give you anything if the number is small.

I agree with the advice to always use /dev/urandom. If you really want to be sure you are using random data, you should be using a hardware RNG, not the output of a PRNG, and you shouldn't be assuming that random is better based on some heuristic guesses that aren't backed up by anything.

The reason its a default for some things is ass-covering, as far as I can tell: if you always appear to be doing the most conservatively secure thing, you can't be criticized later.

The issues in the implementation described in http://www.pinkas.net/PAPERS/gpr06.pdf have hopefully been fixed

Some of the attacks are fun, using /dev/random allows you to be DOSed by anybody who can cause the systems entropy to be continually depleted through reading of /dev/urandom. :-)

Russell: Sources of Randomness for Userspace

Posted Apr 5, 2012 17:39 UTC (Thu) by gmaxwell (guest, #30048) [Link] (1 responses)

I've actually had problems on systems due to _running out of entropy_.

Picture this— a lightly loaded multiuser shell system that does a little SSL webserving. Incoming SSH connections intermittently hang for a second or so.

The problem: sshd is using /dev/random, the kernel has a fixed size* random number pool of only four kilobits, and every SSL request eats a few hundred. On many headless systems the 100hz timer is the only source of entropy for the pool, because paranoia called for the removal of random contributions from most network drivers (because an external party controls them).

Modifying ssh to use urandom would have broken the distribution packages an inhibited adding security updates in the future.

The solution was to toss haveged on the system, it does a good job keeping the pool full, but it should would be nice if the kernel had a pool which wasn't so insanely small.

*The size used to be variable, but there was an exploit(!) related to this capability... so it was fixed. But that was back when just about every driver contributed to the pool, so the small size wasn't quite so crazy.

Russell: Sources of Randomness for Userspace

Posted Apr 5, 2012 20:19 UTC (Thu) by dlang (guest, #313) [Link]

that is a case where the application should really be using /dev/urandom, not /dev/random

the administrator has the choice of either recompiling the package, adding additional randomness source, or tricking the application by renaming /dev/random to something else and making /dev/random be a link to /dev/urandom