picoCTF "MATRIX" Walkthrough (Caution: an extremely lengthy post)

Introduction

For this post, we are going to tackle one of the hardest challenges when it comes to the category of Reverse Engineering on picoCTF that is worth 500 points. Certainly, it was a lot harder and took more time to understand and ultimately obtain the flag than two previous challenges I completed, but it was a pretty great learning experience I would say, which taught me a good deal about the mindset and technique I should use to approach reverse engineering in general. Since the challenge is a lot harder than others, the post may be a bit longer than the usual to explain some of the findings, but I will do my best to explain things concisely and right to the point. Without further ado, let's dive in to it!

1. Analyzing the Binary

Start

Just with two previous challenges, this requires one to download the binary and examine the content inside. Let's download and import it to Ghidra for analysis.

• Here are various details regarding the binary. In some cases, there may be some noteworthy details that might aid one in finding out what one is working with, but I don't really see anything too interesting in it, so we move on to the next phase where Ghidra commences analysis.

• Let's use the default options for the analysis of the binary.

• Here we are in the part of Ghidra for examining the innards of the binary. You can check the bottom-right corner to check the progress of an analysis. Once it's done, we start analyzing it ourselves!

"Main" Function

So, the very first thing I do is to check a list of functions that might give away some hints on how we should approach the challenge. Let's check out what kind of functions it has.

I don't even see anything too noteworthy that piques my interest, and in fact, there is no main function that we usually encounter in a binary written in C. Hmm, I think this binary is written in C and compiled with GCC, but I don't see any function called main. However, there is a function called __libc_start_main, which is called inside the function entry. Let's check out the function entry.

The function __libc_start_main is provided with the total 7 arguments. There are a few interesting arguments worth checking out. In Ghidra, any function that cannot be named, due to it being stripped during the compilation process or for some reason, gets assigned a random name that starts with the substring FUN_. As you can see, there are a few arguments whose name starts with the substring FUN_. So what one can deduce is that one of the functions passed to the function __libc_start_main is called when the program starts? Rummaging through the Internet, I come across this help page for the function __libc_start_main.

The page basically states that the function __libc_start_main is called to initialize the environment for a process, prior to executing the main function we call. The very first argument passed to the function is actually a function pointer for the main function that will be executed, once the preparation for running a process is done. The name of the function we must check out is FUN_001010d0. Let's move on to checking out the very function FUN_001010d0.

Seems like we are at the right place to start figuring out how things work!

• In the screenshot right above this paragraph, line 39 outputs the string Have a flag!, which subsequently in the next line outputs the flag we need to complete the challenge. Since we are in the initial stage of analysis, it is still very unclear what we should do to lead the binary to output the flag in general. Let's investigate the function for more clues.
• From line 32 to 34, it repeatedly calls the function FUN_00101350 inside the do...while block. The function FUN_00101350 is provided with total two arguments, &local_168 and local_16c. In line 37, it checks the first value of local_16c to see if it amounts to a NULL byte (0), and once it checks that it is indeed a NULL byte, it proceeds to the next line to check whether the value of the variable local_16a is a NULL byte as well. Based on the information I laid out, you can presume that the variable local_16c is passed to the function FUN_00101350, and somehow gets modified after each execution. The character & indicates that it accepts the address of the variable local_168. So what does the variable &local_168, the first argument of the function FUN_00101350, contain?

• The variable local_16a gets assigned the address of the data DAT_001020f0. Since its name starts with the substring DAT_, we can presume that it may be pointing to a constant data that is located somewhere within the binary. Let's check out what data it contains.

Okay, we end up at the address of 0x1020f0, and it contains a byte, which is equal to the value of 0x81. And in the next bytes, the values 0x75, 0x00, 0x80 are laid out. Still not sure about its purpose. After further investigating and scrolling around, I find something interesting.

• Let's read this thing from bottom to top: m a k e i t o u t a l i v e ?.

