Re: Patch: new random pseudodevice

[Thor Lancelot Simon <tls%panix.com@localhost>]

On Fri, Dec 09, 2011 at 09:18:39PM +0100, Pawel Jakub Dawidek wrote:
> 
> That's the problem. They might seem random, but they are not. They
> weren't designed as true random number generators, so they can't be
> trusted neither to generate true random numbers nor to be resistant on
> various attacks. For example how does your sound card handle very loud,
> continuous noice? Does it generate random numbers then? Does sound card
> manufacturers test that? No. Sound input on the other hand can be nice,
> one of many, entropy sources for CSPRNG.

In fairness to Mouse, I think he's talking about something very different.
I will try to address what I think he was talking about below.

Let us suppose the construction of an "entropy pool" generator is simply
to hash all inputs it has ever received and return the SHA1 hash as the
generator's output.

Now, let's say the generator's output O at time T is unpredictable -- we do
not know any of the generator's inputs.

 (if we want B output bits such that guessing their value is as hard either
  as breaking SHA1 or resorting to brute force, it would suffice in fact that
  we not know B of the inputs; but let's say we don't know any)

Now, here our generator is just SHA1.  Let's say no more input arrives, but
at time T1 we generate an output.  It will be the same.  Oops.  But how
to fix this is clear: we make "T" itself an input to the generator.

In fact, let's say no more input arrives, ever.  Now the generator's output
degrades to the SHA1 of the concatenation of O and T1...Tn.  It seems
reasonable to consider T1.....Tn to be known to any competent adversary.

Some people are as comfortable with this generator as they are with the
security of the underlying hash function.  This I take to be basically
Mouse's position -- or, a much less sophisticated form of it, since he
would doubtless observe that the "entropy estimator" tries to protect
us against all the inputs T1...Tn really being entirely predictable.

(However, consider that an adversary could use another PRNG to generate
a sequence of request-times that our estimator could not distinguish
from a truly random sequence -- and that, in fact, event timing is
_exactly_ how the existing code does its entropy estimation for almost
all sources, making it vulnerable to exactly this kind of active attack!)

But let's keep considering the simplified generator without the estimator.
Note that if the adversary were to learn O, the game would be up.  Knowing
O and knowing or being easily able to guess T1...Tn, the adversary can
predict all future outputs of the generator!

Are we really willing to make the security of all future outputs depend
on the security of O?  One way to frustrate this is to jam a cipher S
in the middle, and rather than directly disclosing O, use O to key S.
Now, you can't know O unless you have a key recovery attack on S.  If
you have a plaintext recovery attack, you can know future bitstrings
that will be produced by S -- but you can't know O.

If you are, basically, more comfortable with this construction than with
the original construction, then you are more comfortable with a PRNG
with the general design of Fortuna, Yarrow, the FreeBSD and OS X
implementations of /dev/*random, and what I sent out as a patch, than
with one generally designed like the original Linux code or our old code.

How many bits of output to allow before causing a reader from /dev/random
to block, however, is even so a valid and useful question.  And I am very
very willing to admit others here may have better ideas about it than I
do.

Thor