4
$\begingroup$

Someone generated a seed for the Mersenne Twister, with the intent of that seed producing this string:

"9!dlroW ,olleH"ck,@

Which is 20 characters long. Why he did it is explained below, but I don't know how he hacked it.

Why he did it:

The user feersum on Code Golf did this to generate a Hello, World! program in the Seed programming language. Obviously he didn't merely brute force his way to this seed, which is 4200 digits in length. How did he do this? Furthermore, this user has other answers in which he uses what is presumably the same trick, see: this answer.

What we know: The seeds tend to be quite large (much larger than if they were brute forced by addition-and-generation). Furthermore, every seed he finds must generate 624 integers with the seed before twisting the next 20 to produce the above string's numerical data. The complexity to brute force a string of n length is O(96^n), very complex indeed.

What I suspect: He filters what seeds he generates in such a way as to reduce the complexity for n length to about O(log(96^n)), which simplifies to O(1). I don't think that "he has access to a supercomputer" is a viable answer.

An acceptable answer: Anything which explains how he might have done this, even if he actually did it differently. It might take a long time for the answer to this to be known.

Interesting Mersenne Twister trivia: You can generate the state of the Mersenne twister with as little as 624 outputs, then predicting future output from it.

Note: Several bounties were pledged on the Hello, World! question for him if he were to explain how he did it. Years have passed, and he is not budging. Maybe those bounties will be passed on to you for having explained this.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ The question would get a better chance to get answered and be deemed on-topic if it came with 1) a description of how exactly, in the Seed programming language, the seed input is processed; or at least, a link to the source of the relevant interpreter, for the part that acquires the seed number, setups the Mersene Twister, and turns its output into a Befunge program. 2) Said Befunge program, which if I get it correctly is a mere 20 ASCII characters. $\endgroup$
    – fgrieu ♦
    Commented Apr 12, 2018 at 16:45
  • 1
    $\begingroup$ @fgrieu The Befunge program is in the question, in a code block. The Befunge generates the Hello, World output. The seed programming language is explained in the links, but I will rehash it in this comment: You execute the Seed interpreter (supplied in the link) with a length argument and a seed argument. The seed is used in the Mersenne Twister to generate length-argument number of characters. Those characters are executed in the Befunge programming language. $\endgroup$
    – Spenser Truex
    Commented Apr 15, 2018 at 1:07

1 Answer 1

Reset to default
6
$\begingroup$

How did he do this?

Actually, you gave much of it away when you mentioned:

You can generate the state of the Mersenne twister with as little as 624 outputs, then predicting future output from it.

This is true, but you can do other things with it. You can also generate previous output (that is, what the Mersenne twister output would be on blocks previous to the one you saw),previous states (that is, what the twister state had to be so that, after an iteration of the twister, you would get the selected state) and also compute the necessary seed to obtain a specific state.

Hence, most likely here's what he did:

  • Created an output of 624 integers, which consisted of the "9!dlroW ,olleH"ck,@ (which is 20 bytes or 5 integers), along with 619 arbitrary values. These last 619 integers will be ignored, and hence it doesn't matter what values you select for them.

  • Reconstructed the internal twister state needed to generate this output.

  • Generated the previous twister state needed to generate this state after going through the twister permutation

  • Generated the seed needed to generate this twister state

And that's it. The above is a bit tedious to do by hand; it'd be fairly trivial for a program.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 624 integers is a bit larger than the state of MT, so if you just pick them, they may not match any state. You may have to repeat several times. Or possibly leave the last Integer semi free, when processing. $\endgroup$
    – Meir Maor
    Commented Apr 15, 2018 at 6:17
  • 1
    $\begingroup$ This answer makes sense. I hadn't put together the fact that you could generate the seed from the state. I am used to the "one-way" feature of cryptographically secure algorithms, which is interlinked with the "can't generate state from outputs" feature. Thank you! $\endgroup$
    – Spenser Truex
    Commented Apr 15, 2018 at 21:34
  • $\begingroup$ This page contains multiple implementations: kspalaiologos.now.im/old.php?id=9 $\endgroup$
    – J.A.K.
    Commented Nov 25, 2020 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.