picoCTF "Classic Crackme 0x100" Walkthrough

Introduction

In this post, we are going to go through the walkthrough for the challenge of Classic Crackme 0x100 on picoCTF. The last post was also about one of the challenges hosted by picoCTF, but this one is a lot harder for the fact that it awards much more points than the last one (+200 points more)! Indeed, it felt a lot harder than the last one, for the fact that it is more complex and involves a bit more thinking on understanding the mechanism by which this binary works; however, just like the last one, this challenges involves decompiling the binary and finding the flag for the challenge. To get the flag, I used tools such as Ghidra and a custom Python script, and was able to solve it after a few tries for some time. Let's go and pwn this!

Classic Crackme 0x100

Just like the last challenge I completed, we need to download the binary and examine its content to find the flag we need to submit for the completion of the challenge. Let's download it and examine it with the tool Ghidra.

1. Examine the binary

• The name of the binary is crackme100. It is basically a binary that can be run in x86_64 Linux systems.

• This shows a list of options that you may use to examine a binary. Let's just leave it as it is and analyze the binary on default options.

• Okay, we entered the screen that displays the result of a decompiled binary. The first thing I do is to check out a list of functions that exist within a binary and see if there is anything interesting. Let's check out a list of its functions.

• Checking out the list of its functions, I couldn't find any function with an interesting name, which naturally led me to examining the function main, which is the entry point for every binary that is written in C.

Upon checking out the function, we notice a few interesting points that hints at capturing the flag.

• In line 33, it has a function called printf displaying the text to the screen for instructing a user to enter the secret password. So, with that, you can easily assume that it has something to do with a user providing its input and checking if it is indeed the password that the binary is looking for.
• From line 51 to line 55, it seems to compare the contents of two different pointers, which made me assume that they are both pointing to addresses containing the string. Once the comparison is made, when both match with one another, the binary jumps to line 53, which displays the following string to a screen: SUCCESS! Here is your flag: %s\n","picoCTF{sample_flag}.

Okay, so what is the exact password that one needs to provide, in order to complete this challenge?

• From line 25 to line 31, there are five variables holding the hexadecimal values of the size of 8 bytes each, one variable holding a hexadecimal value of the size of 7 bytes, and lastly, another variable holding a hexadecimal value of the size of 3 bytes. Let's see if they are placed adjacent to one another, to see if they together form a giant string.

Finding the right password

According to memory layout of the function main, the very first variable (local_68) with a hexadecimal value is placed at the address of EBP minus the offset of 0x68, and the variable after this (local_60) gets placed right after the variable local_68, which basically confirms that they together form a string when the variable local_68 is referenced using its pointer. From local_68 to local_48 holds a string the size of 40 bytes total, and the very last variable in the screenshot above, which is local_40, holds a string the size of 11 bytes. So when you add 11 to 40, it results in total 51 bytes. So is the password a string of total 51 bytes? No, it is actually 51 bytes minus 1 byte, because a string in C should always end with a NULL byte to mark the end of the string, so the very last byte is likely to be a NULL byte, which doesn't count as part of a string in C. So, the password is likely to be of the size of 50 bytes. So what's the password? Let's actually run the binary in a VM and see what the password is.

• Here is a screenshot of running the binary. It basically accepts a password from a user, and compare it to the password that it holds. In this instance, inputting the random string fails and exits the process. Let's check out the password that our password is being compared to using the GNU Debugger.

• So, in order to analyze the running binary, we have to first set the breakpoint, at which we can see the string itself. A breakpoint is essentially the point at which we can completely stop the program from executing further. At line 34 is where the program stops to accept a password from a user using the function called scanf. And the very second argument passed to the function scanf is a variable local_a8, a pointer to an array of type char where our input is going to be stored. In line 51, the binary compares the alleged password local_68 with our input local_a8, using the function called memcmp. So we can set the breakpoint at where memcmp is called, and check out what the alleged password is. Let's go ahead and try.

• We set the breakpoint at where the function memcmp is called, by typing b memcmp. And we run the binary, by typing in run.

• The process is created, and it asks for the password again, just like the first time we ran the binary. I type in asdfasdfasdfasdfasdf and press ENTER.

• The screenshot above is a screen upon invoking the function memcmp, and as you can see, we can observe what it does, by watching the contents of its registers, stacks, flags, etc.

• In the code section shows the exact instruction that the code is currently running. The highlighted line in green text is the next instruction that the process is planning on running when you decide to proceed, and its angle brackets(<>) has the word memcmp+0 inside to show the function that it is about to run, so we are basically about to run the function memcmp. Let's move on to executing next instructions, by typing in si and next until we stumble upon something interesting.

