Re: init.d/urandom : saving random-seed
On 07/31/2010 09:00 PM, Jerry Leichter wrote: I wouldn't recommend this for high-value security, but then if you're dealing with high-value information, there's really no excuse for not having and using a source of true random bits. Yes indeed! On the question of what to do if we can't be sure the saved seed file might be reused: Stir in the date and time and anything else that might vary - even if it's readily guessable/detectable - along with the seed file. [1] This adds minimal entropy, but detecting that a seed file has been re-used will be quite challenging. A directed attack can probably succeed, but if you consider the case of a large number of nodes that reboot here and there and that, at random and not too often, re-use a seed file, then detecting those reboots with stale seed files seems like a rather hard problem. (Detecting them *quickly* will be even harder, so active attacks - as opposed to passive attacks that can be made on recorded data - will probably be out of the question.) I've been thinking about that. That approach might be even *better* than it first appears. By way of background, recall that a good design for the central part of a PRNG is: output = hash(key, counter) [2] where -- the hash is your favorite cryptographically strong hash function; -- the counter is just a plain old counter, with enough bits to ensure that it will never wrap around; and -- the key is unique to this instance of the PRNG, is unknown to the attackers, and has enough bits to rule out dictionary attacks. -- There should be some scheme for reseeding the key every so often, using real entropy from somewhere. This is outside of what I call the central part of the PRNG, so let's defer discussion of this point for a few moments. Note that this works even though the counter has no entropy at all. It works even if the attacker knows the counter values exactly. This is crucial to an analysis of idea [1], because I am not sure that the date/time string has any useful amount of entropy. Let's be clear: if the attacker knows what time it is, the data/time string contains no entropy at all. Now, if all we need is a /counter/ then the merit of idea [1] goes up dramatically. I reckon date +%s.%N makes a fine counter. Note that date is /bin/date (not /usr/bin/date) so it is usable very early in the boot process, as desired. This requires that all boxes have a working Real Time Clock, which seems like a reasonable requirement. Security demands that the key in equation [2] be unique on a machine-by-machine basis. This means that if I want my live CD to be secure, I cannot simply download a standard .iso image and burn it to CD. I need to -- download the .iso image -- give it a random-seed file with something unique, preferably from the output of a good TRNG, and -- then burn it to disk. I have very preliminary draft of a script to install a random-seed file into an Ubunto live-CD image. http://www.av8n.com/computer/randomize-live-cd Suggestions for improvement would be welcome. = So, let's summarize the recommended procedure as I understand it. There are two modes, which I call Mode A and Mode B. In both modes: *) there needs to be a random-seed file. The contents must be unique and unknown to the attackers. *) /dev/urandom should block or throw an error if it used before it is seeded *) early in the boot process, the PRNG should be seeded using the random-seed file _and_ date +%s.%N. This should happen -- after the random-seed file becomes readable -- after the Real Time Clock is available -- as soon thereafter as convenient, and -- before there is any need to use the output of /dev/urandom *) This is all that is necessary for Mode B, which provides a /modest/ level of security for a /modest/ level of exposure. As a first rough guess I suggest limiting exposure to 1000 hours of operation or 1000 reboots, whichever comes first. *) Mode A is the same as Mode B, but has no exposure limits because the random-seed is replaced before the Mode-B limits are reached. *) It is nice to update the random-seed on every reboot. This should happen -- after the random-seed file becomes writable -- as soon thereafter as convenient, to minimize the chance that the system will crash before the update occurs. *) The random-seed file should be updated again during shutdown. This allows recovery from a situation where the random-seed file might have been compromised. *) Updating fails if some wiseguy mounts a filesystem in such a way that the random-seed file that gets updated is not the one that will be used for seeding the PRNG. AFAICT Mode A depends on having the random-seed file in local writeable persistent storage, not on (say) a networked remote file system. In some cases the init.d/urandom script would have to be customized to locate the random-seed file on a
Re: init.d/urandom : saving random-seed
On Aug 1, 2010, at 10:34 AM, Henrique de Moraes Holschuh wrote: (Please keep all CCs). On Sun, 01 Aug 2010, Jerry Leichter wrote: file might be reused: Stir in the date and time and anything else that might vary - even if it's readily guessable/detectable - along Well, yes, we have several *guessable* sources of variable data available during early userspace that we could use. We can also distill them through sha256. But it would add very little variation across reboots of the same box, and that variation is easily guessable I discussed this in the rest of my message. Apparently I wasn't explicit enough. Consider the overall situation. We have a large number of systems out there. They reboot here and there. Each of them saves their previous PRNG state, and uses it on reboot. Sometimes, the PRNG state is not saved, and a second reboot uses the same state. Attackers do *not* have access to the saved state. They *can*, however, observe the values produced by the PRNG. (In practice, they get a noisy, incomplete sampling through things like generated keys, but let's make the safe assumption that they see the complete stream.) Thus, they can easily check that a given system is generating the same sequence of values, so presumably didn't update its state. Thus, it will continue to produce the same values for a while (until it can gather enough entropy). Now consider the situation where a rebooting system stirs in the date and time, the MAC and IP addresses of the first couple of messages it sees, whatever. Given a properly implemented PRNG, the output stream will look nothing like the output stream it produced the last time around. (Flipping one bit of input to something like SHA-1 flips, on average, about half the output bits.) Sure, an attacker who *knew* the saved state could easily *guess* the low-entropy inputs, match what the system emits, and break security. But the problem here is entirely different: Recognizing that the stream it's seeing is the result of a small tweak applied to an unknown previous state. If someone an show a solution to that problem, I'll withdraw my suggestion. But I doubt any simple attack of this sort exists. If an attacker can't recognize systems that are re-using state, it has to try attacking all of them. Think about what that attack looks like. When the system works as it's supposed to, the state is saved over the reboot, so the reboot effectively never occurred. The extra guessable state makes no difference: In this situation, we're assuming that the PRNG is secure. When a restart does occur, the attacker is seeing two (or more) continuations from the same *unknown* internal state, using different guessable - assume known - small tweaks, and he must predict the future outputs. It's kind of a related-key attack, and doesn't look easy. In fact, if the number of tweaked bits is small, it doesn't look like there's even enough information available to solve it in principle. (With enough reboots without a state update, the bits accumulate.) But there are likely situations it's plausible. In those - use a true RNG. -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: init.d/urandom : saving random-seed
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
