12
$\begingroup$

I generated some random numbers using a Python script. I have the first 40 numbers of the sequence. Is there a way to recover the seed or find the next 460 numbers in the sequence?

The numbers were generated using the following code.

import random

i=1
mn = 1
mx = 2
while i<500:
    print(random.randint(mn,mx))
    mn=mn*2
    mx=mx*2
    i=i+1
|improve this question
$\endgroup$
  • $\begingroup$ Do you know how it was initialized? The internal state of python's random number generator is rather large, so these may not be enough in the general case, you seem to have only 800 bits. If you know there was an Int or even Long seed it is easier. $\endgroup$ – Meir Maor Dec 9 '17 at 11:18
  • $\begingroup$ From what I understand Python uses "long(_hexlify(_urandom(2500)), 16)" by default and if that fails then "long(time.time() * 256" . I tried brute force for the second case without any success :( , so it's most likely the first one. $\endgroup$ – SeeCSea Dec 9 '17 at 11:33
  • 1
    $\begingroup$ I'm afraid you are out of luck, you have 800 bits of information and you want to restore 19968 bits from a strong random source. $\endgroup$ – Meir Maor Dec 9 '17 at 11:45
18
$\begingroup$

I have the first 40 numbers of the sequence. Is there a way to recover the seed or find the next 460 numbers in the sequence?

The first thing to know is that Python's random module uses Mersenne Twister as the PRNG. That is not a cryptographically secure RNG, in fact it is easy to recover the state as long as you have enough samples.

40 numbers of the sizes you use is not sufficient to recover the full MT state and find the next outputs that way.

It is more than enough to recover a time seed as Python uses when OS randomness is not available. You can just run a brute force of time values in the recent past. Latest versions of Python 2/3, however, initialize the full state from urandom or similar where available, and that cannot be inverted with this little output.

(Of course you can still call random.get_state() but presumably you were not asking that ;)

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I fail to get from the source how random is initialized in Python 2.7.14 on Windows. On one hand, automated experiments repeatedly running a two-liner in Python invoked at fixed time() (using a bat file repeatingtime 09:00 & python.exe test.py with appropriate privileges) concludes that time() is not the only entropy source, as stated by the doc. On another hand, I fail to locate the code making that better initialization. I have removed everything that I said until I'm confident in my understanding. $\endgroup$ – fgrieu Dec 12 '17 at 7:12
  • 1
    $\begingroup$ @fgrieu, Yeah, sorry, you are right about that part. In fact Python 2.7 does also initialize from urandom when available, by constructing a random.Random object when you import random. The code is terrible, so no wonder we were both confused: the seed function in Python's _randommodule.c is called twice on every Random object creation - once from random_new with null/None seed argument and once from the child class init->seed with an already random seed argument. $\endgroup$ – otus Dec 12 '17 at 14:12
  • $\begingroup$ Ps. the time function used as fallback is python's time.time which has subsecond accuracy on most systems. $\endgroup$ – otus Dec 12 '17 at 14:18
  • $\begingroup$ Ah, thank you, I had missed that upper layer in random.py; what a mess, complete with silent fallback to something very much worse than the normal behavior if some runtime mishap occurs. $\endgroup$ – fgrieu Dec 12 '17 at 17:50
12
$\begingroup$

Python uses a Mersenne twister PRNG, and though it is not secure it does have a large state. You have here 40 numbers, the first one gives you 1 bit and each subsequent number has an extra bit for a total of 800 bits. This is significantly smaller then the internal state of the MT-19937.

This page explains how to find the internal state of python's PRNG: https://jazzy.id.au/2010/09/22/cracking_random_number_generators_part_3.html Step 1 is getting 624 Integers out of it, much more than 40 even if they were full integers.

If you know for instance there was an Integer seed or such, you have enough information and it is also possible computationally.

|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.