[Cryptography] Uncorrelated sequence length, was: A TRNG review per day
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
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.
More information about the cryptography