• After executing a number of instructions, we stumble upon some weird strings on stack memory. Those strings consist of 50 characters each, and we are currently in the code where we are comparing two strings with one another. That means, one of them has to be the password that we have to match! One thing to note is that the string we provided (asdfasdfasdfasdfasdf) at the start of the process is no longer to be seen, and transformed into one of those two strings. So which one is the right password, and which one is our input? Let's go back to Ghidra and find out.

• Hovering a cursor over the hexadecimal value of local_68, the very start of the right password to match our input against, we see the information above in which we can see how they are converted to either a decimal or a series of characters. Right next to char[], we see the following string jhpnnkpm. The one thing we learned from solving the last challenge is that the string is stored in little-endian (reversed), so if we reverse the string, it becomes mpknnphj.

• So the string that starts with mpknnphj is the password, and here is that very string! So the one that starts in avgl is the string we have provided (asdfasdfasdfasdfasdf), and it has turned into something completely new. That means there must be a section of code that converts our string into something brand new, and our job is to find the string that, after conversion, turns into the exact string that starts with mpknnphj! Let's go back to Ghidra and see how its encryption works.

Understanding how its encryption works

Here is an excerpt of code relevant for the encryption of an input we provide to the binary. The code is really hard to read in general, due to a lot of variables whose names are prefixed with local. So, we will have to sort of modify the code, by changing the names of those variables into something readable, and understand how it works.

Let's go over the mechanism by which its encryption works, by going through the code above.

• In line 7, the process determines the length of the variable right_password (local_68), the address of the right password, and subsequently, in line 8, assigns its length to a variable right_password_length (local_14). In line 15, the process iterates over the for-loop exactly 50 times by comparing its counter to right_password_length.
• From line 14 to line 15, we see the nested for-loops, and line 14 shows that it exactly repeats the process 3 times. With every iteration in a for-loop in line 14, the for-loop at line 15 goes over every character of the password provided by a user. Since the counter involved in it goes from 0 to 49 (50 times), it goes over and transform each character of our input into something new, by the method with which it encrypts a string.
• So, the conclusion is that it repeats the encryption process the total three times, with every iteration transforming each letter of our input.

Time to delve into how it transforms each character of our input! The second screenshot above from this shows a list of variables used in the encryption process. They are basically nothing but a number used to modify each character; however, the screenshot very above this is where all the magic happen.

• In line 16, it executes the line in sequential order. The variable local_18 holds the constant value of 0x55 (85).
  • (password_index % 0xff >> 1 & local_18) // Let's call this "Operand 1" - 1. Two operands on modulus --> 2. Shift bits to right once --> 3. Do AND bitwise operation
  • (password_index % 0xff & local_18) // "Operand 2" - 1. Two operands on modulus --> 2. Do AND bitwise operation
  • local_28 = (Operand 1) + (Operand 2) - Add both and assign the result to the variable local_28.
• In line 18, it utilizes the variable local_28 from line 16 for further computation. The variable local_1c holds the hexadecimal value of 0x33 (51).
  • ((int)local_28 >> 2 & local_1c) // "Operand 1" - 1. Shift the bits of local_28 to right twice --> 2. Do AND bitwise operation
  • (local_1c & local_28) // Operand 2 - 1. Do AND bitwise operation
  • local_2c = (Operand 1) + (Operand 2) - The result of addition of Operand 1 and Operand 2 gets assigned to the variable local_2c, which is going to get utilized in the very subsequent line of code.

For both the line 16 and 18, what I noticed is that they don't involve the input of a user at all. All they require is an index at which a character is located, so since they will always retain the constant values depending on a very index, and are definitely used for encrypting each character of our input, let's make a note of this and move on to the next line, which is line 20.

• In line 20, it utilizes the variable local_2c from line 18 for further computation. The variable local_20 holds the hexadecimal value of 0xf (15).
  • ((int)local_2c >> 4 & local_20) - 1. Shift the bits of local_2c to right four times --> 2. Do AND bitwise operation with the value 0xf
  • ((int)our_input[password_index] - (int)character_a) - 1. Subtract the decimal value of a character in ASCII with the decimal value of the character "a", which is 97
  • (local_20 & local_2c) - 1. Do AND bitwise operation
  • iVar1 = (Operand 1) + (Operand 2) + (Operand 3) - The result of the addition of Operand 1, Operand 2, and Operand 3 gets assigned to the variable iVar1, which is going to get utilized in the very subsequent line of code.

The last line is where a newly encrypted character gets placed in our input rightfully at its index. Let's briefly check out how it works, and see what we should do to somehow reverse the process of encryption.

