Re: Patch: new random pseudodevice

[Dennis Ferguson <dennis.c.ferguson%gmail.com@localhost>]

On 9 Dec, 2011, at 17:38 , Mouse wrote:
> 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.)

I agree with many of the things you are arguing, and I do only
know enough about this to be dangerous, but I'm pretty sure the
assertion you seem to keep making that if you use 128 bits of
information to key a CSPRNG, or a cryptographic hash, or pretty
much any other cryptographic device, then taking 128 bits of output
from the device is fine but the 129th bit is somehow suspect, is
misunderstanding how these things work and is not correct.

If you key a CSPRNG with 128 truly random bits then you have 2^128
possible input states.  For 128 bits of output from the CSPRNG to have
the same amount of information as the input would require that the
128 bits of output have the same number of possible states, i.e.
2^128.  For this to be true, however, would require that there be a
one-to-one correspondence between each of the possible 2^128 inputs
and each of the possible 2^128 outputs, and if that were true then
the function would be trivially invertible since it is a linear
transformation.

Because cryptographic-anything needs to protect its input it can't
work like this.  The output of a CSPRNG (or cryptographic hash, for
that matter) has less entropy per bit than its input because this
is necessary to keep from trivially revealing its input.  That
is, if you take 128 bits of output from the 128-bit-salted CSPRNG
some of the 2^128 possible 128 bit codes will be reliably missing from
that output.  Any particular 128 bits of output from the CSPRNG is
less random than the 128 bits you put in.  The argument that the 128
bits are indistinguishable from random instead relies on a
computational expense argument: knowing that codes are missing
does an attacker no good unless he knows which codes are missing,
and if the only way to determine which codes are missing is by
trying all 2^N possible inputs to see what is *not* missing then,
for sufficiently large N, the computation may be infeasible.

I think, then, that if you are comfortable taking 128 bits of
output from a CSPRNG then there's no reason not to be comfortable
taking a 129th (and 130th, and 131st and so on).  The state of
the 129th is only infinitesimally less unpredictable than the 128th
bit since its state depends on input information that was not revealed
in the first 128 bits of output (since the first 128 bits of output
contain less than the 128 bits of "information" the CSPRNG was keyed
with).  If you are uncomfortable with the 129th bit, however, then you
must also be uncomfortable with the 128th (and 127th and 126th) since
they are only a little bit better than the 129th.  There is no sharp
cutoff at 128 bits.  I assume there might be some sequence of less
than 128 bits which would be as random as the 128 input bits, but
good luck figuring out what that length would be.

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

You keep saying the bit in parentheses, but I'm pretty sure that's
wrong.  A cryptographic function where an 'N' bit output was as
random as the 'N' bit input would not be a cryptographic function,
so if you are assuming that N->N bit transformations through
cryptographic functions don't lose information you are about
as reliant on those "weaker assumptions" as the code you are
criticizing here, I think.

Dennis Ferguson