# 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?

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).
• ...but the usual algorithm for seeding the state from a single long is not surjective on the set of valid states! In particular, the first state word is set equal to the seed and the remaining words depend completely on the seed (obviously); however the state is transformed once before the first word is emitted. Now the question is whether one can obtain the first word of the freshly seeded state given only the first word of the twisted state, but I suspect this can be done using a little algebra. – yyyyyyy Oct 11 '15 at 16:43