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

Jerry Leichter leichter at lrw.com
Sat Oct 25 23:32:13 EDT 2014


On Oct 25, 2014, at 8:08 PM, Bear <bear at sonic.net> wrote:
>> 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.  
It makes no difference whether AES-256 is "hard".  What matters is that "it's as hard as itself".  If there's an attack against it, it applies equally to the CPRNG and to the encryption.

This argument only works when you can show that any attack against the generator also gives you one against the encryptor.  For combinatoric algorithms like AES-256, this is unlikely to be something you can argue convincingly unless the same algorithm is used in both places.  (For algorithms with more mathematical structure, the story *might* be different.  In particular, something *like* Dual EC DRGB - but done in a way that ensured no one had a back door - *might* be provably as hard as some EC cryptographic algorithm.)
 
> 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.

                                                        -- Jerry



More information about the cryptography mailing list