On Sat, 31 Jul 2010, John Denker wrote: > This is to answer the excellent questions you asked at > http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=587665#81
Thanks. I also got another reply, and your answers mostly match it. > > 1. How much data of unknown quality can we feed the random pool at boot, > > before it causes damage (i.e. what is the threshold where we violate the > > "you are not goint to be any worse than you were before" rule) ? > > There is no possibility of making things worse. It is like shuffling > a deck of cards: If it is already shuffled, shuffling it some more > is provably harmless. [...] > > 2. How dangerous it is to feed the pool with stale seed data in the next > > boot (i.e. in a failure mode where we do not regenerate the seed file) ? [...] > b) current /dev/urandom: The consensus among experts is that /dev/urandom > is routinely used in ways for which it is not suited. See my previous > email, or refer to > http://www.pinkas.net/PAPERS/gpr06.pdf We could well audit Debian for this. But the best way of fixing a Debian system to be more secure as far as the quality of the randomness used by a random user application will be, AFAIK, is to simply get a medium or high bandwidth TRNG, and use rng-tools to constantly reshuffle the pool, doing batched large entropy credits (to cause as many catastrophic reseeds as possible). That improves the quality of /dev/urandom output. I don't have a proper TRNG at the moment, but if I manage to get one (lost the opportunity to get one a few months ago :-( ), I will improve rng-tools (the one used in Debian and Ubuntu) to be better suited to that application, move it to /sbin, and provide an one-shot mode suitable for initramfs usage to do high-quality early seeding. > c) high-grade randomness: For high-stakes adversarial applications, > including crypto and gaming, you really ought to use a TRNG not a > PRNG. In this case, no state is required and no seed is required, > so the question of how to preserve the state across reboots does not > arise. Constructive suggestion: for high-grade applications, use > Turbid: http://www.av8n.com/turbid/ > > To repeat: For serious applications, I wouldn't trust /dev/urandom at all, > and details of how it gets seeded are mostly just re-arranging the deck > chairs on the Titanic. The question is not whether this-or-that seed > preservation policy is "safe". The most you can ask of a seed preservation > policy is that the PRNG after reboot will be _not worse_ than it was before. > > Now, to answer the question: A random-seed file should never be reused. > Never ever. Ok. Let's differentiate writing to /dev/urandom WITHOUT credit (write to that device) and with entropy credit (what rng-tools does using IOCTLs). Writing without credits is supposed to be always safe, even if you write twice the same data. If the kernel got any entropy from anywhere else, you won't dilute the pool and you're not worse off, correct? So, if you can never be worse off, why shouldn't we allow for a *failure-mode* where we could possibly reuse the random-seed file? After all, userspace CANNOT completely seed the Linux kernel RNG, we can never reset its state using writes (it just shuffles the pool without any entropy credit), and even a very large entropy credit using IOCTLs will cause just a catastrophic reseed, which STILL uses the some of the current state of the pool anyway AFAIK. If we cannot tolerate this failure mode, we will never be able to use anything but a TRNG to do early pool shuffling, and must retain what we have right now (we shuffle after we have write access, so that we can immedialely remove the seed file). > Reusing the random-seed file makes the PRNG very much worse than it would > otherwise be. By way of illustration, suppose you are using the computer See above. Note that in this thread we are concerned only with writes to /dev/urandom, not PRNGs in general. /dev/urandom, as far as we've been told (and as far as I could understand from the Linux kernel code) CANNOT be truly reseeded, it can only be shuffled. > On the other hand, it is harmless to make the random-seed file larger than > it needs to be. Let's just use a static size of 512 bytes at late init time, and of 2048 bytes at shutdown time, then. Makes for easier scripts, that only need dd and nothing else. We get those bits from /dev/urandom, so it doesn't matter at all if we will drain 4096 bits or 16384 bits from it when we're about to shutdown/reboot any normal system (and Debian isn't suitable for stuff that needs to reboot in less than a second anyway). We will have a lot of shuffling seed data available at the next boot for the common case without failure modes, and we will close the "use same seed file twice" window during late boot, by switching the (already used) seed file with a new seed file without draining more entropy than the strictly needed during boot. That should sort-of future proof us if the kernel increases the pool size. Alternatively, we could just use 512 bytes for everything by default, and have that parameter configurable in /etc/default/random. > Sometimes /dev/urandom is advertised as a "cryptographically secure PRNG". > If that's what it is supposed to be, it should block or throw an error if > it is used before it is seeded. To say the same thing the other way: if It is considered to be always seeded, I think. Its seed (the primary pool) gets a few bits of entropy right away, from disk activity and other sources. It doesn't matter for this discussion how disputable the randomness of these bits are, because unless you're going to remove such entropy contributions from the kernel, the pool will *always* already have something inside when control is handled to userspace. So, unless one is going to do kernel surgery, urandom will be already "initialized" when control is handled over to userspace. We cannot trust the quality of any random numbers at that time, except (*maybe*) in very specific platforms and setups. > > 5. Is there an optimal size for the pool? Does the quality of the > > randomness > > one extracts from the pool increase or decrease with pool size? > > If the poolsize is too small, all sorts of bad things happen. It can hold less entropy, for sure. But I am certainly NOT going to advocate increasing pool size over the default 512 bytes (which would help the kernel handle sudden spikes of entropy requests), because a smaller size probably helps protects you from overestimation of the entropy entering the pool (as we keep adding data to it even after it is full, thus eventually we will really have that much entropy in the pool, and the larger the pool, the more time it will take for that to happen). In other words, I don't know enough math and RNG theory to prove that a 8192 or 16384-bit pool would not, in fact, have worse performance quality-wise because we are NOT sure of the quality and real entropy inside the data we will feed it, and also if we wouldn't be worse off at early system lifetime, where the quality of the pool state is really dubious. One could always have a init pool (small), and swap it with a large pool later, but I doubt people would accept such a change in the kernel unless it is backed up by some serious research that proves it is well worth the complexity on scenarios for which "get a real TRNG" isn't an answer. > The built-in poolsize is 512 bytes i.e. 4096 bits which is plenty big > enough for PRNG purposes. This size is not based on the needs of It is not just used for PRNG, though. It is used (through /dev/random and internal kernel interfaces) to generate session IVs and keys. > I recommend not messing with the built-in poolsize. In that, we agree. I would appreciate if someone from academia did a throughout study of the entire random subsystem in Linux and FreeBSD, based on *recent* kernels :-) Maybe someone already did and I don't know about it. I still need to read that paper you mentioned. > Seeding should happen > -- after the random-seed file becomes readable, i.e. after the > relevant filesystem is mounted. > -- as soon thereafter as possible Agreed, but that DOES mean we have a failure mode where the seed file can be used twice to stir the pool, should we crash/reboot before filesystems are mounted read-write. And that failure mode is not rare. It will happen when fsck finds anything wrong in the / partition, and that is not nearly as uncommon as one would hope it to be. So, I'd like to get an confirmation about it, since there was apparently some contraditory information on your reply about this issue (I probably misunderstood what you mean, but still, please clarify). > Note that the filesystem can be readonly at this point. Read/write is > OK too. And we should move the seed file to somewhere inside /etc or /lib. It is as simple as that. /var cannot be used for any data you need at early userspace. > Updating the random-seed file should happen during boot > -- after the random-seed file becomes writeable > -- as soon thereafter as possible > > Updating should happen again during shutdown, if possible. Agreed. > Embedded systems, if they want to have any pretense of security, need to > have either: > a) enough persistent local storage to hold the random-seed, or > b) a hardware TRNG that collects real entropy, so that no seed is needed. Any embedded system worth its price has a TRNG inside somewhere. Servers and workstations can add TRNGs to their internal USB ports, or you could also use that PoS called a TPM if you're going to trust black-box unreviewed designs from potentially hostile sources, and a complex and very annoying userspace software stack to get your hands on the random bits. > For systems that boot from read-only media, such as diagnostic and emergency > maintenance CDs, there is a serious problem, with no entirely satisfactory > solutions that I know of. Suggestions would be welcome. Well, nowadays datacenters would boot an hypervisor, do all the proper RNG initialization for the hypervisor (over the network from an entropy source box, if needed), and have the hypervisor provide a suitable way for the VMs to ask for initial random data to seed themselves during kernel initialization. I believe Linux already allows that on very recent kernels. What I could do to help other scenarios is move rng-tools to /sbin. Other suggestions are welcome. -- "One disk to rule them all, One disk to find them. One disk to bring them all and in the darkness grind them. In the Land of Redmond where the shadows lie." -- The Silicon Valley Tarot Henrique Holschuh _______________________________________________ Pkg-sysvinit-devel mailing list [email protected] http://lists.alioth.debian.org/mailman/listinfo/pkg-sysvinit-devel