• Another interesting artifacts that read like the following, when you read it from bottom to top: Congratulations,.

Actually, let's run the binary in a VM to check out how it works at face value.

• Okay, at the outset, it actually outputs the message WELCOME to the M A T R I X \n Can you make it out alive?. Did you notice that at the last part of the output, it contains the substring make it out alive? that we found during the analysis of the binary?
• Subsequently, I input a random string to see what happens, and press ENTER, and am instantly greeted with the message You were eaten by a grue.
• So, I basically have to provide the right password to the binary to eventually obtain the flag. What's the right password? Let's go back to Ghidra and investigate further statically.

Exploring the function "FUN_00101350"

Back to Ghidra! Since the function FUN_00101350 seems to be the one that dictates the overall flow of the binary, it's time to check out its contents.

Okay, so this is quite a lot to digest, with nearly 200 lines of code welcoming us right before our eyes. Nonetheless, we have to go over the entirety of the function, in order to figure out what's going on.

Here are some references that you should know prior to continuing. These will be referenced throughout the post, and will greatly help you understand how things work basically:

• param_1[0] (param_1 + 0 bytes == 0x00007fffffffdfc0) - holds the address 0x1020f0 (0x00005555555560f0), from which the real program starts. When the function FUN_00101350 gets invoked, the binary passes the address 0x00007fffffffdfc0 to the FUN_00101350 as the first argument.
• param_1[1] (param_1 + 8 bytes == 0x00007fffffffdfc8) - holds the offset of two bytes, with which the address, at which the current command is located, is calculated, by adding 0x1020f0 to the offset.
• param_1[2] (param_1 + 16 bytes == 0x00007fffffffdfd0) - holds the address of the top of one of the makeshift stacks. This stack gets used the most often. The starting address of the stack is at
• param_1[3] (param_1 + 24 bytes == 0x00007fffffffdfd8) - holds the address of the top of one of the makeshift stacks. This stack gets used the least often and is mainly for temporarily storing values needed in another stack.

• The register r12 stores the lowest address of the stack at param_1[3], which is 0x0000555555559ab0.
• The register r13 stores the lowest address of the stack at param_1[2], which is 0x00005555555592a0.
  • Every item on the stack is 2 bytes worth, which means that an item occupies 4 digits at once. And also, considering the fact that the binary is in little-endian, the value starts from the right, so you can read like 0x0001|0001|0000|0061. In the screenshot above, the address at 0x00005555555592a6 holds the value 0061, which is basically the hexadecimal value of a in ASCII. a is the very first character of the input I provided to the binary. So I assume that every character gets placed at the exact address of 0x00005555555592a6 for processing. What about 0x0001|0001|0000| in the front? We will see what they represent.

• At this point, all we know is that the function receives two arguments, the first one being a pointer to another pointer - &local_168 gets passed as the first argument, and & indicates the memory address of the variable local_168. local_168, by the way, is assigned an address of 0x1020f0 prior to entering this function - local_168 = &DAT_001020f0; - so we know for sure that it is a pointer.
• In line 17, the binary dereferences the pointer param_1, whose value is 0x00007fffffffdfc0, and assigns it to the variable lVar4. lVar4 ends up with the address of 0x1020f0.
• In line 18, it adds 1 to the argument param_1, which becomes 0x00007fffffffdfc8. Since param_1 is a pointer of the long type (8 bytes), when you add 1 to it, it is equal to adding 8. And then it change its type from long * to ushort *, which means that it turns into a pointer that can reference up to two bytes only. And lastly, it dereferences the pointer - the first two bytes from the address of param_1 + 1 (0x00007fffffffdfc8) - and assigns it to the variable uVar2.
• In line 19, the binary adds the value of the variable uVar2 to 1, and assigns it to the variable uVar9.
• In line 20, the binary assigns the value of uVar9 to the address param_1 + 1 (0x00007fffffffdfc8). The value at param_1 + 1 increments.
• In line 21, it adds the address 0x1020f0 (0x00005555555560f0) stored in the variable lVar4 to the value of uVar2, which results in the address bigger than 0x1020f0, subsequently converts its type from long * to byte *, and lastly dereference it to fetch a byte from the calculated address.
• Summary - The variable uVar2 in line 18 holds the offset, which in line 21 is added to the address 0x1020f0 and subsequently dereferenced for a command that needs to be executed. Let's see what kind of commands there are by going through the screenshots below.

