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

[M.-A. Lemburg]

On 10.09.2015 19:04, Xavier Combelle wrote:
>> I think this is the major misunderstanding here:
>>
>> The random module never suggested that it generates pseudo-random data
>> of crypto quality.
>>
>> I'm pretty sure people doing crypto will know and most others
>> simply don't care :-)
>>
>> Evidence: We used a Wichmann-Hill PRNG as default in random
>> for a decade and people still got their work done. Mersenne
>> was added in Python 2.3 and bumped the period from
>> 6,953,607,871,644 (13 digits) to 2**19937-1 (6002 digits).
>
> It is not a evidence, I have an evidence of the opposite:
> some people can and does use random.random() for generating session key or
> csrf tokens and it's an insecure default.

It all depends on what you consider "secure" or "secure enough"
and points directly to another misunderstanding: that "secure"
is a well-defined term :-)

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.

It's also easy to make the output of the random instance more
secure by passing it through a crypto hash function.


But back to the original question: What is "secure" ?

In crypto terms, "secure" usually refers to "computationally
infeasible to calculate before the sun goes dark" (to take one
variant).

More realistically, it can be defined as: Based on the public
knowledge known today, it's impossible to run a program which
allows converting the output of a crypto function back to its
inputs within a reasonable time span. And this property will
- based on today's knowledge - hold for at least the next
5-10 years.

You may notice the many parameters in these definition attempts.
It all depends on who you ask.

With the advent of new technologies like quantum computers,
it's not at all clear that any of those definitions will still
hold in a couple of years. It's well possible that only quantum
computers will be able to implement the necessary programs
and it'll take a while for mobile phones to catch up and come
with chips implementing those ;-)


Now, leaving aside this bright future, what's reasonable today ?

If you look at tools like untwister:

    https://github.com/bishopfox/untwister

you can get a feeling for how long it takes to deduce the
seed from an output sequence. Bare in mind, that in order
to be reasonably sure that the seed is correct, the available
output sequence has to be long enough.

That's a known plain text attack, so you need access to lots
of session keys to begin with.

The tools is still running on an example set of 1000 32-bit
numbers and it says it'll be done in 1.5 hours, i.e. before
the sun goes down in my timezone. I'll leave it running to
see whether it can find my secret key.

Untwister is only slightly smarter than bruteforce. Given
that MT has a seed size of 32 bits, it's not surprising that
a tool can find the seed within a day.

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.

Tim ?

BTW: Looking at the sources of the _random module, I found that
the seed function uses the hash of non-integers such as e.g.
strings passed to it as seeds. Given the hash randomization
for strings this will create non-deterministic results, so it's
probably wise to only use 32-bit integers as seed values for
portability, if you need to rely on seeding the global Python
RNG.

-- 
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/