| |||||||||||||
Russell: Sources of Randomness for UserspaceRussell: Sources of Randomness for UserspacePosted Mar 30, 2012 18:38 UTC (Fri) by rahvin (subscriber, #16953)Parent article: Russell: Sources of Randomness for Userspace
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.
(Log in to post comments)
Russell: Sources of Randomness for Userspace Posted Mar 30, 2012 18:54 UTC (Fri) by drag (subscriber, #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]
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] 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]
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]
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 (subscriber, #31333) [Link]
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]
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 (subscriber, #31333) [Link]
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]
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 (✭ supporter ✭, #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. :-)
|
|||||||||||||