Going through the screenshots, you may notice that there are some notable case clauses with the following values:

• 0 (0x00)
• 1 (0x01)
• 0x10 - 0x14
• 0x20 - 0x21
• 0x30 - 0x34
• default - 0x80 - 0x81, 0xc0 - 0xc1

Each case clause performs different functions for the binary, but one thing in common is that the most of them use the line at the beginning to fetch the address of the top of the stack at param_1[2]. The binary actually utilizes two makeshift stacks to store various data needed in calculation. The memory address at param_1[2] stores the top address of one of the makeshift stacks that the binary uses. Stacks used in this binary consist of values up to 2 bytes each, so when the binary pushes or pops the stack, the address of the top of the stack increases or decreases by two bytes.

Explaining what each value does in detail may be way too time-consuming, so instead, I will give you the brief explanations of what each does.

• 0 - It doesn't do anything

• 1 - Executing this results in the end of the binary. This is where the binary determines whether you have successfully finished the challenge.

• 0x10 - Copies the value at the top of the stack (-0x2) and pushes to the stack at param_1[2], basically duplicating the value. The value at param_1[2] increases by 2.

• 0x11 - Pops the stack, whose value at param_1[2] decreases by 2.

• 0x12 - Adds the value at the top of the stack (-0x2) to the value of the item right below (-0x4), and store it at the offset (-0x4). Then pops the stack.

• 0x13 - Subtracts the value at the top of the stack (-0x2) to the value of the item right after (-0x4), and store it at the offset (-0x4). Then pops the stack.

• 0x14 - Swap the value at the top of the stack (-0x2) with one right after (-0x4).

• 0x20 - This involves two stacks - the one at param_1[2] and param_1[3]. The top of the stack param_1[2] pops and pushes to the stack at param_1[3].

• 0x21 - This involves two stacks - the one at param_1[2] and param_1[3]. The top of the stack param_1[3] pops and pushes to the stack at param_1[2].

• [0x30] - Pops the top of the stack at param_1[2] and puts the offset at param_1[1]. This is where we increments and stores the value in line 20 of the function. It basically changes the flow of the program.

• [0x31] - Pops the top of the stack at param_1[2] TWICE. If the second popped item has the value of 0x0000, then change the offset at param_1[1] to that of the first popped item.

• 0x80 - Pushes the value of a byte to the stack param_1[2]. Increases the offset at param_1[1] by 2.

• 0x81 - Pushes the value of two bytes to the stack param_1[2]. Increases the offset at param_1[1] by 3.

• 0xc0 - Accepts the input from a user.

• 0xc1 - Outputs whatever is on the stack param_1[2].

Most of the commands above only increment the offset at param_1[1] by a number from one to three at most, but ones that are surrounded by square brackets (0x30 and 0x31) drastically change the offset using the value stored on the stack param_1[2], which means that they kind of act like the JMP instruction in Assembly.

Okay, so basically the offset at param_1[1] starts with the value 0, which means that if you add the value 0 to the base address 0x1020f0, it results in the address of 0x1020f0. The very first command located at that address is the following:

• There is a byte value of 0x81 at the address 0x1020f0. Revisiting the explanation on the command related to the byte 0x81, we know that it has to do with pushing the value of two bytes to the stack param_1[2]. So which value does it push to the stack? It combines the next two bytes (0x1020f1 => 0x75, 0x1020f2 => 0x00) after the current address 0x1020f0, pushes the very combined value 0x0075 to the stack param_1[2], and lastly, increases the offset at param_1[1] by 3, which results in the next command at the address 0x1020f3 => 0x80.

