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

Bear bear at sonic.net
Fri Oct 31 16:41:08 EDT 2014


On Fri, 2014-10-31 at 19:09 +0000, dj at deadhat.com wrote:

> I'm confused. Wouldn't any CAZAC code meet this definition without being
> remotely useful for cryptography.
> 
> Presumably the term 'uncorrelated' isn't sufficiently precisely defined. A
> optimal CS-PRNG should produce both correlated and uncorrelated outputs
> for any definition of which output strings are correlated and which are
> not.

The property is necessary (IMO) but definitely not sufficient.  
XOR with a repeating pattern has an uncorrelated length the size 
of the pattern - and is completely useless for cryptography if 
your message is so long that any part of the pattern is used 
more than once.  But it is also a completely unbreakable one-time 
pad if the message is not that long.

Anyway, this is a property that is relatively easy to add to a system 
without diminishing the security of any CSPRNG you're using; you 
can just "whiten" the output of a PRNG having a long uncorrelated
sequence length and VERY long repeat period (such as a lagged-
Fibonacci generator with several thousand words of state) by XOR 
with the CSPRNG output.  The result will be have the provably
uncorrelated  sequence length of the PRNG, and will certainly be 
no less unpredictable than the CSPRNG.

That said, for efficiency's sake I'd prefer to simply use a CSPRNG
that has enough bits of state that there are no sequences of any 
length remotely close to the size of the largest single output I'll 
ever need which are impossible (or significantly more or less likely) 
for it to produce.

			Bear




More information about the cryptography mailing list