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

Bear bear at sonic.net
Fri Oct 31 14:31:12 EDT 2014


On Sat, 2014-10-25 at 23:32 -0400, Jerry Leichter wrote:
> On Oct 25, 2014, at 8:08 PM, Bear <bear at sonic.net> wrote:
>  
> > 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 don't know what this means.  Any *specific* property - like a long
> uncorrelated sequence length - is just a special instance of a way of
> distinguishing the output of some algorithm from a true random
> sequence.

I am completely baffled by this comment. 

A provable uncorrelated sequence length of N or greater is a proof 
that it is NOT even theoretically possible to distinguish any
generated sequence having length less than N from a true random
sequence.  That is the opposite of being a way to distinguish a
generated sequence from a truly random sequence. 

This is "like a one-time pad" in that there are an equal number of 
possible initial states of the PRNG that could result in any output
sequence of the uncorrelated sequence length or less, just as in a 
one-time pad there are an equal number (in that case, one) of 
possible pads that could have produced the observed ciphertext
regardless of the plaintext. 

If we want protection from unforeseen mathematical insights into 
the PRNG, we can obtain it (to some extent) by using PRNGs which 
have an uncorrelated sequence length strictly longer than the length 
of any single output we intend to generate. In exactly the same way 
that a one-time pad is immune to any cryptanalysis no matter how
advanced but can protect only messages shorter than itself, a PRNG 
of long uncorrelated sequence length is immune to any possible way 
to distinguish a PRNG output sequence from a random sequence, but 
that immunity is limited to output sequences shorter than that 
length. 

If someone is using a PRNG with a 32-bit state to generate his
128-bit keys, my brute force search space for the key is 2^32 possible
keys, not 2^128, because there are only 2^32 values which are both 
valid keys _and_ could have been produced by that generator. 

If additional constraints on the output sequence eliminate a much 
larger fraction of the possible sequences (eg, if it has to be a valid 
RSA key) then we're talking about the intersection of two sets -- the
set of valid keys and the set of sequences that length which could 
have been produced from your generator.  And even if both the number 
of possible keys and the number of possible sequences are beyond 
the reach of brute force, the intersection of the two might be 
within it. 

An attacker with the right insight into the mathematics would only 
need to brute-force a set the size of the intersection, rather than a 
set the size of all possible keys or a set the size of all possible
PRNG-produced sequences.  An uncorrelated sequence length strictly
longer than the RSA key means that even for an attacker with omniscient 
mathematical insight there is no POSSIBLE attack that can consider 
less than the full set of valid RSA keys, because with that 
uncorrelated length, every valid key is provably equally likely 
to be produced by the generator. 

We are allowed to disagree about whether this is important, depending 
on how likely we consider attackers with greater mathematical insight 
than ourselves to be. But I believe that it is a significant property
for PRNGs, and that attackers with greater mathematical insight are a
more significant risk, comparatively speaking, than attackers with
detailed knowledge of the PRNG's internal state at a chosen instant or
attackers who influence our sources of entropy at a chosen instant, 
particularly when we are talking about the long-term security of data
at rest. 


			Bear



More information about the cryptography mailing list