Keygenme

TL; DR

The flag is the licence key and it is stored in acStack56. The key is found to be of the format picoCTF{br1ng_y0ur_0wn_k3y_********}. The * represents those characters in the key that are always randomised for different participants. Two hash values are generated by hashing the strings picoCTF{br1ng_y0ur_0wn_k3y_ and }. The hashing function used is MD5. Finally, certain characters are selected from the previously created hash values to form the last 8 characters of the key.

Solve

FUN_00101209

This function’s duty is to assess whether the licence key provided is authentic or not. The licence key is the CTF flag itself. The binary merely confirms this for you. You gain nothing else if the binary says that your key is valid aside from just that confirmation. The correct key is stored in acStack56. This entire function essentially revolves around constructing this key. In order to know the correct key’s contents, we will need to analyse specific segments of the binary.

Stack Allocation

Ghidra has a useful naming convention for its decompiled local variables. Firstly, their local scope is indicated by being named local. Secondly, their address on the stack is indicated by the number that is present at the end of the variable’s name. Thirdly, there might be some variables whose data types Ghidra cannot reasonably ascertain. Even if it may not be aware of the exact data type of a variable, it always knows its size and this is revealed by the number that is post-fixed after the word undefined. For example: undefined8 local_90; Here, local_90 is a local variable declared on the stack at address 0x90 and whose size is 8 bytes.

undefined8 local_98;
undefined8 local_90;
undefined8 local_88;
undefined4 local_80;

// ...
local_98 = 0x7b4654436f636970;
local_90 = 0x30795f676e317262;
local_88 = 0x6b5f6e77305f7275;
local_80 = 0x5f7933;
local_ba = 0x7d;

These variables actually store the hexadecimal representations of the strings “{FTCocip“, “0y_gn1rb”, “k_nw0_ru”, “\0_y3” and “}” respectively. It is important to know how these variables are allocated on the stack frame. This will be covered later.

Hashing

  sVar1 = strlen((char *)&local_98);
  MD5((uchar *)&local_98,sVar1,local_b8);
  sVar1 = strlen((char *)&local_ba);
  MD5((uchar *)&local_ba,sVar1,local_a8);

sVar1 stores the length of the string that is about to be hashed. It is obvious that the hashing algorithm used is MD5. MD5() accepts three arguments:

1. char* - the string to be hashed
2. int - the length of the string to be hashed
3. char* - the pointer that will reference the new message digest

The extent of the string that we want to hash is determined by sVar1. We determine this size using strlen(). Knowing how strlen() works can prove quite useful. In short, it accepts a char pointer and continues incrementing it until it encounters \0 which is the character for null. In our example, we pass a pointer to local_98 and forcibly cast it as a char pointer.This will cause the function to commence counting the string’s length from &local_98 in 1 byte steps (this is because a char is 1 byte). As the pointer is incremented, it will move down the stack (this is because the stack grows downwards).

Stack Contents

Unallocated memory spaces will usually be \0 or 0. However, this is not always necessarily true, especially in cases where memory locations have been released from a variable.

The table above shows a portion of the stack frame ranging from address 0x98 to 0x7d (note the decreasing index because of the fact that the stack grows downwards with newer additions). Each memory location can store 1 byte (8 bits of data). strlen() will commence from address 0x98 and conclude when it encounters \0 present at address 0x7d. Therefore, the length returned to sVar1 will be 0x98 - 0x7d = 27 characters.

Now, we invoke the external helper method MD5() to hash a string of 27 characters. For this, we pass the address &local*98, the length stored in sVar1 and finally a pointer to the address that will store the resultant message digest. The string being hashed is picoCTF{br1ng_y0ur_0wn_k3y* and the resulting hash value that is generated is 0x438218d572e90162d0981cbbc7d43882.

We repeat this process for the next string that is to be hashed as well.

Just as before, strlen() is once again used to obtain the length of the string to be hashed. We pass the address &local_ba to commence counting the length from that address onwards. Since the very next address has a null character, the length returned to sVar1 will be 0xba - 0xb9 = 1 character.

Once again, MD5() is invoked to hash a string of 1 character. The string being hashed here is }. The hash generated is 0xcbb184dd8e05c9709e5dcaedaa0495cf.

Reallocating the Hash

The newly generated hashes are reallocated to different memory locations using sprintf(). sprintf() essentially works just as the normal printf() but instead writes to a char buffer instead of stdout. The hash value of the first string is transferred to the address of local_78 while the hash value of the second string is transferred to the address of local_58.

