Entropy

The most fun and informative part about this challenge was Entropy in my opinion. As far as I understand Entropy is the way of measuring information in units of bits. The idea is so much more then representing integers with bits. The idea is having information about what set or objects you have at hand, every additional bit you learn doubles your information. So if you have 16 objects in a set and you have knowledge about 2 bits, then you can guess the right one in one out of four times.

The idea is that the objects you have are represented by one of the 16 combinations of the 4 bits and as you learn any 1 bit information you eliminate half of the group you have.

As you can learn an additional bit to cut your set in half you can search as many as your objects to learn an additional bit, so if you have four objects and you see an additional four objects then you can gain one more additional bit of information about the object you are looking for.

This challenge utilezes a similar idea to recover a mersenne twister.

Mersenne Twister

I won’t be explaining what mersenne twister is or assume I even know how it works. You can find it out by a quick google search, the wikipedia pages of both entropy and mersenne twister cracker.

The main idea is that there is a very large prime number called Mersenne prime ($2^{19937}-1$) and we somehow use this prime number with a seed to get bunch of random numbers.

But there is of course a catch!

If you don’t change the seed and let the mersenne twister generate enough outputs (624 times 32 bit values to be exact) you can one shot the seed using a mersenne twister cracker. How exactly? With mersenne twister crackers. I used the following one with combination of z3: icemonster’s symbolic mersenne cracker also I used the following wordle solver.

How to solve the Challenge

First let’s discuss how to win the challenge. The challenge consist of wordle rounds, 3000 rounds to be exact (this is actually an important value), if you manage to win 20 rounds back to back on first try you would get to the final stage which is outputting the write letter of LAIN according to the previous leak, which is a 2 bit value.

As you checkout the server.py file of the challenge first think you see that server creates a Random object and seeds it with 32 bytes random value from the operationg systems (“hopefully secure”) random generator, and never reseeds the Random object.

93    rng = random.Random(os.urandom(32))

Then we call the get_next_word() function to generate our next wordle challenge. This part is where the magic happens!

64def get_next_word(rng: random.Random, cache: list[int], wordlist: list[str]):
65    if not cache:
66        value = rng.getrandbits(32)
67        cache.extend([(value >> 16) & 0xFFFF, value & 0xFFFF])
68    idx_raw = cache.pop(0)
69    useful_bits = math.ceil(math.log2(len(wordlist)))
70    idx = idx_raw & ((1 << useful_bits) - 1)
71    if idx >= len(wordlist):
72        idx ^= 1 << (useful_bits - 1)
73    # Return the word and the next 2 bits (bits 13 and 12 of the chunk)
74    return wordlist[idx], (idx_raw >> 12) & 3

In wordle (or in original wordle, check out the video) there are 2315 words to choose from, so $\lceil \log_2(2315) \rceil = 12$ bits is more then enough to decide between which word to choose, but the server calls for a value = rng.getrandbits(32) 32 bit value whenever its cache is empty. This means that every odd round we generate a 32 bit value use upper 16 bits of it then store the lower 16 bits in the cache to use in the next round.

Then as I said we only need little more then 11 bits we get the lower 12 bits of the 16 bit value and get rid of the 11th bit (zero indexed) if the value we left with is larger or equal 2315. This creates a problem as for values between 267 and 2047 (both included) you don’t know what the 11th bit is, but I guess to compansate for this loss or just for the last round to get the flag the server generously leaks 2 bits of information.

So if you run the wordle solver 1248 rounds and win you will generate 624 times 32 bit values, exactly the information we need. That means you create enough information to crack the seed, but there is only one problem. You do not see all of this information, the challenge gives you guaranteed 11 bits of information from the result of the wordle round, sometimes the extra one bit of information if the word is in the correct range, and 2 bits from the leak (for free).

You are always gauranteed to have 13 bits of information. Is this enough? Apparently not!

Why?

Altough you get gauranteed 13 bits of information, you actually need 14 bits, because you need to match the leak, the word and the 11th bit, but the upper most 2 bits could be anything (I think), but the lower 14 bits should exactly match our original 1248 rounds or we cannot guess the next round correctly.

So the question is how do you gain one more bit of information?

You double what you learn and you compansate for the 11th bit you are losing with the xor operation on line 72

71if idx >= len(wordlist):
72        idx ^= 1 << (useful_bits - 1)

Instead of 1248 rounds you need to play the wordle 2496 rounds, which is conveniently still under 3000 rounds with room for our 20 round winning streak.

In Conclusion

To win the challenge you need to play 2496 wordle rounds let the mersenne twister cracker or z3 find viable solutions for the mersenne twister (I think we dont have to find the exact seed match, lower 14 bits of every 16 bit value is enough), then we iterate 20 more rounds with guessing the next 32 bit value, use that value with servers logic to guess the next 20 values, and output the right character of LAIN according to the last leak value we see.

Here is my solution to the challenge