[Cryptography] randomness +- entropy

[Nico Williams]

On Thu, Nov 07, 2013 at 08:11:57PM -0500, Jerry Leichter wrote:
> 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
> [...]

That's a strawman.  I never said that's a definition of a PRNG (good,
bad, whatever).

I also never said anything about provability.

I was only arguing that consuming n bits of PRNG output != lowering the
PRNG's "entropy" by n bits.

> > 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.

Think DTrace.  The debugger might only be permitted to read.

Nico
--