• In line 23, it utilizes the variable iVar1 from line 18 for further computation.

  • our_input[password_index] = character_a + (char)iVar1 + (char) (iVar1 / 0x1a) * -0x1a;
  • 1. Divide the value of iVar1 with 0x1a, which is 26 in decimal
  • 2. Multiply it with -0x1a (-26)
  • 3. Add the result of the step 2 with the value of iVar1
  • 4. Lastly, add the result of the step 3 with the decimal value of the character "a" (97)

• Summary

  • From line 16 to 18, they don't involve the input of a user at all, so the only value that holds sway over the values of the variables local_28 and local_2c is the counter (which runs from 0 to 49, since the right password is of 50 characters) in the for-loop in line 15. The variable local_28 is used in calculating the value of local_2c.
  • Line 20 is where it involves the input of a user for calculating the value of the variable iVar1. In the very next line, iVar1 is then used to transform a character of an input of a user, and a transformed character replaces an original character in the input of a user.

So, that's pretty much it when it comes to encryption. At this point, since we are equipped with adequate information on how the program works basically, it's time to actually figure out the actual input, which will be transformed to the string mpknnphjngbhgzydttvkahppevhkmpwgdzxsykkokriepfnrdm after three rounds of encryption. Let's say if we were to reverse the following encryption method that consists of four steps above, the logical way to approach solving this would be to completely go backwards from the point at which we end up with the right password.

2. Reversing the encryption process

Since we learned that three rounds of encryption using the method above wind up with the following mpknnphjngbhgzydttvkahppevhkmpwgdzxsykkokriepfnrdm, we are going to iterate over the string from its very last character to its first and eventually work our way towards the answer we need.

So, beginning with the letter m at the index of 49 in the string above, let's start from line 23.

• m = character_a + (char)iVar1 + (char) (iVar1 / 0x1a) * -0x1a;
  • The only value we are missing right now is iVar1. There may be more than one number that can take place of iVar1, so we kind of have to guess to find out what iVar1 is, by placing a random value from 0 to 50 to see if we end up with the letter m.
• iVar1 = ((int)local_2c >> 4 & local_20) + ((int)our_input[password_index] - (int)character_a) + (local_20 & local_2c)
  • Once we learn what iVar1 is, we move on to line 20, where the only value missing is a character, our_input[password_index]. We already know in advance what the values of both local_2c and local_20 are going to be, with the realization that the only factor that controls the values of local_28 and local_2c in line 16 and 18 is an index of our input at which a character is located. Once we guess a right character, with which we end up with the same value of iVar1, we replace a letter in the string with a very letter we find.

Let's create a script for finding the right input!

We are going to go over the code in the screenshot right above this paragraph, to see what's going on.

• Remember that the only factor that controls the values of local_28 and local_2c in line 16 and 18 is an index of a letter, at which a character is located in our input? The first for-loop in the screenshot basically calculates the values of local_28 and local_2c using an index, saves them in the list wowow, and puts the list wowow in the list whose name is keys. Since the answer consists of 50 letters, the list keys will have the total 50 items. Those values will be used in the helper function called find_previous_letter, to find a previous letter before encryption.
• The second for-loop is a rendition of the reversed process of the encryption process we saw above, and nested, for the fact that the encryption is done for three rounds. In its nested loop, it goes over from an index 49 to 0 (50 times) and uses one helper function called find_iVar to guess a right number that can take place of iVar1, and uses a number to find a previous letter to reverse encryption. The function find_iVar actually returns an integer value, which subsequently gets converted to a ASCII letter associated with the very value, so its name isn't really accurate.

Let's go over two helper functions that are instrumental in finding the right answer.

• the function find_iVar does the job of finding the right candidates for a value that may be used as that of iVar1. Once it identifies a potential value of iVar1, it passes a value to the function find_previous_letter.
• The function find_previous_letter accepts the potential value of iVar1 and an index, at which a character is located in the input, as arguments. It is the function for finding the right character (our_input[password_index]) in the line iVar1 = ((int)local_2c >> 4 & local_20) + ((int)our_input[password_index] - (int)character_a) + (local_20 & local_2c). Occasionally, the function find_iVar may find and pass a wrong candidate to the function find_previous_letter, which results in not matching a single character from 'a' to 'z' - an early exit. To avoid the script from exiting early with an exception, I use the "try...except" block that skips the wrong candidate for iVar1, and the script continues finding a next candidate for the value of iVar1.

Running the script outputs the following answer:

mmhhkjbakavyaqprqnpbuygdymyyddkratrjsbbceizsgtbcxd is what the script says an answer is basically. Let's see if it spits out the right flag with the submission of the answer.

Yay! We got the flag! I submit the very flag and get 300 points!

Overall, it was a pretty interesting challenge to solve, albeit it was kind of challenging compared to the previous one I did. In the near future, I will complete more challenges and post their walkthroughs from time to time. Thank you for reading.