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

Jerry Leichter leichter at lrw.com
Fri Oct 24 23:24:47 EDT 2014


On Oct 24, 2014, at 1:56 PM, Bear <bear at sonic.net> wrote:
>> So, why do we need true random data at high speed so badly that Intel
>> decided to build in a device requiring large capacitors and it's own
>> power regulator?  The truth is, we don't need high speed.  As many
>> people have argued here, all any single system requires is 256 bits of
>> true random data.  That's all they *ever* need, so long as it remains
>> secret (which is hard), and so long as a cryptographically secure PRNG
>> (CPRNG) is used to generate all future cryptographically pseudo-random
>> data (which is comparatively easy).
> I think I'm going to take issue with this.  While 256 bits plus a 
> CPRNG is enough to prevent known and practical means of predicting 
> the stream of numbers created, it does not constitute proof that 
> a stream of outputs of that length *CANNOT* be predicted.  It 
> restricts the uncorrelated sequence length to be provably no more 
> than 256 bits.  Actually, it forces the uncorrelated sequence 
> length to be provably less than 256 bits assuming a CPRNG....
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.

Now, I'll agree this is not a very "clean" assumption.  You'd really like a random number generator that you can use with any cryptosystem of interest.  If you want to use ChaCha, then using AES to generate your "random" numbers leaves two points for analytic attacks:  AES and ChaCha.  What this argument comes down to is that there is no such thing as a generic CPRNG.  What's generic is the true random number generator - though it may only have to supply a fixed, fairly small, number of bits.  They can be used to initialize a CPRNG that should be part of the crypto suite, chosen so that it's no weaker, under the attacks considered, than any other part of the suite that depends on it.

                                                        -- Jerry



More information about the cryptography mailing list