Re: Patch: new random pseudodevice

[Mouse <mouse%Rodents-Montreal.ORG@localhost>]

[I'm pulling together multiple mails from tls here.  The second-level
quotes are from varying people; I've marked their authors according to
the info I have.]

[Mouse]
>> "Revealed to userland", of course.

>> Combined with the conservative approach to estimating how much
>> entropy was put into the pool, it is a reasonably good way of making
>> sure that when you ask for strongly random bits, you get strongly
>> random bits uncorrelated with anyone else's bits.
> Look at the implementation.  It *never* worked that way.

It came reasonably close.

> To cause bits to actually be "taken out", you'd have to maintain two
> pools, discard the entire contents of one every time any bits were
> revealed to userspace, and switch to the other.  Or something along
> those lines.  And that's just not how it ever worked.

To be certain of it, yes.  It should have been done that way, and I
would support changing it to be done that way.

What it actually was is a hybrid.

[Alan Barrett]
>> Fair enough, but you still seem to be talking about how good a
>> CSPRNG it is, whereas my concern is that it's pseudorandom, nor
>> random.

> So was the output from the old entropy pool.

Only sort of.

> As soon as you start "accumulating" random bits in any manner that
> leaves the old ones in -- that is, does not entirely eliminate them
> as inputs to the accumulator function -- even after you "take them
> out" -- that is, disclose the accumulator function's output -- you
> are dealing in precisely what you say you want not to:
> cryptographically secure pseudorandomness.

Not entirely, in two respects: (1) provided you don't draw on the pool
for more bits than it has information content, you are in principle
getting information out.  If the mixing function is good, you will
actually be doing so.  (2) If you are stirring new randomness into the
pool in the meantime, it...complicates things; it is no longer a pure
PRNG.  To an approximation as good as the mixing function is good, you
can draw on the pool as much as you like, provided you never draw
enough to reduce the information content to zero.

I'm not particularly happy with the old mixing function; see below.

I would much prefer to do what you suggest...

> To get the property you seem to want, you basically have to buffer
> the purportedly "true" randomness into pools, blocks, [...]

...to accumulate entropy into unread blocks and release it to the rest
of the subsystem in blocks, to be consumed as such.  Preferably, it
should be whitened as it's accumulated into blocks.

_That_ would actually be fixing one of the potential problems the
current system has, without introducing more.

> Let me put it this way: before, you may have thought you were getting
> some kind of "true" randomness.  You weren't.

But you were, to a decent approximation, assuming the input entropy
estimate was not an overestimate.

You appear to think that anything that's not pure true randomness must
be pure PRNG.  The old randomness pool was neither; it was a hybrid.
If the mixing function is good - and that's the first weakness; we have
only heuristic reasons to think it is - then to a correspondingly good
approximation, it returned real randomness - bits uncorrelated with
anything else - as long as the actual entropy-in-pool was greater than
the number of bits returned.  This is the second weakness; nobody
really knows how good the estimate of the entropy supplied by input is.
Personally, I suspect it's an underestimate, but I have no particular
evidence for that; as long as I'm right, it's OK in this respect.

> Now, you still aren't, but at least what sits between you and the
> entropy source is a lot more clear, and a lot better analyzed

I don't know; it sounds a lot less clear to me.

I'd still rather fix it right.  If you go ahead with inflicting a PRNG
on /dev/random, it really really needs to be prominently marked as
being a PRNG even for the stronger device, since that's a nontrivial
regression over previous versions (which may not have been perfect, but
did return at least _some_ real randomness in the bits it produced, the
exact amount depending on how good the mixing was and how good the
input estimates were).

> The bottom line: pseudorandomness is the best you're going to get.

With your design, perhaps.  But you actually outlined a design that
does not suffer from those problems; why not do that instead?

> It might as well be done in the safest way possible,

That's fine, for /dev/urandom.  If you want to hook what you've
outlined, or something like it, up to /dev/urandom, that's fine.

For /dev/random, I consider it a bug.  That the old system was
partially broken (to an extent nobody really knows) does not excuse
replacing it with something even more broken.

> I have been trying to follow the Yarrow/Fortuna design paradigm of
> rekeying the stream generator from the entropy pool at each
> "request".  [And asking, what's a "request"?]

> However, when applications use /dev/random, we could consider a
> "request" to be a single read from the device.  This also has the
> appealing property that it aligns with how the underlying generator
> (CTR_DRBG) counts "requests".  That way, in practice, each read from
> /dev/random would get a fresh AES key -- and most application reads
> from /dev/random, which may block, are very small.

Combined with a strong entropy pool such as you outlined, one that
accumulates whitened data into blocks and, once accumulated, returns it
without stirring, that looks fine to me, but it's excessively
complicated; why burn a whole AES key's worth of bits from the pool
when someone reads 16 bits from /dev/random?  I'd prefer to just return
data from the underlying pool directly (and, of course, discard it
permanently, like any data drawn from the underlying pool).

> I think that, in practice, that is about as close to meeting the
> expectations of the application authors as possible.

As an application author, I'm not sure.  From a point of view of making
the device fit the use, I would like to see

(1) Strong bits suitable for direct use as things like crypto keys.
Using a PRNG here, even a really good one, is a major fail.  The only
time it's acceptable is when the data drawn is no larger than the PRNG
key, and then you might as well return the bits directly.

(2) Bits that are unpredictable in practice but need not be good enough
for strong crypto uses.  For example, I've done a long-running
simulations for which I basically clone random(3) and then,
occasionally, mutate its state with a byte from /dev/urandom, to
disrupt any possible patterns that could be interacting with the
simulation.  (I don't use random(3) directly because its state isn't
documented enough for me to be able to do the "mutate it a little"
operation without going under the hood.)  Another application is to
seed userland PNRGs - random(time(0)), loosely - but without things
like getting the same seed whenever two instances are started during
the same second.

I think /dev/random should be (1) and /dev/urandom should be (2).

/~\ The ASCII                             Mouse
\ / Ribbon Campaign
 X  Against HTML                mouse%rodents-montreal.org@localhost
/ \ Email!           7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B