This challenge is about the Dual_EC_DRBG random number generator, which is famous for being backdoored by the NSA so they can predict the output after reading only 32 bytes of the random stream. This excellent video should demonstrate how to generate the point $Q$ so that we can easily recover the state of the PRNG given that we know the relation of $P = dQ$, where $d$ is the secret component only known by the NSA.

For the challenge, we need to gain enough money (self.dollars >= 130), we should obtain the flag. Observing the PRNG, we can see that the PRNG is a Linear Congruential Generator, with properly randomized parameters. Let’s first discuss how to break the LCG. Denote the multiplier mul as $M$, increment inc as $I$, modulo as $N$. We can easily retrieve $M, I$ after obtaining three numbers from the LCG, denoted by $A, B, C$.

The key is generated using current_time = int(time.time()), hence if we send two request quickly, the value of current_time is the same, leading to the same key. We can reuse this key for decryption of the flag. Another idea is to generate the space of all possible keys that can be generated on the server. However, it seems like there is some time sync issue (the time on my machine is different from the time on the server), hence we will need a bigger range of time, specifically range(current_time - 100, current_time + 101), where current_time is the time measured using int(time.

We will exploit the fact that the key is randomly generated, and the ciphertext, after the assertion, will not contain the same bytes as the flag. We can issue a lot of requests to the server to slowly eliminate the space of possible characters for the unknown portion of the flag (the ???? portion). The guess space for each unknown position is the characters in the range of 33 to 127, the printable characters.

This covers the two parts of the challenge. The challenge is related to the CVE-2017-11424 key confusion vulnerability in pyJWT. This is somewhat hinted by the challenge’s description of a “patch” to enable the exploit. Looking at the commit, we see that one of the newly added invalid_strings is '-----BEGIN RSA PUBLIC KEY-----'. This implies that we can leverage the public key for some forging. Combined with this line from the source code: