Re: Patch: new random pseudodevice

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

[Another omnibus reply.]

Thor has several different arguments, but some of them seem to amount
to "the old way was broken, therefore the new way is better".  I
certainly hope I'm misreading those, because the Thor I thought I knew
is smart to seriously support that kind of stance.

The old way was indeed broken in some ways.  Thor's new appreach is
better in a few of those ways; it's significantly worse in some others.
(I see no point in listing them here; upthread, I've gone over all the
ones I've noticed.)

[Joerg]
> Trying to estimate the entropy of the input is a flawed process.  The
> (older) random pool based CSPRNG is using this flawed concept to
> provide a sense of security it can't provide.  Ignoring every
> (theoretical) question of how well mixing entropy actually works --
> if you can't properly measure it, it is simply something that has to
> be dropped from the output.  That's what you get with Fortuna.

I still can't see how this amounts to anything other than estimating
the entropy provided as infinite, and I still can't see how that isn't
worse than just about any other estimate.

[Thor, quoting me]
>> 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.
> I think we have a basic disagreement here.  I don't grant that there
> is such a thing as "hybrid" true randomness.

No, not hybrid true randomness.  I'm not sure that even makes sense.
Rather, I meant a hybrid between pure randomness and pure PRNG.

>> [...] 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).
> What is "real randomness in the bits"

Information, in the information-theoretic sense, which has not been
previously revealed in the output.

> and why is it not in the bitstream produced by the CTR_DRBG keyed
> from the entropy pool?

It is - up to the amount used as input to the PRNG.  However, once
keyed, that PRNG will never produce more information than its contained
in its key, and that is limited to the number of bits used in the key.
(I'm considering rekeying as a new PRNG.)  That it is currently
difficult to exploit the correlations among its output bits does not
mean they aren't there; I want /dev/random to return new information,
not just a warming-over, no matter how complicated or currently secure,
of old information.  The old ("current") way did return new
information, even if maybe not one full bit of information per bit of
output, whereas the PRNG approach you've been describing doesn't, not
until rekey.  (If rekeying happens after it's generated no more bits
than went into the keying, it's fine, but I doubt that's what you're
planning.)

> I *am* going to replace the entropy pool with Fortuna, which has
> several appealing properties that are not exactly what you want, but
> head in that general direction.

As long as /dev/random is hooked up to a PRNG, CS or not, it is not
what I want.  Nor is switching from the hybrid to a pure PRNG a move in
even the general direction of what I want.

Improving the mixing function would have been.  Switching to something
such as you outlined, a (presumably whitened, and conservatively
estimated) entropy pool whose output is _not_ mixed back in, would have
been a much bigger step in the direction I want.

>> (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.
> This may be your opinion, but it differs radically from the opinion
> of almost every expert in the field of which I am aware.

Then either you have misunderstood them or they are wrong - or they are
talking about a substantially more restricted domain than I am.

A PRNG cannot create information; its output contains no more
information than its input.  If it is keyed with 128 bits, say, it
cannot produce more than 2^128 different output keystreams, even if
those keystreams are far longer, and thus appear to contain far more
information, than that.  Unless you're using it for a purpose that
doesn't need more than 128 bits of information content, it is
unsuitable.  (And if you don't need more than that, any good
cryptographic hash function will do just as well.)

A version of this very issue, with much smaller numbers, actually
happened.  I don't recall full details, but I think it was a Linux
distro shipping with an ssh implementation that ultimately used a
16-bit seed when generating ssh keys, meaning it could generate only
2^16 different keys; even though they looked large enough to be secure,
they weren't, even if those 16 bits were strongly random.  Using a PRNG
as you are have outlined is the same thing, only with larger numbers.
It may be fine in practice, today, but it is not theoretically
acceptable.  The only case a PRNG is of any real use for is computing a
longer key when you want a large key and have only a small one, but
even the small one has sufficient entropy for your purposes.

> Notably, [Mouse's opinion] differs from the opinons of the people who
> wrote the several relevant FIPS and X9 standards, who _require_ that
> cryptosystem keys be generated by an approved DRBG (their terminology
> for a CSPRNG) -- though they also impose minimum entropy requirements
> for keying the DRBG itself -- and of SP800-90, which explicitly
> discusses this issue.

I don't know why they chose that.  Perhaps the standards body simply
made a mistake.  Perhaps they had to compromise for any of many
possible reasons.  Perhaps they simply considered the minimum input
entropy to be enough for the purpose the standard is intended for and
just use the PRNG as a whitening and stretching function.  But I value
information-theoretic considerations, such as any determinstic
computation's inability to contain more information in its output than
is present in its input, over any standards body's output.

[Paul Koning, quoting me]
>> [uses for RNGs]
>> (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.

> I don't think this is correct.

> One thing to keep in mind is that the current standard of quality for
> a cipher is that its output is indistinguishable from a random string
> (up to a length limit, 2^blocksize or 2^(blocksize/2), I'm not sure
> which).

Computationally indistinguishable, today.  It is never theoretically
indistinguishable, as can easily be seen by considering trying all
possible keyings and seeing if any of them match.

This is why I'm hammering on the information-theoretic considerations:
they are fundamental, not subject to change with advances in
cryptanalysis.  The security of bits drawn from an properly-designed
entropy pool depends on much weaker assumptions than the security of
bits produced by a PRNG (when the PRNG seed is smaller than the number
of bits produced).

In practice, today, what Thor is proposing (or, in view of what he's
said, perhaps I should say "imposing") is probably good enough for most
purposes.  It is not good enough in theory.  That's why it does not
satisfy me, especially when there is an easy way to get something that
is as good, theoretically, as is available - indeed, Thor himself
outlined it.

[smb]
> In my opinion ([and presumably others']), a CSPRNG is more secure.
> Why?  Because we *know* what it does, all the time.  "True" RNGs are
> devilishly hard to get right, and are susceptible to all sorts of
> environmental perturbations.  Imagine what would happen if someone
> upgraded the disk to a flash disk or one with a large flash cache....

You still need a true RNG (to seed your PRNG), though, or you get
predictable bits.

A CSPRNG makes a good mixing function.  But that's really all it's
doing, because that's all it's capable of doing.

In any case, it's no skin off my nose.  I have plenty of other reasons
for not using whichever NetBSD this ends up in.  I've pointed out the
problems; if NetBSD is determined to carry on regardless, that's its
lookout.

/~\ 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