[Cryptography] randomness +- entropy

[Nico Williams]

On Thu, Nov 07, 2013 at 11:41:02AM +0200, Yaron Sheffer wrote:
> When this Minstrel guy reads urandom (which only has 23 bits of
> entropy at the time), do you reset the entropy estimate to 0? If you
> don't, and Minstrel broadcasts the random value somehow (in this
> case, as a timing value) an attacker can easily discover the first
> 23 bits of entropy which would make guessing the PRNG value of the
> next consumer much easier.

That's *not* supposed to be the case.  That is, 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!

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!

The PRNG needs an estimate of security relative to attackers that get to
observe some (many, most, all) of the PRNG's outputs.  This estimate is
not the same thing as an estimate of the PRNG's state's entropy.  This
estimate of strength should go down very slowly as outputs are produced,
and it should go up sharply when new trusted seeds are consumed.

An estimate of entropy is useful for protection against generating keys
from a not-yet-(or unsafely)-seeded PRNG.  Once the PRNG is seeded with
with enough entropy, the PRNG's state's entropy estimate should be
largely irrelevant because the more interesting question becomes: how
resistant is the PRNG is to guessing by attackers that get to observe
its outputs.

I.e., ssh-keygen might want to demand /dev/urandom outputs with N>256 bits
of entropy and 2^256 brute-force-equivalent cryptanalysis resistance.

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

Ideally /dev/urandom gets re-seeded on every read using HW RNG outputs.
Then occasional state compromises become almost a non-issue; sustained
compromise == complete compromise.

Nico
--