Reverse Engineering Challenge - Zed's Frequency

Reverse Engineering Challenge - Zed's Frequency

Introduction

Hey you're back already!? You must be looking for another reverse engineering challenge walkthrough! Well you came to the right place. Today we are going to analyze Zed's Frequency. The description for this challenge says we have to feed the program a key file. It also says that the name of the challenge should give us a hint for the solution. So, the key file should have something to do with frequency of something. If you want you can check out my video walkthrough on YouTube. However, if you are tired of hearing my voice or think I talk too much, read on! This challenge was actually made by the same guy who made Zed's Crackme! As if that weren't obvious. Let's see if he has any crazy tricks up his sleeve! If you prefer you can take a look at the video walkthrough below:

Zed Frequency Video Walkthrough

Optional Materials to Follow Along

If you want to follow along feel free to download the VM I provide. You can find instructions on importing the VM here. If you don't want to use my VM that's fine, my feelings won't be shattered. But you will at least need the binary. You can download the binary here. The binary comes in a password protected file. The password is crackmes.one.

You'll also need a disassembler. I recommend IDA or Ghidra. With all of that out of the way, let's get reversing!

Initial Triage

As always we start by running file on the binary.

File output
File output

Alright so we are dealing with a 64-bit binary that has not been stripped! Let's take a look at those symbols!

Output of nm
Output of nm

We don't see any user defined functions aside from main so it seems we will only need to analyze one function which makes our lives a little easier. Let's go ahead and take a look at the strings before we open this up in IDA.

Output of strings
Output of strings

So, it looks like this binary will generate some key based on the file we provide. We see a series of numbers: 01234567890123456789012345 followed by a success and failure message. Let's try and load the numbers into a file and run the program with that file.

Output of program with bad key file
Output of program with bad key file

Alright that didn't go as planned, but does it ever? Let's now open this bad boy up in IDA!

Static Analysis with IDA

Main Function Prolog and other stuff
Main Function Prolog and other stuff

Everything here looks pretty standard. We see the binary stores argc in var_B4 and argv in var_C0. The instruction at address 0x000872 looks a little strange but I believe we talked about this before. This instruction is grabbing a stack canary and stores it in RAX. The next instruction then stores that in var_8. At the end of this main function we should see this variable in a comparison that will check whether this value has changed. Essentially, it's checking if we performed a buffer overflow or not. Then it checks whether we supplied an argument or not and then prints the usage message if we don't. Ok so nothing entirely interesting here. Let's rename the variables and move on to the next loc_8B2.

Analyzing loc_8B2
Analyzing loc_8B2

This section here is also not entirely interesting. All this is going to do is pass argv[1] as an argument to fopen. The file is being opened with rt mode which is "read text." I'm going to rename stream to fp as I did in a previous challenge. I just happen to like the name fp. Finally, we see var_B0 is set to 0 before an unconditional jump. Let's go ahead and rename var_B0 to i and being analyzing loc_8FC.

Analyzing loc_8FC
Analyzing loc_8FC

This section is also pretty simple. We see we are looping over this var_A0 variable, setting each index to 0. Let's go ahead and rename this to array_all_zero. Let's go ahead and write some C code shall we!?

if(argc <=1)
{
	printf("Usage: %s <filename>", argv[0]);
    exit(1);
}
i = 0;
FILE* fp
fp = fopen(argv[1], "rt");
while(i <= 0x19)
{
	array_all_zero[i] = 0;
    i++;
}

After this block of code finishes we move on to loc_905 so let's take a look at that section which turns out to be where the meat and potatoes begin! Let's eat! First, the meat!

The Meat
The Meat

It starts off by calling fgetc on our file pointer, fp. The result is then stored in i and compared to -1 (0xFFFFFFFF in hexadecimal) which means we've reached the end of the file. If it is -1 we jump to loc_98C otherwise we continue to perform another series of comparisons. First it compares i to 0x60 which IDA tells us is the backtick (`) character. If i is greater than 0x60, it compares i to 0x7A which IDA tells us is the (z) character. The next part is a little confusing. I'm going to write the corresponding C code and then back track and explain how I came to the conclusion.

