Kyle Hamilton wrote: > On Thu, Aug 7, 2008 at 6:59 AM, David Schwartz > <[EMAIL PROTECTED]> wrote:
> > Kyle Hamilton wrote: > >> If the pool is seeded once, the "randomness" will be random for as > >> long as the amount of entropy in the seed holds out. After this, the > >> numbers generated won't really be random. > > Right, but they will be cryptogrpahically secure. Forever. > Uh, no. Uh, yes. > If you seed it with 1 bit of entropy, then there's only 2**1 > possible output chains. You cannot "seed it with 1 bit of entropy". > Entropy is observation of chaos, which is > supposed to make all possible values of the entropy pool equally > possible -- and the less entropy you stir in, the more likely it is > that someone who figures out what's come before is going to be able to > figure out what's going to come in the future. What you are claiming can happen -- that the /dev/urandom pool can produce cryptographically-secure random numbers but then run out of entropy -- is impossible. It cannot happen. If you could seed the pool with 1 bit of entropy, it would never produce any cryptographically-secure random numbers. If you seeded it with 64-bytes of entropy, it would produce an effectively unlimited amount of cryptographically-secure random number, well in excess of 2^64 bytes. This is not an accident or artifact. This is the specific design intention of the implementation. It's as assured by the implementation as RSA assures that its operations are irreversible. > >> The only way to guarantee that your numbers are truly > >> cryptographically secure is to use /dev/random and deal with the fact > >> that it will block until there's been enough entropy seeded into the > >> randomness pool. > > > > Nope. That does not "guarantee" that the numbers are truly > cryptogrpahically secure. There could be a bug in the /dev/random > implementation. A cosmic ray may cause the PRNG software to be bypassed. > > > > If you get to argue that there might be a weakness in the PRNG > algorithm such that it does not generate cryptogrpahically-secure > numbers even if it was seeded, then I get to argue that there > might be a weakness in your RNG alogorithm. > Technically, if you want to absolutely guarantee that you have truly > cryptographically secure numbers you should perform thermodynamic > analysis of case air-flows, or measure the periodicity of the release > of electrons or photons from radioactive nuclei, or directly measure > other phenomena that are nondeterministic. The /dev/random > implementation measures as much of the nondeterministic phenomena as > is possible in a typical computer system, and uses that to seed the > random number generator. > /dev/random and /dev/urandom have historically shared the same > implementation. The difference is that /dev/random blocks when it has > calculated that its entropy pool is exhausted, and /dev/urandom does > not. Right. So /dev/random tries to provide truly random numbers while /dev/urandom tries to provide only cryptographically-secure pseudo-random numbers. > >> Otherwise, many random number generators use a > >> linear-feedback shift register with a periodicity of 2**56. That's > >> approximately the same amount of keyspace as DES, and the output over > >> multiple successions of readings of 2**56 bytes will repeat and not be > >> suitably random. > > > > That seems pretty boneheaded to me, considering how trivial it > is to create PRNGs with much higher periods. In any event, > Linux's /dev/urandom implementation has a periodicity of way over > 2^64 bytes. > Sure, it's possible to create PRNGs with much higher periods, but it's > rather difficult to create /good/ PRNGs with much higher periods. > Even then, though, all PRNGs have the property that their output is > deterministic... and "deterministic" is the antithesis of > "cryptographically secure". No, it is not. Deterministic is the antithesis of truly random. Deterministic is entirely compatible with cryptographically secure. Non-deterministic processes are one way to produce cryptographically-secure random numbers, but it is not the only way. It's like a one-time pad, it is easy to prove that it works and is secure, but is not always the best in practice. If you don't use it, you risk theoretical vulernabilities, but you choose mature, well-researched algorithms to mitigate that risk. > >> (If an attacker can figure out the state of your > >> PRNG, the attacker can figure out your next-generated "secret" > >> randomness. This is why the Debian debacle was so serious, and why > >> only a few thousand possible keys were generated by the vulnerable > >> implementations -- the randomness wasn't.) > > > > The whole point of the design of Linux's /dev/urandom > implementation is that if it was ever seeded, no matter how much > output you have made, an attacher can never determine the state > of your PRNG. This was an explicit design goal. > The whole point of cryptosystem implementation is so that if the key > is properly kept secret, no matter how much material is encrypted > under the key, an attacker can never determine the key or the > plaintext. This is an explicit design goal. > Of course, no cryptosystem has ever been found to have an unknown > weakness or buggy implementation, right? That is the risk of every system. If all you're trying to say is that /dev/urandom has the same risks as every other cryptograhic implementation of every algorithm, then fine. But you are inventing some special "run out of entropy" risk. There is no such special risk. It's the same as the risk that someone might find a faster way to factor primes is a risk for RSA. That is, the implementation is carefully designed and tested to control this well-understood risk. It is not some vulnerability that normal users of the algorithm need to worry about, except in the same sense that they worry about prime factoring with RSA. (For example, with RSA, you need to constantly evaluate whether your key size is still appropriate.) > >> I'd certainly like to see references to the contrary, if they exist -- > >> my references are the Handbook of Applied Cryptography and Applied > >> Cryptography 2nd Ed. > > > > Linux's /dev/urandom implementation was specifically made such > that if it was ever seeded, no amount of known output would > compromise the state of the PRNG. > > > > So long as it is initially seeded, the only risk is that the > algorithm has some unknown weakness or bug. > I'll vote "unknown weakness". Give me /dev/random and blockage any > day, and/or have me seed the PRNG with the timing of my keystrokes (a > la PGP 2.x) or mouse-cursor movements (a la PGP 5.x+), or something > else. Fine, but then make clear that your argument is not about any known vulnerabilities, but a specific claim that the algorithm might not actually meet its design goals. > Entropy is really the only way to protect against PRNG bugs. And it's > also really the only way to work around the deterministic nature of > the PRNG. > > -Kyle H This really is comparable to the view that no public-key encryption algorithm should ever be trusted. In principle, every such algorithm can be reversed. It's almost equivalent to the view that only a one-time pad should be used as an encryption algorithm, but not quite, as there is often no way to use a one-time pad and there is rarely no way to get sufficient true randomness. In case you don't have a good idea how the /dev/urandom PRNG works, it's roughly like this: 1) There's a pool of entropy. It's way too large to brute force. 2) That pool is iterated with a LFSR type algorithm with a ludicrously high period. It would take the known age of the universe to get it to repeat. 3) A secure hash algorithm runs over the pool after each iteration. The output of the secure hash algorithm is much smaller than the size of the pool. Some of the output of this secure hash algorithm is used as the output random number. Provided the input seed is sufficient, any attacker who tries to attack this algorithm, regardless of the amount of output he had or how long the algorithm has run (assuming much less than its period, of course) must exploit some weakness in the secure hash algorithm. The secure hash algorithm used is SHA1, which is as well-studied as almost any other cryptogrpahic algorithm, and it has no known (or even suspected, AFAIK) relevant weaknesses. DS ______________________________________________________________________ OpenSSL Project http://www.openssl.org Development Mailing List [email protected] Automated List Manager [EMAIL PROTECTED]
