[Python-ideas] Should our default random number generator be secure?

[Robert Kern]

On 2015-09-14 20:07, Sturla Molden wrote:
> On 14/09/15 19:15, M.-A. Lemburg wrote:
>
>> I am well aware that MT doesn't satisfy all empirical tests
>> and also that it is not a CSPRNG
>
>> However, it has been extensively studied and it is proven to be
>> equidistributed which is a key property needed for it to be used as
>> basis for other derived probability distributions (as it done by the
>> random module).
>
> And with this criterion, only MT and certain PCG generators are acceptable.
> Those are (to my knowledge) the only ones with proven equidistribution.

Do not confuse k-dimensional equidistribution with "equidistribution". The 
latter property (how uniformly a single draw is distributed) is the one that the 
derived probability distributions rely upon, not the former. Funny story: MT is 
provably *not* strictly equidistributed; it produces a exactly 624 fewer 0s than 
it does any other uint32 if you run it over its entire period. Not that it 
really matters, practically speaking.

FWIW, lots of PRNGs can prove either property. To Nate's point, I think he is 
primarily thinking of counter-mode block ciphers when we talks of CSPRNGs, and 
they are trivially proved to be equidistributed. The counter is obviously 
equidistributed, and the symmetric encryption function is a bijective function 
from counter to output.

However, not all CSPRNGs are constructed alike. In particular, ChaCha20 is a 
stream cipher rather than a block cipher, and I think Marc-Andre is right that 
it would be difficult to prove equidistribution. Proving substantial 
*non*-equidistribution could eventually happen though, as it did to ARC4, which 
prompted its replacement with ChaCha20 in OpenBSD, IIRC.

And all that said, provable equidistribution (much less provable k-dimensional 
equidistribution) doesn't make a good PRNG. A simple counter satisfies 
equidistribution, but it is a terrible PRNG. The empirical tests are more 
important IMO.

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
  that is made terrible by our own mad attempt to interpret it as though it had
  an underlying truth."
   -- Umberto Eco