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

[M.-A. Lemburg]

On 11.09.2015 22:44, M.-A. Lemburg wrote:
> On 11.09.2015 20:52, Tim Peters wrote:
>> [Tim]
>>>> ...
>>>> 2. If they knew they were targeting MT, and had 624 consecutive 32-bit
>>>> outputs, they could compute MT's full internal state essentially
>>>> instantly.
>>
>> [Marc-Andre]
>>> How would they do that ? MT's period is too large for
>>> things like rainbow tables.
>>
>> It's not trivial to figure out how to do this, but once you do, it
>> works ;-)  No search, or tables, of any kind are required.  It's just
>> simple (albeit non-obvious!) bit-fiddling to invert MT's
>> state-to-output transformations to get the state back.  Here's a very
>> nice writeup:
>>
>> https://jazzy.id.au/2010/09/22/cracking_random_number_generators_part_3.html
> 
> Indeed very nice. Thanks for the pointer.
> 
> I wonder why untwister doesn't use this. I gave it 1000 32-bit
> integers, so it should have enough information to recover the
> seed in a short while, but it's still trying to find the seed.
> Oh, and it now shows: 5 days 21 hours left. I stopped it there.
> 
> Anyone up for a random.recover_seed() function ? ;-)

Turns out this will have to be named random.recover_state().

Getting at the seed is too difficult, esp. for strings in Python 3,
and not really worth the effort anyway.

While implementing this, I found that there's a bit more trickery
involved due to the fact that the MT RNG in Python writes the
624 words internal state in batches - once every 624 times
the .getrandbits() function is called.

So you may need up to 624*2 - 1 output values to determine a
correct array of internal state values.

-- 
Marc-Andre Lemburg
eGenix.com

Professional Python Services directly from the Source  (#1, Sep 12 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 ...                               6 days to go
2015-10-21: Python Meeting Duesseldorf ...                 39 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/