[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