[Cryptography] randomness +- entropy

[Jerry Leichter]

On Nov 7, 2013, at 5:06 PM, Nico Williams wrote:
> [A] good PRNG does not
> allow an attacker that observes some of the PRNG's output to use it to
> guess future outputs.  Obviously the security of a PRNG will decrease as
> the attacker observes more and more outputs, but, given a random and
> unpredictable (high-entropy) initial state of N bits, the PRNG's
> resistance to such attacks will be reduced by one bit (N--) for each bit
> observed by the attacker!
This is a very weak and inappropriate definition of a PRNG.  The BBS generator *provably* can reveal many more bits than its seed without allowing an attacker to gain any significant advantage in computing either past or future outputs.  (The actual security statement is complicated to state.  Since BBS is way too slow to be practical, the details aren't all that interesting anyway.)  The proof, as is the case for all proofs we have in cryptography, is based on the difficulty of quadratic residue computation, which in turn is equivalent to factoring.

A practical generator that takes the one-way hash of its internal state using something like SHA doesn't have any strong proofs associated with it, but in practice is as "unpredictable" as the cryptographic algorithms it's use with even if way more bits of output than were in the initial seed.  (You still don't release the intact internal state, of course, as then anyone can compute the next value.)

This is why I don't like "entropy talk".  If you want to discuss *information theoretic security*, then, yes, you should (very carefully, see my comments earlier about the "entropy cost" of a three-way choice) count bits.  But no algorithm you're going to feed these values into comes with information theoretic security claims, just computational hardness claims.  (Well, OK, if you want to use the output to generate a one-time-pad, you want information theoretic unpredictability.  But that's not a particularly interesting case.)

> A PRNG with n bits of high-entropy state should provide as-good-as-
> brute-force protection.  Allowing the attacker to observe one output of
> the PRNG should reduce the attacker's work factor by 2^-n, not by a
> factor of 2!
A *good* PRNG releasing one bit should allow a "reasonable" (polynomially-bounded) attacker way less than that - essentially nothing.  The security claims for AES-128 state that with an unknown key K, the stream of values produced by E(K,0), E(K,1), ... - i.e., the values used in counter mode - are indistinguishable from a random sequence even as you approach 2^64 *blocks* of output.  Wouldn't you want your PRNG to have a similar security property?  And if you have such a property, what would be the point of a *stronger* requirement when generating an AES key?  (There *is* a point; see below.)

Granted, a cryptographically strong one-way or encryption function in your PRNG may be too slow.  But unless you have hardware and associated software to generate random bits you trust at a very high rate, even a couple of invocations of a good PRNG is going to generate strong values faster than you can pull them from your environment.

> Periodic re-seeding with high-quality seeds is necessary for robustness
> reasons: to recover quickly from state compromises (e.g., a sysadmin
> with root access using a kernel debugger to get at the PRNG's state and
> using this to escalate privilege once the debugging session is over).
This is an entirely different class of attacks, and absolutely, to defend against "state exposure" attacks, you need a way to get some new, independently unpredictable, state.  Of course, the kernel debugger attack is a funny one:  You're assuming an attacker who can read all of your state, but can't modify things (like, say, the constants used to decide how many bits of entropy various collectors contribute, even if you want to assume that the code is somehow protected from modification).  I think a more interesting state exposure attack is against a VM image.  The image could be signed to prevent any modification, but still expose its internal state.

                                                        -- Jerry