local_d0 = 0;
for (local_cc = 0; local_cc < 0x10; local_cc = local_cc + 1) {
sprintf(local_78 + local_d0,"%02x",(ulong)local_b8[local_cc]);
local_d0 = local_d0 + 2;
}
local_d0 = 0;
for (local_c8 = 0; local_c8 < 0x10; local_c8 = local_c8 + 1) {
sprintf(local_58 + local_d0,"%02x",(ulong)local_a8[local_c8]);
local_d0 = local_d0 + 2;
}

The message digest contains bytes that cannot be directly represented as a string. This issue is resolved by the loops above. They use the format specifier %02x to convert each byte into its hexadecimal equivalent. For instance, the letter T will be reformatted into 74. This newly reformatted data is once again split so that it can be stored in two different memory locations. So continuing our example, 74 will be separately stored as individual bytes - with 7 in one memory location and 4 in another.

The tables below should help visualise what has just been explained in the paragraph before. Take the first byte of the message digest at address 0xb8 as an example. This byte is reformatted so that it can now be stored as two halves in two different memory locations. In our example, 43 is split in such a way that 4 is stored in 0x78 and 3 is stored in 0x77. This process is repeated for the remaining 15 characters in the message digest. If you were able to understand this, then it should also make sense why local_d0 is incremented in steps of 2.

Every message digest always comes in 16 bytes. As explained before, these bytes are reformatted into their hexadecimal equivalent (this is because some bytes do not have representable characters). Therefore, if each byte is split into two individual bytes stored in separate memory locations, our previously 16 byte hash will now be expanded and distributed over 32 bytes now.

#include <stdio.h>
int main()
{
	char result[16];
	char digest[16] = "trevisliuchangfe";


	int offset = 0;
	for (int i = 0; i < 0x10; i++) {
		sprintf(result + offset, "%02x", (unsigned long long) digest[i]);
		offset += 2;
	}

	printf("%c\n", result[0]);
	printf("%c\n", result[1]);

	printf("%s\n", result);
}

The program above is what I came up with to try and figure out what the binary was trying to do. It simulates the same behaviour as the two for loops found in the binary. It is advised to use a debugger with breakpoints to observe how the char buffer is affected with each iteration.

Stack Layout

Once the reallocation process has been completed, the call stack would look something like the table below. Note that the first hash value is stored from address 0x78 to 0x59 and that the second hash value is stored from address 0x58 to 0x39.

At this point, we can consider the problem as more or less solved. We can use the table above to look up the values of specific variables that we want to know about. Suppose that,

acStack56[28] = local_5f

By observing the table, we can easily deduce that the value being assigned here is “7” (note that is the char ‘7’; not the integer 7. In other words, we are talking about 0x37).

Constructing the Key

After reallocating the hash values to local_78 and local_58; acStack56 i.e. the correct key is constructed.

for (local_c4 = 0; local_c4 < 0x1b; local_c4 = local_c4 + 1) {
acStack56[local_c4] = *(char *)((long)&local_98 + (long)local_c4);
}
acStack56[27] = local_5e;
acStack56[28] = local_78[0];
acStack56[29] = local_62;
acStack56[30] = local_60;
acStack56[31] = local_60;
acStack56[32] = local_62;
acStack56[33] = local_39;
acStack56[34] = local_6a;
acStack56[35] = (undefined)local_ba;

Despite performing the most important role in the function, the construction is rather simple once the harder parts of the call stack’s layout are clearly understood. The key is constructed by referencing all of the previous values that we have used and encountered, including the hash values.

The first 27 characters of the key form the very same string that we had hashed earlier i.e. “picoCTF{br1ng_y0ur_0wn_k3y_”. In every iteration of the loop, we cast the address of local_98 into a char pointer. This ensures that we read one byte at a time as opposed to eight bytes at a time which is the actual size of the original data type. This pointer is then dereferenced immediately in order to fetch the actual byte stored at the current address being pointed at. This process is repeated for 27 bytes and the resulting string obtained is the same as the first string we had previously hashed.

The remaining 8 characters of the key are usually randomly selected bytes from the hash values. You can simply use this table to find out which position on the stack does each local variable refer to.

The last character is always 0x7d or }. Note that we specifically cast it as undefined for this reason because the size of undefined is 1 byte which is the same as char.

Comparing the Key

This segment is mostly self-explanatory. The binary will firstly assess whether the input key is of the correct length of 36 characters. After this check, it compares every single character of the input key with acStack56. Any discrepancy causes the binary to immediately reject the key (the function rejects the key by returning 0).

The final key is found to be picoCTF{br1ng_y0ur_0wn_k3y_9d74d90d}. Happy reversing!