Buggy Time Machine

I am the Doctor and I am in huge trouble. Rumors have it, you are the best time machine engineer in the galaxy. I recently bought a new randomiser for Tardis on Yquantine, but it must be counterfeit. Now every time I want to time travel, I will end up in a random year. Could you help me fix this? I need to find Amy and Rory! Daleks are after us. Did I say I am the Doctor?

Category: Crypto

Solver: miroka

Description

In this challenge, a python-script for the creation of a Flask web server was given.

The setting is a crazy time machine.

The python Flask server script contained the following HTTP routes:

• /next_year (GET)
• /predict_year (POST)
• /travelTo2020 (POST)
• / (GET)

The crazyness comes from an (iteratively) applied function of the form (x * y + z) mod n with unknown x, y, z, and n. All you can get is

• the result with x being the previous result
• OR the result for a given x, but only after unknown, but constant many iterations.

You win the challenge and get the flag, if you can provide an x (called seed) such that the result after hops many iterations is 2020.

Walkthrough

You can find the solution code in the jupyter notebook (a nice and visual python shell) called solution.ipynb or in the PDF solution.pdf that has been exported from that.

An adapted version of the given python server can be seen in the file my private public test server.py. Mostly, it was adapted to enable local execution.

Steps

1. Set some imagined values for the unknown variables to understand in general, what the procedures are calculating.
2. Come to the result that the seed value is effectively unguessable and the whole system looks chaotic.
3. Write some helper functions to enable programmatic calls to the web server. Use the locally deployed test server for debugging. For me it also helped to see some raw requests from my code to understand why my requests failed so many times. For this I have used the program netcat as a TCP server using nc -l 0.0.0.0 8080 (nc -l <listening address> <listening port>).
4. Recognize that the online deployed web server and the given web server script differ in a detail: The route /travelTo2020 does not only fail if the time machine’s travel year does not equal to 2020, it also returns the result year that was calculated instead.
5. Perform some useless calculations and tests: Measure, how long a single time travel takes, how long a specific time travel (aiming at the year 2020) takes and how much of this time the network round-trip time takes up. This approach aimed at estimating a lower boundary for the hops variable, because the main (expensive) calculations in the specific time travel are done hops times as compared to 1 time in the single time travel. Therefore, the hops variable should be at least 20. However, this calculation is really inaccurate and seems useless, because the other calculations are still too complex.
6. Let’s just predict some years for given seeds using the /travelTo2020 route. We initially chose the seeds 0 to 19, to keep the math simple. It became obvious, that the seed and the predicted year increase proportionally for small seeds until an ‘overflow’ happens. Even then, the predicted years increase linearly. Therefore, even though the method is a black box, the outer ‘function’ seems to be of the form year = (seed * x) mod n. x seems to be a base_year and equals the result for seed=1. By looking at the overflow, one can also calculate n using the following code modulo_n = seeds[5] * base_year - years[5] with the overflow happening between seed=4 and seed=5. For further explanations, look into the solution code.
7. Let’s quickly check the assumpted equation for correctness for the first 100 seeds and corresponding years and be happy about 100 Trues.
8. The last part of the challenge is to find a seed such that the predicted year is 2020. Therefore, solve the equation seed * 430046689 % 2147483647 == 2020, preferably by putting it into an online solver like wolframalpha.com: solve x * 430046689 mod 2147483647 = 2020 and get x = 4260992388 = seed
9. Quickly check the found seed by inserting it into the found equation: 4260992388* 430046689 % 2147483647 == 2020 evaluates to True.
10. Send the seed to the web server (jump_to_2020(4260992388)) and get {'flag': 'HTB{l1n34r_c0n9ru3nc35_4nd_prn91Zz}'}.
11. The flag is HTB{l1n34r_c0n9ru3nc35_4nd_prn91Zz}

Fun Facts

• The used modulo_n = 2147483647 = 2^31 − 1 was the largest known prime number until 1867.
• You can find the dumped website in the folder website_dump. I especially like the audio file website_dump/static/soundtrack.mp3. However, as far as I know, there is no challenge hidden in the website dump, but it looks really nice!

See for yourself: