6
$\begingroup$

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?

|improve this question
$\endgroup$
4
$\begingroup$

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.

|improve this answer
$\endgroup$
  • 3
    $\begingroup$ ...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. $\endgroup$ – yyyyyyy Oct 11 '15 at 16:43
  • 1
    $\begingroup$ @yyyyyyy, that's true, but with the usual algorithm 32-bit seed -> 32-bit output is not bijective, so you would not necessarily find a unique timestamp. I've edited the answer. $\endgroup$ – otus Oct 11 '15 at 17:36

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.