The very next command 0x80 at 0x1020f3 is also really similar to that of 0x81, albeit it pushes only the value of one byte located right after the given address to the top of the stack, and increases the offset at param_1[1] by 2. So why does it try to achieve from pushing a bunch of bytes to the stack? When you run the binary, it actually outputs the intro message before you have to input an answer. Basically, it is preparing to output the message Welcome to the M A T R I X\nCan you make it out alive?!

Once it fully pushes all the necessary bytes to the stack, it eventually reaches the address 0x102161, which holds the byte 0x81. It pushes the value 0x013b to the top of the stack, increases the offset by 3, and proceeds to the next command 0x30 at 0x102164. At this point, the very value at the top of the stack at param_1[2] is 0x013b. The command 0x30 pops the stack at param_1[2] to param_1[1]. The next command after this will be calculated by adding 0x013b at param_1[1] to the base address 0x1020f0, which results in the address 0x10222b.

Having learned how the binary works, one thing that comes to my mind is basically this: At which address does it accept our input? Let's go back to the dynamic analysis of the binary and check the address at which we wind up for providing our answer to the binary.

One way to figure out the offset at which the command for accepting an input from a user is to stop the process upon the invocation of the function that accepts the input! Upon going through Ghidra, we discover the following code.

• Inside the main function FUN_001010d0, we discover the lines above, at which the pointers to some unknown functions are passed to the variables. Let's click each function and where we end up at.

Clicking the function FUN_00101320, we end up at the address 0x101320. Inside it, we discover the line that calls the function getc whose argument is stdin. The function getc alongside stdin as the argument causes the program to stop and accept an input from a user! So what we have to do right now is to stop the program upon the process calling the function getc. And then skipping a few steps, we end up finding out the exact address, at which the command for accepting an input from a user gets invoked.

The process stops upon entering the function getc. With that, I type the GDB command next multiple times, until the program accepts an input from a user. I type in asdfasdfasdfasdf and press ENTER to continue.

Eventually, the process exits the function getc and returns back to the function FUN_00101320. One thing to note is that the instruction for calling the function getc is located at 0x55555555532b inside the function FUN_00101320. Let's briefly go back to check out the line that is responsible for calling the function FUN_00101320. In order to do that, we go back to GDB and type the command si a few times, until we exit the function FUN_00101320.

We wind up at the address 0x5555555555c5. Going back to Ghidra and searching for any address that ends with 5c5, we find the following:

The last two screenshots contain the identical instructions, and upon clicking the instruction at the address of 001015c5 in Ghidra, we learn that the command c0 is responsible for accepting an input from a user.

The very next offset at param_1[1] after accepting an input from a user is 0x7c, and it is stored in the rax register. We know this for sure, for the fact that inside the function FUN_00101350, it passes the offset to the variable uVar2. When you click the variable uVar2 and checks the assembly code to see which line is associated with the line, you see that the instruction at the address 00101357 passes the value to the rax register.

Processing input from a user

Adding the offset 0x7c to the base address 0x1020f0 results in the address 0x10216c.

Let's basically go through what is going on above. The only valid characters that the binary accepts for an input are the followings:

• u
• d
• l
• r

Providing a character other than those above results in the binary outputting the message You were eaten by a grue. This is how it works.

1. After accepting an input, the binary pushes the first character of your input to the stack at param_1[2].
2. It first pushes the value 0x75, a hex value for the character u, to the top of the stack at param_1[2].
3. Using the command 0x13, it subtracts the first character of your input from the value at the top of the stack, which is 0x75, pops the stack, and replaces the value at the top of the stack with the calculation result.
4. It then pushes the new offset value that may potentially replace the offset at param_1[1] to the stack.
5. Using the command 0x31, if the calculation result is 0, it replaces the offset at param_1[1] with the new offset value that was pushed to the stack at param_1[2] in the previous step. Lastly, the stack at param_1[2] pops twice. If the calculation result is not zero, proceeds to the next step:
   • u --> 0x102190
   • d --> 0x10219a
   • l --> 0x1021a4
   • r --> 0x1021b0