while(1)
{
	if(fgetc(fp) == -1)
    	break;
    if((i <= 0x60) || (i > 0x7A))
    	// go to loc_956
    else
    	array_all_zero[i - 0x61] += 1;
}

I created an or statement because we can reach loc_956 two different ways. Only one has to be true in order for us to reach that block of code. I'll analyze that section in a bit but first there's the array_all_zero[i - 0x61] += i. Where the heck did that come from? Let's look at this instruction-by-instruction. I'll update the registers as we go along. Let's pick an i that will allow us to reach this chunk of code. That is i must be greater than 0x60 and less than or equal to 0x7A. Well setting i to 0x61 will do the trick so let's do that. The instruction at address 0x0000935 stores i in the EAX register. The very next instruction will subtract 0x61 from EAX. So, at this point, EAX holds i - 0x61. The MOVSXD RDX, EAX instruction will store EAX in RDX. MOVSXD stands for move with sign extension. This is essentially the proper way to move 32-bit registers to 64-bit registers and ensuring the sign is preserved. So, now, RDX also holds i - 0x61. The next instruction mov edx, [rbp+rdx*4+array_all_zero] will store array_all_zero[i - 0x61] in the EDX register. Then we see that 1 is added to EDX so the value EDX holds is now 1. Remember we initialized every index with zeros. Finally, we see another MOV instruction, mov [rbp+rax*4+array_all_zero], edx. If you recall, RAX holds i - 0x61. So, this effectively is a convoluted way of performing array_all_zero[i - 0x61] += i as I have in the C code above. Hopefully that all makes sense and you're still here with me! Now, let's take a look at loc_956.

Analyzing loc_956
Analyzing loc_956

This looks very similar to the previous section we just analyzed. First, i is compared to 0x40 and if it's less than or equal to 0x40 it goes back to the beginning of the loop. The same thing happens for the next comparison to 0x5A. Because of this behavior, this is going to be and if((condition 1) && (condition 2)) type of situation because in order to reach the instruction at address 0x0000968 both of these conditions have to fail essentially. I know it sounds strange but if we flip the conditions to be if ((i > 0x40) && i <= 0x5A)) it makes a little more sense. So, again let's assume we have an i that meets this criteria, say 0x41, let's see what happens. Well actually the same thing as we discussed earlier happens. The only difference here is instead of subtracting 0x61, the program subtracts 0x41. So, we can update our C code from earlier to reflect what we just learned.

while(1)
{
	if(fgetc(fp) == -1)
    	break;
    if((i <= 0x60) || (i > 0x7A))
    {
    	if((i > 0x40) && (i <= 0x5A))
        {
        	array_all_zero[i - 0x41] += 1;
        }
    }
    else
    	array_all_zero[i - 0x61] += i;
}

You might be asking why I created an infinite loop while(1) instead of while (fgetc(fp) != -1). Actually, in both cases, the result is the same. Both notations yield the same end result, we break out of the loop when we reach the end of the file. Mama always said you gotta eat your vegetables! So, let's eat the potatoes!

The Potatoes
The Potatoes

Right away we see a familiar string: "the generated key is: ". After this string is printed, var_AC is set to 0 followed by an unconditional jump. Since we already used i let's rename var_AC to j. We see j is compared to 0x19 then jumps to loc_9AA. This looks pretty simple, it just prints out array_all_zero[j]. After that we get to a slightly confusing section again. Just as I did earlier, I'll write the C code and provide an explanation.

printf("the generatted key is: ");
j = 0;
while(j <= 0x19)
{
	printf("%d", array_all_zero[j]);
    new_string[j] = array_all_zero[j] + 0x30;
    j++
}

Alright let's step through this again instruction-by-instruction. Also, I'm going to rename s1 to new_string. In fact, to make things easier to follow, I'll show you the updated disassembly with the proper variable names.

The Potatoes with updated variable names
The Potatoes with updated variable names

