entropy depletion

[Zooko O'Whielacronx]

I would love to have an information-theoretic argument for the security 
of my PRNG, but that's not what we have, and I don't think reducing the 
entropy_count by one bit per output bit gets us any closer to such an 
argument.

For starters, the entropy_count value before you output the bit is 
obviously not a measure of the real information-theoretic entropy in 
the PRNG's state.  It is a guess implemented by a simple algorithm (the 
"entropy estimator").  So if we set the resulting entropy_count after 
outputting one bit to be equal to the previous entropy_count - 1, we 
really have no justification for thinking that the resulting 
entropy_count is any closer to the true information-theoretic entropy 
than if you had set it equal to the previous entropy_count - 2.

On the other hand, I've haven't heard an information-theoretic argument 
that the output bit contains a whole bit of entropy.  There is a nice 
practical-cryptography argument that an observer gains a whole bit of 
information from seeing that output bit, but in pure 
information-theoretic terms an observer gains less than one bit of 
information from seeing that output.  So perhaps when you output a bit 
from /dev/random you ought to decrement entropy_count by 0.9 instead?

In general, I've heard no persuasive information-theoretic argument to 
justify the practice of decrementing the entropy_count by 1 bit per 
bit.  If that practice does indeed ever protect someone from a 
cryptanalytic attack on their PRNG, it will not be because the practice 
is Information Theoretically Correct, but because the 
entropy_count-bits-added-per-input-bit minus the 
entropy_count-bits-subtracted-per-output-bit were an engineering fudge 
factor that was turned up high enough to drown out the cryptanalytic 
weakness in the PRNG.

Of course using such a fudge factor has some other costs, including the 
cost of introducing new security risks.  I estimate that the chance of 
a successful attack due to timing attacks, induced failure, taking 
advantage of accidental failure, social engineering, etc. outweighs the 
chance of a successful attack due to cryptanalysis of the PRNG, which 
is why I use /dev/urandom exclusively [*, **].  You may weigh those 
trade-offs differently, but you shouldn't think that by decrementing 
entropy_count you are achieving information-theoretic security.

Regards,

Zooko

[*] Of course I have to be aware of the regrettable possibility that 
/dev/urandom has *never* been properly seeded and protect against that 
in user space.
[**] ... and the possibility that the operating system is re-using 
stored random state which it already used just before an unclean 
shutdown.


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com