> From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of Enzo > Michelangeli > Sent: Tuesday, January 04, 2005 7:50 PM > > This "entropy depletion" issue keeps coming up every now and > then, but I still don't understand how it is supposed to > happen. If the PRNG uses a really non-invertible algorithm > (or one invertible only with intractable complexity), its > output gives no insight whatsoever on its internal state. > I see much misunderstanding of entropy depletion and many misstatements because of it.
It is true you don't know what the internal state is but the number of possible internal states tends to reduce with every update of the internal state. See "Random Mapping Statistics" by Philippe Flajolet and Andrew M. Odlyzko (Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, Houthalen, Belgium, Pages: 329 - 354, year 1990) for a thorough discussion. The jist is that a well behaved state update function for a PRNG will have one very long cycle. This cycle will be shorter than the number of possible values that the state can hold. States not on the cycle are on branches of states that eventually land on the cycle. Flajolet and Odlyzko go on to show that the expected cycle length for a 1000 bit state will be around 2^500 iterations. So, you start your PRNG by filling the state with 1000 bits of real entropy. You have 2^1000 possible states. You use your PRNG and update the state. Now, there are a certain number of states that the PRNG cannot be in. After one state update, the PRNG cannot be in the states at the ends of the chains of states branched off from the aforementioned cycle. This means that, after one state update, you have slightly less than 1000 bits of entropy. When you update the state again, you now have more states that the PRNG cannot be in, thus reducing your entropy again. Every time you use your PRNG, you reduce your entropy in this way and you keep on doing so in an asymptotic way until, after many many iterations, you are close enough to 500 bits that you don't care anymore. In the real world, our PRNG state update functions are complex enough that we don't know if they are well behaved. Nobody knows how many cycles exist in a PRNG state update function using, for example, SHA-1. You run your PRNG long enough and you may actually hit a state that, when updated, maps onto itself. When this occurs your PRNG will start producing the same bits over and over again. It would be worse if you hit a cycle of 10,000 or so because you may never realize it. I don't know of any work on how not-so well behaved PRNG state update function lose entropy. I figure the state update functions we as a community use in what we consider to be well designed PRNGs probably have multiple long cycles and maybe a few scary short cycles that are so unlikely that nobody has hit them. I don't even know what multiple cycles means for entropy. Because of the lack of knowledge, cryptographic PRNGs have more state than they probably need just to assure enough entropy - at least that is one thing I look for when looking at cryptographic PRNGs. -Michael Heyman --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
