22

Challenge 22: Crack an MT19937 seed

Make sure your MT19937 accepts an integer seed value. Test it (verify that you're getting the same sequence of outputs given a seed).

Write a routine that performs the following operation:

  • Wait a random number of seconds between, I don't know, 40 and 1000.
  • Seeds the RNG with the current Unix timestamp
  • Waits a random number of seconds again.
  • Returns the first 32 bit output of the RNG.

You get the idea. Go get coffee while it runs. Or just simulate the passage of time, although you're missing some of the fun of this exercise if you do that.

From the 32 bit RNG output, discover the seed.

How do they want us to solve this?

Seeding you PRNG with timestamp is pretty bad because it's too predictable: the adversary can guess about what time the PRNG was seeded and only has to try a small number of possibilities before it recognizes the output corresponding one of the possible seeds. You can see some great examples on this video:

"Telling The Time" - OWASP talk by Chris Anley on Exploiting Insecure Randomness in Web Applications

Is this what we are supposed to do here ? It is not at all related to MT19937, though: Even using the best possible PRNG, you cannot get security if you don't use a proper entropy source to seed it. Also it's a pretty trivial attack.

However the instructions seem to indicate that this is what they expect from us. Also other people seem to have interpreted the instructions the same way: github:ricpacca, github:akalin...

So this is the scenario: you get a pseudo-random number from a PRNG which you know is seeded with the current timestamp in seconds. You don't know exactly when the timestamp is taken but you have at least a vague idea, and since seconds go by pretty slowly for computers there are not that many possibilities to try.

In [1]:
from time import time
from random import randint

from libmatasano import html_test, MT19937_32

now = int(time())
delta1 = randint(40, 1000)
seed = now  + delta1
delta2 = randint(40, 1000)
prng = MT19937_32(seed)

random_nb = next(prng)
time_of_output = now + delta1 + delta2
In [2]:
for i in range(40, 1000):
    seed = time_of_output - i
    prng = MT19937_32(seed)
    if next(prng) == random_nb:
        guess = seed
        break
else:
    raise Exception('could not regenerate random nb')

html_test(guess == seed)
OK

Morale

When using a PRNG, if you don't want people to be able to predict the output of your PRNG, you should make sure you seed it with a good source of entropy. Anything the adversary might have even a vague idea about is a bad source of entropy, and current time is one of them.

All operating systems provide easy ways to get access to good entropy. On Linux you have /dev/urandom for instance.