| |||||||||||||
Russell: Sources of Randomness for UserspaceRussell: Sources of Randomness for UserspacePosted Mar 30, 2012 22:15 UTC (Fri) by wahern (subscriber, #37304)In reply to: Russell: Sources of Randomness for Userspace by rahvin Parent article: Russell: Sources of Randomness for Userspace
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.
(Log in to post comments)
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. :-)
|
|||||||||||||