6. The steps 2-5 repeat until a character matches 0x64 == d, 0x6c == l, or 0x72 == r. If not, you fail the challenge, and are greeted with the message You were eaten by a grue. Once the binary pushes the value 0x00FB to the stack at param_1[2], you can assure that you are doomed to fail the challenge, because the offset 0xFB added to the base address 0x1020f0 is the very address for printing out the message for the failure of the challenge!

A series of characters consisting of those characters? u means UP, d means DOWN, l means LEFT, and r means RIGHT. Yes, you are basically navigating the maze that a single wrong step leads to your demise.

Creating the script that simulates the binary

So far, we have extensively covered the binary. It's really grueling to manually go through every single command to fully keep track of how the binary works. Starting at the base address 0x1020f0, it ends at the address 0x1026c1, which means that there are about a thousand of the commands to go through to fully understand the inner-workings of the binary. Going through this manually might take forever to cover every little detail it contains. What about creating a Python script that simulates the inner-workings of the binary? That's what I set out to do.

Why creating a script that replicates the inner-workings of the binary? I can fully control and observe how the state of both stacks at param_1[2] and param_1[3] changes after processing each character, without the help of GDB, outside the VM.

In order to replicate the inner-workings of the binary, we have to sort of understand how the binary works right after it accepts an input from a user. Some of the things we will take into considerations are the followings:

• The state of the stack at param_1[2] - With every character being processed by the binary, the binary produces a sort of accumulative results and saved them to the stack for future calculations.
• The state of the stack at param_1[3], which is temporarily used for storing data from the stack at param_1[2].
• How each command manipulates those two stacks above - The commands we discussed above directly manipulates the stack at param_1[2].

Here is how I came up with the script that simulates the binary:

1. Parse all the available commands starting from the address of 0x1020f0 to the address of 0x1026c1, since those are what the function FUN_00101350 executes into the JSON file.
2. Create a script that simulates the binary.

Creating a map of the maze inside the binary

The only allowed characters are u, d, l, and r, as an input, and we can presume that those are characters used to navigate the maze that somehow leads to the exit. So, if there is the maze, can we actually map it? One thing that we have to take into consideration is that any step that leads the offset at param_1[1] to become 0x00FB is to be avoided! Let's go back to Ghidra and go through the list of commands a bit to find all the the addresses with the value of fb.

• There are a lot of 0xfb in a list of commands from the base address 0x1020f0 to 0x1026c1.
• The first address with 0xfb is 0x0010218d. This address actually is not that relevant to the maze, since 0xfb at this address is pushed to the stack at param_1[2] upon finding out that one of the characters of an input of a user is not u, d, l, r.
• The really interesting address with the value of 0xfb starts at the very next address 0x102265. The next values of 0xfb are found at the address 0x102269, 0x10226d, 0x102271, etc. 0xfb is placed next to each other at the offset of 4 bytes consistently, which continues until the address of 0x102667, the one with the last value of 0xfb.

Starting from the first relevant address 0x102265 that contains the value of 0xfb and scrolling down the list of commands, you notice that every value 0xfb is preceded by the value of 0x81, which makes sense since the command 0x81 is used to push the value of two bytes located right next to it. Basically, 0x81 pushes the value of 0x00fb to the stack, prior to the command 0x30 changing the value of the offset at param_1[1].

Okay, so what we are sure about is that the actual map may be starting from the address of 0x102264, which holds the value of 0x81. Increasing the address in increments of 4, you notice that each address ends up with either the value of 0x81 or 0x30. 0x30's are definitely safe, for the fact that it doesn't replace the offset at param_1[1] with the value of 0xFB.

