entropy depletion (was: SSL/TLS passive sniffing)

[Michael_Heyman at McAfee.com]

> From: owner-cryptography at metzdowd.com 
> [mailto:owner-cryptography at metzdowd.com] 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 majordomo at metzdowd.com