# [Cryptography] Uncorrelated sequence length, was: A TRNG review per day

Bear bear at sonic.net
Fri Oct 24 13:56:35 EDT 2014

```On Fri, 2014-10-24 at 05:31 -0400, Bill Cox wrote:

>
> So, why do we need true random data at high speed so badly that Intel
> decided to build in a device requiring large capacitors and it's own
> power regulator?  The truth is, we don't need high speed.  As many
> people have argued here, all any single system requires is 256 bits of
> true random data.  That's all they *ever* need, so long as it remains
> secret (which is hard), and so long as a cryptographically secure PRNG
> (CPRNG) is used to generate all future cryptographically pseudo-random
> data (which is comparatively easy).

I think I'm going to take issue with this.  While 256 bits plus a
CPRNG is enough to prevent known and practical means of predicting
the stream of numbers created, it does not constitute proof that
a stream of outputs of that length *CANNOT* be predicted.  It
restricts the uncorrelated sequence length to be provably no more
than 256 bits.  Actually, it forces the uncorrelated sequence
length to be provably less than 256 bits assuming a CPRNG.

In order to prove an uncorrelated sequence length, it is necessary
to first accept some standard for correlation, and then prove that
every sequence of a given length is produced by a set of the
possible initial states of the PRNG none of which are larger or
smaller than any of the other sets by a ratio larger than your
correlation parameter.  With a state of size N, there aren't even
as many possible initial states as there are output sequences of
length N+1, so some output sequences must be impossible - the set
of initial states that produces those sequences has cardinality
zero, and zero will definitely fall outside any correlation
parameter.

That is, whether or not there's any *known* way to mathematically
predict whether the next bit is a 1 or a 0, there are guaranteed
to *be* sequences at minimum 257 bits long which can never be
produced, and therefore we cannot prove that there is no *unknown*
way to mathematically predict whether the next bit is a 1 or a 0.

The distinction may not be important for most applications; but
if an attacker knows some important technique for attacking
the CPRNG that you don't know, and can eliminate whole classes of
bit sequences as being impossible to produce from that CPRNG,
the attacker may need to search a key space no larger than the
uncorrelated sequence length -- and, for some ciphers such as
RSA, a 256-bit search space is for other reasons relatively
trivial.  Using a CPRNG proven to have an uncorrelated sequence
length of N bits means that the key space he has to search even
when he knows a key has been produced by it, no matter what he
knows about which sequences are possible and impossible (or
more-likely and less-likely) given your CPRNG, is still never
smaller than N bits.

So, I would say that seeding with just 256 bits of state is only
reasonable if for some reason you absolutely know that there can
be no *POSSIBLE* attack on your CPRNG.  Because math that enables
new attacks will keep being discovered.....

A relatively humble lagged-Fibonacci generator of the sort we would
never use for cryptography, provably produces an uncorrelated
sequence the size of its state.  So does a linear feedback shift
register. But, as is true with every generator that *provably*
produces an uncorrelated sequence the size of its state, they
are trivially predictable thereafter and therefore not a candidate
for use as a cryptographically secure PRNG.  Any PRNG must have
some impossible sequences of outputs which are no longer than
its state, and cryptographic PRNGs must have correlated sequences
which are shorter.

For a good CPRNG, I think it's important to prove a minimum length
of uncorrelated sequences. A small state proves a maximum length
for uncorrelated sequences.

Bear

```