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

[Bear]

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