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

Steven D'Aprano steve at pearwood.info
Mon Sep 14 15:32:33 CEST 2015

On Mon, Sep 14, 2015 at 09:26:33AM -0300, João Bernardo wrote:
> Quick fix!
> The problem with MT would be someone having all 624 32-byte numbers from
> the state. So, every now and then, the random generator should run twice
> and discard one of the outputs.

No, that's not good enough. You can skip a few outputs, and still
recover the internal state. The more outputs are skipped, the harder it
becomes, but still possible.

> Do this about 20 times for each 624 calls and no brute force can find the
> state. Thanks for your attention ;)

This is not brute force. The recovery attack does not try generating
every possible internal state. The MT is a big, complicated equation
(technically, it is called a recurrence relation), but being an
equation, it is completely deterministic. Given enough values, we can
build another equation which can be solved to give the internal state of
the MT equation.

Are you suggesting that every time you call random.random(), it
should secretly generate 20 random numbers and throw away all but the
last?

(1) That would break backwards compatibility for those who need it. The
output of random() is stable across versions:

[steve at ando ~]\$ for vers in 2.4 2.5 2.6 2.7 3.1 3.2 3.3 3.4; do
> python\$vers -c "from random import *; seed(25); print(random())";
> done
0.37696230239
0.37696230239
0.37696230239
0.37696230239
0.37696230239
0.376962302390386
0.376962302390386
0.376962302390386

(There's a change in the printable output starting in 3.2, but the
numbers themselves are the same.)

(2) it would make the random number generator twenty times slower than
it is now, and MT is already not very fast;

(3) most importantly, I don't think that would even solve the problem. I
personally don't know how, but I would predict that somebody with more
maths skills than me would be able to still recover the internal state.
They would just have to collect more values.

--
Steve