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

[M.-A. Lemburg]

On 11.09.2015 16:34, Cory Benfield wrote:
> On 11 September 2015 at 13:56, M.-A. Lemburg <mal at egenix.com> wrote:
>> The random module seeds its global Random instance using urandom
>> (if available on the system), so while the generator itself is
>> deterministic, the seed used to kick off the pseudo-random series
>> is not. For many purposes, this is secure enough.
> 
> Secure enough for what purposes? Certainly not generating a password,
> or anything that is 'password equivalent' (e.g. session cookies).
> 
> As you acknowledge in the latter portion of your email, one can
> predict the future output of a Mersenne Twister by observing lots of
> previous values. If I get to see the output of your RNG, I can
> dramatically constrain the search space of other things it generated.
> It is not hard to see how you can mount a pretty trivial attack
> against web software using this,

In theory, yes, in practice it's not all that easy. I suggest
to give untwister a try... it started with telling me it needs
about 1.5 hours, then flipped to more than a year, now it's
back to 6 hours. I'll leave it running for while to see whether
it finishes today :-)

>> It's also easy to make the output of the random instance more
>> secure by passing it through a crypto hash function.
> 
> Or...just use a CSPRNG and save yourself the computation overhead of
> the hash? Besides, anyone who knows enough to hash their random
> numbers surely knows enough to use a CSPRNG, so who does this help?

There's a difference between taking a pseudo random
number generator and applying a hash to it vs. using
a CPRNG:

A CPRNG will add entropy to its state at regular intervals, so
there's no such thing as a seeded sequence.

A RNG + hash still has the nice property of allowing
to reproduce the sequence given the seed, but makes it
much harder to determine the seed (brute force can be
made arbitrarily hard via the hash function).

The entropy in the output of the second variant is constant
(only defined by the initial seed and the hash parameters),
while it constantly increases in the CPRNG.

Some more background on this:
https://en.wikipedia.org/wiki/Entropy_%28information_theory%29

>> Perhaps it's time to switch to a better version of MT, e.g.
>> a 64-bit version (with 64-bit internal state):
>>
>>     http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt64.html
>>
>> or an even faster SIMD variant with better properties and
>> 128 bit internal state:
>>
>>     http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html
>>
>> Esp. the latter will help make brute force attacks practically
>> impossible.
> 
> Or, we can move to a CSPRNG and stop trying to move the goalposts on
> MT? Or, do both? Using a better Mersenne Twister does not mean we
> shouldn't switch the default.

I think it's worthwhile exposing the CPRNG from OpenSSL via
the ssl module (see one of my earlier posts in this thread).

People who need something as secure as their SSL implementation,
can then get secure random numbers, while kids implementing coin
flipping games can continue to use the well established API
of the random module.

Switching to a CPRNG in random would break the API, since some of
the functions in the API would no longer be available (e.g.
random.seed(), random.getstate(), random.setstate()).

PS: Apart from the API issue, the default RNG in random would
also have to be equidistributed and uniform, otherwise, the
derivatives available in the module would no longer satisfy their
expected distribution qualities. This is not needed when all
you're interested in is to get some non-predictable random
number for use in a session key :-)

-- 
Marc-Andre Lemburg
eGenix.com

Professional Python Services directly from the Source  (#1, Sep 11 2015)
>>> Python Projects, Coaching and Consulting ...  http://www.egenix.com/
>>> mxODBC Plone/Zope Database Adapter ...       http://zope.egenix.com/
>>> mxODBC, mxDateTime, mxTextTools ...        http://python.egenix.com/
________________________________________________________________________
2015-09-18: PyCon UK 2015 ...                               7 days to go

::::: Try our mxODBC.Connect Python Database Interface for free ! ::::::

   eGenix.com Software, Skills and Services GmbH  Pastor-Loeh-Str.48
    D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg
           Registered at Amtsgericht Duesseldorf: HRB 46611
               http://www.egenix.com/company/contact/