The address 0x102664 is the last address in increments of 4 starting from the address 0x102264, before the last value of 0xFB at the address 0x102267. So if I were to subtract 0x102264 from 0x102664, I get the value of 1024 in decimal. Considering the fact that the binary increases the address in increments of 4, dividing 1024 by 4 results in the value of 256. If you multiply 16 by 16, you get 256. Are we dealing with a 16 * 16 grid? With that very conjecture, let's create a simple Python script for visualizing the maze.

Here is what I did:

1. Create a two dimensional array for storing 16 arrays of 16 elements.
2. Starting from the address at 0x102264, you evaluate the followings:
   • If the value at the address is 0x81, and the value at the very next address is 0xFB, you are dead. Mark it with -
   • If the value at the address is 0x81, and the value at the very next address is not 0xFB, you are alive. Mark it with O
   • If the value at the address is 0x30, you are alive. Mark it with O
3. Increase the address in increments of 4, and repeat the step 2, until the last address of 0x102664.

When you run the script above and output the grid, you get the following result.

That looks like a breakthrough! So, where do we actually start the maze from? It's got to be the very first corner at the top left of the maze, and our goal is to get out of the maze through the only exit at the bottom right corner.

If we were to start from the top left, we can technically exit the maze with the following: rrrddrrrrrrddddddlllllddrrrrdddrruuuruuuuuuurrddddddddlddrd. Let's see if it works or not.

It is wrong! Frustrating. Let's check out why we got it wrong and how we can fix this, by analyzing the binary. The key to analyzing why we got it wrong is checking the states of those two stacks at param_1[2] amd param_1[3].

Analysis of the first failed attempt

Let's modify the script that simulates the binary for debugging purposes, by having a look at the stacks.

So moving right three times seems perfectly okay, and interestingly increments the value at the lowest item on the stack at param_1[2] by 1 with each move to the right. The problem occurs when we try to move downwards. Let's see what is being pushed at the very address that seems to be causing the problem. Starting from the very first item in the 2-D array we created for visualizing the grid, we wind up at the address 0x1022F4.

The address 0x1022F4 holds the value of 0x81, and it seems to push the value of 0x0574 and ultimately replace the offset at param_1[1] with it. Are there several addresses with the value of 0x0574 in the list of commands?

There are about 5 addresses between the address of 0x102264 and 0x102664 with the value of 0x74. Let's factor that into the map, fix the script, and see the difference between the previous one and the new one.

I marked every address that pushes 0x574 with the plus sign, and yes, they are all placed in the path to the exit. So, how do we possibly pass this? In midst of trying various methods, I find something very, very interesting.

So I know for sure that, from the starting point, I can move to the right the five times max, and when I do that, the third value from the lowest on the stack at param_1[2] increments by 1. Is the third value from the lowest on the stack the key to passing through the plus sign that we discovered earlier? Let's go back to the starting point, and see if we can move downward this time.

I was able to move downward with the input rrrrrlllllrrrdd! The third value from the lowest on the stack decrements by 1, whenever you go past the plus sign! So, since there are total five plus signs that we have to get past, in order to exit the maze, that means that the third value from the lowest on the stack must be at least 5. With that in mind, let's create the input and check if it works.

I provide the input rrrrrlllllrrrrrlllllrrrrrlllllrrrrrlllllrrrrrlllllrrrddrrrrrrddddddlllllddrrrrdddrruuuruuuuuuurrddddddddlddrd, and yes, it seems like I got it right! Let's try it on the binary being run on the server by picoCTF, and obtain the flag!

Yay! I got the flag, and submit it for the whopping 500 points!

This is the end of the walkthrough, but I feel like I didn't explain about how I came to the conclusions in some parts. I will review this post and revise and fill in some of the missing parts from time to time! Thanks for reading!

Link to the scripts I made for this challenge