On 10/19/2013 09:55 AM, Sandy Harris wrote:
Mixing in the clock makes a machine behave a bit differently each time it is rebooted. Again, there are better fixes such as mixing in a saved file, but again this is still worth doing.
These are reasonably cheap and done only once at boot time. They can do no harm and are useful in at least some cases, so worth doing.
OK, the next step in any such discussion is to ask the famous question, What's Your Threat Model (WYTM). Several different reasonable answers are possible. 1) At one extreme, we have the "no threat at all" model, aka the "non-adversarial" model. Examples include *) Doing a Monte Carlo integral in the context of a molecular dynamics calculation. The molecules are not going to attack our PRNG. They are not going to cryptanalyze it. Almost any PRNG is "random enough" for this purpose. *) Cooperative situations, such as friendly computers on a LAN, doing random exponential backoff as part of the layer-1 Ethernet CSMA/CD. Everybody has a shared interest in implementing the protocol properly, so even if they could break the PRNG they wouldn't want to. *) Et cetera. There are tons of examples in this category. A PRNG in category (1) could be considered "random" but not "secure". It is usually adequate to seed this type of PRNG with things like the MAC address, serial number, and time-of-day. 2) At the opposite extreme we have high-stakes adversarial applications, including military cryptography, banking, other high-value business communications, high-stakes gaming, etc. etc. etc. A PRNG in this category needs to be *secure* against a wide range of threats. For tasks in this category, seeding the PRNG with things like the MAC address, serial number, and time-of-day is nowhere near good enough. It is a band-aid or worse. It is security theater. It gives you "randomness" in some weak sense, but it does not give you security. The typical modern PRNG in this category consists of a seed, a counter, a hash function, and a reseeding mechanism. Sometimes there is a block cipher in there somewhere, but to a sufficient approximation this is the same basic architecture, just with a fancier hash function. So let's look in more detail at the threats against such a PRNG. *) For starters we have the threat of direct cryptanalysis of the output. If the preimage can be found, all further outputs will be known to the attacker, and probably all past outputs as well, over the span bounded by the nearest past and present reseedings. The feasibility of finding a preimage depends on the number of bits output by the PRNG. Therefore there should be a limit on the number of output bits between reseedings. *) Another type of threat is more indirect. For example, suppose the PRNG was seeded at boot time from the saved random-seed file. It may be possible for the attacker to find this, perhaps by sneaking a peek at an old backup tape or whatever. Such a threat is independent of the number of bits emitted by the PRNG. It is hard to say what it /does/ depend on, but in the absence of anything better, wall-clock time is a plausible proxy. Therefore there should be a time limit on how long a seed file is allowed to remain on disk before it is regenerated, and a time limit between reseedings of the PRNG. On 10/19/2013 01:37 PM, James A. Donald wrote:
Any system that needs crypto, communicates. Any system that communicates, sees events whose details are difficult to predict for anyone not in physical possession of the system.
Solution: Block for a short period after startup. Possibly a small number of systems will freeze up and fail to boot. This is almost always fixable by moving the blocking process in the bootup so that it no longer blocks other processes while it is blocked waiting for /dev/urandom, while /dev/urandom is blocked waiting for entropy.
That might be a "solution" in certain favorable cases, but it is nowhere near being a reliable, general solution. I can think of five failure modes in five minutes. Perhaps the most obvious is this: Suppose my system is sitting in a rack at some colocation provider. All the attacker needs to do is rent a box in the same rack, on the same LAN segment. Then he knows my MAC address, the time at which I booted up, and (to a good approximation) the arrival time of every network packet addressed to me. Similarly for my laptop on the corporate wifi network. The bad guy in the loft across the street has a nontrivial chance of figuring out everything he needs to know about my network traffic. If anybody has a proof that this cannot happen, please explain. Here's the only thing that has ever made sense to me: a) Any device that wants to have any security whatsoever needs to be able to store a seed, even when powered off. b) The seed needs to be provisioned on a per-device basis, much like the MAC address is provisioned. c) The seed needs to be big enough, randomly-chosen, and secret, very unlike the MAC address, RTC, and device serial number. _______________________________________________ The cryptography mailing list cryptography@metzdowd.com http://www.metzdowd.com/mailman/listinfo/cryptography