Subject: Re: init.d/urandom : saving random-seed
Date: Saturday 31st July 2010 11:55:18 UTC (over 7 years ago)
Hi Henrique -- This is to answer the excellent questions you asked at http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=587665#81 Since that bug is now closed (as it should be), and since these questions are only tangentially related to that bug anyway, I am emailing you directly. Feel free to forward this as appropriate. > 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. This property is a core design requirement of the PRNG, and has been for ages. Note that writing to /dev/random requires no privileges, which makes sense in light of this property. > 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) ? As is so often the case in the security / crypto business, the answer depends on your threat model. The demands placed on a PRNG vary wildly from one application to another. Interesting use cases include: a) low-grade randomness: For non-adversarial applications such as Monte Carlo integration of a physics problem, almost any PRNG will do. Even a LFSR would do, even though a LFSR can easily be cryptanalyzed. The point is that nobody is going to bother attempting the cryptanalysis. 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 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. 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 to help you play "battleship" or "go fish" against a ten-year-old opponent. If you use the same 'random' numbers after every reboot, the opponent is going to notice. You are going to lose. In more-demanding situations, against an opponent with more skill and more motivation, you are going to lose even more miserably. > 3. What is the optimal size of the seed data based on the pool size ? While we are on the subject, let me point out a bug in all recent versions of init.d/urandom (including the current "sid" version as included in initscripts_2.88dsf-11_amd64.deb) : The poolsize as reported by /proc/sys/kernel/random/poolsize has units of _bits_ whereas the random-seed filesize has units of _bytes_. It is a bug to directly compare these numbers, or to set one of them based on the other. There needs to be a conversion factor, perhaps something like this: (( DD_BYTES = ($POOLSIZE + 7)/8 )) Now, to answer the question: It suffices to make the random-seed file contain the same number of bits as the PRNG's internal state vector ("poolsize"). Call this the BBJR size (baby-bear-just-right). On the other hand, it is harmless to make the random-seed file larger than it needs to be. In contrast, using the size of the random-seed file to reset the PRNG's poolsize is a bad idea, especially if the random-seed file is (intentionally or otherwise) bigger or smaller than the BBJR size. Semi-constructive pseudo-suggestion: *IF* we want to keep track of the poolsize, it might make more sense to store it separately and explicitly, in its own file. This would make the code simpler and more rational. On the other hand, I'm not sure why there is *any* code in init.d/urandom for saving or setting the poolsize. Chez moi /proc/sys/kernel/random/poolsize is read-only. Indeed I would expect it to be read-only, since changing it would have drastic consequences for the internal operation of the PRNG, and looking at random.c I don't see any code to handle such a change. So the real suggestion is to eliminate from the Linux init.d/urandom all of the code that tries to ascertain the size of the random-seed file and/or tries to set the poolsize. (For non-Linux systems, the situation may or may not be different. I have no comment on that.) > 4. How dangerous it is to have functions that need randomness (like > encripted network and partitions, possibly encripted swap with an > ephemeral key), BEFORE initializing the random seed ? An unseeded PRNG is unsuited for any purpose except possibly the lowest of low-grade non-adversarial applications. It is grossly unsuited for any security-related application. The security literature contains many examples of serious attacks based on figuring out the state of the victim's PRNG. 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 meant to be used as an unseeded PRNG, it should be renamed to /dev/nonrandom so that users are not deceived. > 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. 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 /dev/urandom but rather of /dev/random, to serve as a buffer in cases where the incoming supply of entropy accumulates slowly but the outgoing demand is subject to sudden peaks. I recommend not messing with the built-in poolsize. > a) Is it better to seed the pool as early as possible and risk a larger time > window for problem (2) above, instead of the current behaviour where we > have a large time window where (4) above happens? Seeding should happen as soon as possible. Seriously, any PRNG that makes any pretense of security should block or throw an error if it is used before it is seeded. I don't see how early seeding makes problem (2) any worse. Late seeding causes all sorts of problems. Seeding should happen -- after the random-seed file becomes readable, i.e. after the relevant filesystem is mounted. -- as soon thereafter as possible Note that the filesystem can be readonly at this point. Read/write is OK too. Note that it should be considered an error to mount something else on top of /var, using /var as a mountpoint. Ditto for the other directories in the path leading to random-seed, typically /var/lib/urandom/random-seed. Such a mount is bad because it makes it impossible to update the relevant version of random-seed (unless somebody carefully unmounts the offending filesystem first, and there's no code to do that). 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. > b) Is it worth the effort to base the seed file on the size of the pool, > instead of just using a constant size? If a constant size is better, > which size would that be? 512 bytes? 4096 bytes? 16384 bytes? Yes, the size of the random-seed file should be set according to the poolsize (but not vice-versa). > c) What is the maximum seed file size we can allow (maybe based on size of > the pool) to try to avoid problem (1) above ? This is a non-problem. Just use the poolsize to determine the file size. This will never cause a problem for the PRNG. At present the filesize should be 512 bytes i.e. 4096 bits. This is likely to remain so for the foreseeable future. If the filesystem cannot handle a file of this size, then we are talking about a highly specialized application, requiring detailed engineering, quite outside the scope of the standard initscripts. 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. 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.