PicoCTF — seed-sPRiNG Walkthrough

The challenge prompt

This challenge is different than all the preceding challenges in the picoGym in the sense that unlike the previous ones, this one doesn’t need you to exploit any vulnerability in the binary itself, but rather attack the logic implemented in the executable to show that it’s vulnerable.

Prerequisites

• Nothing much really, read on to find out why

Tools Used

• Pwntools (for the exploit script)
• GCC (to compile the pattern generator)
• Radare2 (for reversing the binary)

Understanding the Logic

Reversing the assembly

First things first, I downloaded the binary, and threw it under radare2 to observe and reverse. We don’t get any source code for this, so we need to decompile it ourselves.

The code itself is very simple and straightforward to decompile from the assembly. You can use any decompiler for this, but seeing that it was easy enough for me to understand the logic from the assembly code itself, I went ahead and decompiled it manually. Pay special attention to the for loop implemented in main() in assembly, where you see this :

/* main() */
/* Code to print the banner */
/* Code to seed rand() with current unix time */
/* Code for FOR LOOP below
...
0x000008ab      c745f4010000.  mov dword [var_ch], 1
0x000008b2      e9be000000     jmp 0x975
...
/* Code to check for correctness of the pattern guessed */
...
0x00000971      8345f401       add dword [var_ch], 1
0x00000975      837df41e       cmp dword [var_ch], 0x1e
0x00000979      0f8e38ffffff   jle 0x8b7
...
/* Code to print the flag */

Notice that the instruction at 0x8ab is actually the beginning of a for-loop, where the counter is initialized to 1, then a condition checked at 0x975 (whether this counter’s value is less than 0x1e or 30) and if true, jumps right inside the loop-block. Also notice the counter increment at 0x971 .

View the assembly code yourself, compare it side-by-side with my interpretation of the decompiled code below, and see what translates to what.

Having decompiled the code, let’s try to understand what it does. Firstly, it seeds rand() with the current unix time, then generates 30 integers one after the other in the loop, and in each iteration, asks the player to guess what the integer could be. The correct answer takes the player to the next iteration, whereas the wrong ones exit the program immediately. So, the only way to win is to guess all the numbers correctly for 30 times back-to-back. Mathematically, our chance to lose is near to a hundred percent…or is it?

Understanding the Pattern generation

Let’s see how the (seemingly) random numbers are generated. In C, the rand() function generates pseudo-random integers in the range [0,INT_MAX] when called, where INT_MAX is implementation-specific. And what are pseudo-random integers? I will be lazy and quote this definition from pcmag.com, with minor modifications:

A set of values that seem random, but is derived from a known starting point and is typically repeated over and over. … It is called “pseudo” random, because the algorithm can repeat the sequence, and the numbers are thus not entirely random.

In other words, running a program which uses rand() to generate random integers will generate the same set of numbers in exactly the same sequence no matter how many times you run the program. To overcome this problem, sometimes the function is seeded with a value that is truly unique, like the current time (because the time once passed never returns…except when it comes to snapshots :P). Seeding rand()with any value makes it return pseudo-random integers from that position in its internal list of randomly arranged numbers. What I mean by that is, imagine an internal list [1,3,7,2] being used. By default, rand() is not seeded, so calling it again and again will return these values in order: [1,3,7,2,1,3,7,2,1,3,…], i.e, the exact same list repeated back-to-back. If it is seeded with, say 2, the 2nd element in this list is chosen to be the first returned pseudo-random integer, but the original sequence in the list is still maintained. Thus you’d get something like [7,2,1,3,7,2,1,3,7,2,…]. So, is it really random? No, right?

In this program, you see this exact thing being done. The current unix time is used to seed rand(). So how do we predict the sequence such that all 30 numbers are correct? It’s simple. All we need to get our hands on, is the current unix time. By mimicking the logic of the program, we can generate all 30 numbers at once, just if we can get the time value right, to know where the sequence starts, isn’t it? Let’s tackle this first, now that we have cracked the pattern generation.

The Sequence generator

From the source code I showed in the above section, take a look at this excerpt that seeds and generates the numbers:

