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

[Steven D'Aprano]

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