On Thu, Aug 7, 2008 at 6:59 AM, David Schwartz <[EMAIL PROTECTED]> wrote: > > Kyle Hamilton wrote: > >> David S: to my knowledge you're at least somewhat incorrect, and part >> of your advice is rather dangerous to rely upon (from a cryptographic >> theory perspective). > > You are at least somewhat incorrect too. > >> And yes, it is possible to "run out" the entropy pool. The amount of >> chaos that you stir in is the amount of chaos that you can pull out -- >> everything else is deterministic, and as the man page says there may >> be a theoretical way that the pseudorandom number generator can be >> attacked (though one is currently not known in the nonclassified >> literature) with the result that the keys generated will be >> predictable. > > This is correct, but doesn't conflict with anything that I've said. > >> If the pool is never seeded, the "randomness" won't ever be really random. > > Right. > >> 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. If you seed it with 1 bit of entropy, then there's only 2**1 possible output chains. 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. >> 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. >> 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". >> (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? > >> 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. 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 ______________________________________________________________________ OpenSSL Project http://www.openssl.org Development Mailing List [email protected] Automated List Manager [EMAIL PROTECTED]