...
time_t seed = time(0);
srand(seed);
/* Loop that checks for correctness of user's guesses */
for(int i=1; i<=30; i++){
/* CODE TO PRINT PROMPT */
random = rand() & 15;
...

Observe the random = rand() & 15; line. All it does is a bitwise-AND operation between 15 (1111 in binary) and the pseudo-random number generated. Since between the pseudo-random number and 15, the latter is the smaller one, the result values would be equal to or less than 15 and greater than 0 (because the resultant cannot have more binary digits than the smallest operand, and thus, the bitwise-AND operation will give us something from all the 4-binary-digit permutations of 0s and 1s, meaning that the minimum and maximum you can get is 0000 or 0 and 15 or 1111). This extra operation lends no added security to the random number generator, because if you just get the current unix time (the seed value), and apply the exact same operations on it as it is done in the program no matter how complex, you have the correct sequence.

I wrote a simple C code to mimic this logic, and give us all the 30 numbers at once, with using only the current unix time as the input argument.

Sweet! But wait, if it needs the current unix time as the argument to know what the correct sequence is, and the program is running on the server and not locally, how do we even get the server’s local system time?

Toe-to-toe with Time

This is the part of the challenge that requires some creative thinking. Unix time is something whose value remains the same at any instant of time all over the world no matter what the timezone is. So, if you can just sync up your local system time with the unix time, then that must in turn get synced up with the game server’s local system time, yes? So that means that you can generate the sequence based on your local time on your machine, yes?

Well, yes and nope. Yes to the first question, because the server must be synced with unix time itself. Nope to the second one, because of network delays; if you send a request to the server at say t=0 secs, it’d never reach the destination at t=0 itself. In other words, you’d never know in advance when your request would strike the server, and since the random number generator is only seeded with the current time only after the server receives the request, you won’t get the seed value correctly with only one hit. I needed some shower-thoughts to help me think of a way that could fight this delay. And I succeeded.

Read and understand my logic carefully. Say that you sent a request to the server at t0=1611864481 seconds, and get a reply at t1=1611864487 seconds. Since you are the client, you won’t get the time when your request actually hit the server. All you’d know is when you sent the request, and when you got a reply, since you control the client-side. In this example, the time at which the server got hit with your request can be anything between 1611864481 and 1611864487, and since the random value in this code is an integer, the only possible values could be [1611864481,1611864482,1611864483,1611864484,1611864485,1611864486,1611864487].

But which one of these is the correct one? Well, we have no way of knowing that in advance, because network delays are totally unpredictable. A naive way may seem to just take the middle (average) value and hope it would be right, and if it isn’t, to try again and again till we succeed. However, the chances of this practically happening is very, very low, because is there any guarantee that the time taken by the server to receive the request will be exactly the same as the time taken for the reply to reach us? It depends on the request/reply sizes plus the network delays, which would always keep fluctuating.

Rather, a smarter way would be to simply take a random guess and choose a single value out of [1611864481,1611864482,1611864483,1611864484,1611864485,1611864486,1611864487] (considering the above example), try it, and if it fails, to try all over again, and follow the same guessing steps with the new list of possible values. This has a much higher probability of succeeding, because now your choices would cover the entire spectrum of possible values, and not just the middle (average) value.

Summarizing my algorithm

Let’s put my logic to clear, sequential steps:

1. Sync up the local system time to unix time
2. Get the current local system time (unix time).
3. Send a request to the game server.
4. Get the current local time when reply is received
5. Generate list of all possible time values when your request would have hit the server.
6. Randomly choose a value from the list and use the sequence generator to get the pseudo-random number sequence in advance that the server would generate.
7. Send the ‘guessed’ answers one-by-one from the sequence generated in the previous step, and if any of the 30 steps fail, go back to step 2 and start all over.
8. If all of the 30 ‘guessed’ answers is accepted, get the flag.

I gave myself a pat on my back when I finally formed this idea after a few hours of pondering on finding the most efficient way to tackle this time problem.

Defeating Time

Next, I put my abstract idea into action by writing out a script to follow the steps as shown above. Here’s the script I wrote:

All this is just fancy talk till now, but will it work? Only time can tell (Notice the dry pun?).

Moment of truth

Below is a screenshot of one of the test runs. Turns out, my algorithm was very efficient. Have a look.

Conclusion

This challenge is a reminder that in addition to having knowledge about how things work, sometimes, you may need some creative thinking to put everything together to make everything work hand-in-hand.

I saw that this challenge was made by one of my favorite internet people, John Hammond (Twitter @_johnhammond), so a shout-out to him. Thanks for the challenge.

Also, if it isn’t the same ‘John Hammond’, please don’t tell me about it more than once, because once is enough embarrassment for me to bury my head in sand.