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?