Is it possible to find a Mersenne Twister seed given only the first output? Suppose I have a Mersenne Twister seeded with some unknown value, and I’ve been given the first output. Given only this first output, and no other information, is it possible to derive the unknown seed?

I feel like the answer is no, but I want to be sure I’m not missing something.



Context: I’m looking at Matasano challenge 22. You seed an MT19937 RNG with the current Unix timestamp, wait a random number of seconds (40 ≤ T ≤ 1000), then get the first output from the RNG. The challenge is to find the original seed.

I started by trying to reverse the output process, essentially inverting the inner workings of the twister. But after some effort, it seems like doing so would be incredibly hard and involve lots of linear algebra – if indeed it’s even possible.

I feel like it’s probably impossible, but I’m not completely sure.

I suspect the intended solution is to take an entirely different approach, and


   use the fact that you have a rough idea of when it was seeded, and so a range for the seed values. If I know it was seeded in the last hour, there are only a few thousand possible values. I can check the first output for each possible seed value, and compare to the actual result.




(Spoiler block for anybody working through the Matasano challenges themselves)

But I’m curious whether my original approach would work. Is it impossible to go from the first output to the seed, or is there some trick that I’m missing?
Is it impossible to go from the first output to the seed, or is there some trick that I’m missing?


Yes, it is impossible, but not because the algorithm could not be reversed. If you had the whole state, you could go back to find the seed, but you need at least 624 32-bit outputs before you can uniquely find the state of MT19937 (due to the $k$-distribution property).

As @yyyyyyy mentions in the comments, seeding with a timestamp cannot produce all the possible states. However, due to collisions there will not always be a single 32-bit state that produces a particular 32-bit value as the first output, so even if you could work through the math to invert to the seed, you might not find a unique timestamp that way.

Your spoilered approach is much better.