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

Bear bear at sonic.net
Sat Oct 25 20:08:54 EDT 2014

On Fri, 2014-10-24 at 23:24 -0400, Jerry Leichter wrote:
> > 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....

> A CPRNG that is at least as "hard" as the algorithms with which it's
> used cannot provide a point of attack.  For example, if you rely on
> AES-256 for your cryptography, and your protocols are secure under the
> assumption (as is common these days) that AES-256 is indistinguishable
> from a random sequence, then generating your random numbers using
> AES-256 in counter mode with a true random key exposes you to no attack
> that wasn't already present.

You're right that a CPRNG that is "hard" doesn't provide a point of 
attack.  But, like most of our ciphers, we don't have any real 
mathematical proof that a particular CPRNG is in fact "hard".  All 
we really know is that we haven't found the soft spots yet.  

A provably long uncorrelated sequence length is the same kind of 
"hard" guarantee as a one time pad -- although, like a one-time pad, 
it applies only to sequences shorter than that length. 

I think that PRNGs should be able to prove a minimum uncorrelated
sequence length (hence require RNG state) that is longer than 
sequences (specifically keys) whose unpredictability we rely on 
for the security of our other components. 


More information about the cryptography mailing list