I created this challenge and Neobeo helped me playtest this more than an year ago. It was (of course) initiated from playing the challenge Coinflip from MapleCTF 2023. I spend some time to find a better seed for this challenge.

The original solution was making a single bit, the seed-forced bit to one and all the other zero, which works because the bit spreads every twist, but not dramatically. This solution gives the result 1824222, which is not enough for a solve.

To solve the challenge, as all solvers know, the key is to make small hammingweight in the middle state, not the first. According to the construction, the inverse spreading speed is higher than the original spreading speed, but still not ignorably high. This drawing is the simple explanation of the solution.

Every solutions were based on setting a single index nonzero. A single bit with 0x80000000 can make up to 1599320, and unexpectedly, 0x6422c37e can make up to 1586822. See solve.py for getting the seed for both solutions.

Then, it makes sense that a single bit can make the state hammingweight small, but what's up with 0x6422c37e? A fun fact is that lydxn actually was the first person to come up with the initial value 0x6422c37e, but sean9892 was quicker to find the actual best based on the fact MT19937 is circular. Understanding about the circular part, reduced.py will be helpful.

It can be easily found that that constant has a deep relation with the twist constant 0x9908b0df.

sean9892 elaborated by saying: After noticing the twist was kind of a Quotient Ring over F2, using xbar^-2 was helpful.

One funny thing is that, the constant 0x6422c37e is only related to 0x9908b0df and nothing related to the tempering algorithm. However when I checked the best possible result from inverting those initial values, 0x80000000 had actually around 10000 bit advantage when it was pre-tempered instead. Check out compare.py.

There is no guarantee that 1586822 is the best possible score, so it would be awesome if you manage to find a better one and share me or release it somewhere.

Merry Christmas and a happy new year.