Alright so, after it prints array_all_zero[j], it stores j in the EAX register. Then, it grabs array_all_zero[j] and stores that in EAX. Next, we see it adds 0x30 to EAX to EAX holds array_all_zero[j] + 0x30. This value is then stored in EDX. Then, we see that new_string is indexed with j and dl is stored in this new_string[j] variable. So, this essentially equates to new_string[j] = array_all_zero[j] + 0x30. Again I hope that makes sense and you're still here with me!

So, it does this for 0x19 iterations before exiting the loop. At address 0x0009FC we var_16 is set to 0. Then, put char is called with 0xA as it's sole parameter. I believe this is a way of writing a new line to the terminal. Next, the new_string is compared to this s2 string which holds "01234567890123456789012345" a string we are familiar with at this point. If they are equal then we get the "you succeed" message otherwise we fail! Ok, so we know this new_string needs to have "01234567890123456789012345." We also know that new_string is contructed based on our input file. Let me combine all of the C code we have so far and let's see if you can figure out what this guy wants us to do:

if(argc <=1)
{
	printf("Usage: %s <filename>", argv[0]);
    exit(1);
}
i = 0;
FILE* fp
fp = fopen(argv[1], "rt");
while(i <= 0x19)
{
	array_all_zero[i] = 0;
    i++;
}

while(1)
{
	if(fgetc(fp) == -1)
    	break;
    if((i <= 0x60) || (i > 0x7A))
    	if ((i > 0x40) && (i <= 0x5A))
        	array_all_zero[i - 0x41] += 1;
    else
    	array_all_zero[i - 0x61] += 1;
}

printf("the generatted key is: ");
j = 0;
while(j <= 0x19)
{
	printf("%d", array_all_zero[j]);
    new_string[j] = array_all_zero[j] + 0x30;
    j++
}

if (strcmp(new_string, s2) == 0)
{
	printf("you succeed!!");
}
else
	printf("you failed!!");

Can you tell what's going on here? Allow me to explain. The part where our file is being read is actually calculating the frequency of the letters in our input file. Let me use a practical example. Let's say we input a file with 3 A's and 1 B. These can be capital or lowercase it doesn't matter. To prove it to you, let's say our input file is: AaAB. Recall, the ASCII value for "A" is 0x41, for "a" is 0x61, and "B" is 0x42. So, the first character is "A." When it reaches the while loop, we compare i to 0x60. Since 0x41 is less than 0x60 we move on to the next comparison. Is 0x41 greater than 0x40 and less than or equal to 0x5A? Yes it is. So, we take array_all_zero[0x41 - 0x41] and add 1 to it. At this point array_all_zero[0] now holds 1. Similarly, when we process the next character we will fall into the else statement, so 1 is added to array_all_zero[0x61 - 0x61]. So, now array_all_zero[0] holds 2. Finally, "B" will set array_all_zero[1] to 1. Then, we get to where it stores our array_all_zero values into new_string but it adds 0x30. It does this because it compares the number to a string. So, this is essentially turning the integers into their string representation. Let's run the program with this file to confirm what we think we know.

Confirming our theory
Confirming our theory

That's it! We got it! So, if we want to pass this challenge, we need a file that has the correct frequencies for each letter! I've listed the correct frequencies below.

Correct Frequencies for the key file
Correct Frequencies for the key file

Now, let's create a file with these frequencies and run the program again!

Success!
Success!

And we got it! Not too crazy right!?

Conclusion

Alright we made it through another challenge! Thank you for reading! I truly hoped you enjoyed reading and you learned something new! If you have any questions feel free to hit me on Twitter, Instagram, or Discord: Jaybailey216#2655. If you have a challenge you would like me to try, let me know and I'll give it a shot!

Support your boy Jaybailey216

I truly hope you enjoyed this reading this blog and/or watching the YouTube video! My goal is to always provide quality content. If you want to support me even further, consider becoming a Patron! This is the best way to support me! Regardless if you decide to join or not, I'll see you all next time!

Peace out! ✌

Show Comments