PoliCTF 2015 – reversemeplz

Introduction

Hello all, it has been a while since I wrote anything so here’s a writeup from reversing challenge number two of the 2015 PoliCTF!

Although I didn’t manage to play all three days, the CTF felt like it was nicely done and organised. This challenge was worth 150 points, and it had some interesting twists in it!

The Challenge

You were given the following binary:

$ file challenge
challenge: ELF 32-bit LSB  executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, BuildID[sha1]=da884e304160351da7785e93dc168eecafe770ed, stripped

“Dynamically linked, stripped”. Fairly standard, although I really feel more relieved when things are dynamically linked. Static compilation can make deducing the binary’s purpose or behaviour much harder, as one has to analyse and understand what each function does in the binary (as opposed to looking at then names of the imports and then looking each function’s documentation), massively slowing the whole process.

As expected, the challenge accepts a key as its input, and spits out a yes or no message. When we get the yes message, we can submit the flag we found on the website and get the points. We have two valuable pieces of information; we know that the flag is only made of lower-case alphabetical characters, and it has the format flag{__some_secret__}! We have no idea how large the flag is, or if the characters should form any type of message, so brute-forcing the flag as an option is out of the question.

Inspecting the binary

Let’s see what the binary looks like from the inside! Firstly, inspecting the binary’s functions:

Figure 2: Functions defined in the binary.
Figure 1: Functions defined in the binary.

There are not many functions declared, or so it seems from the looks of it! What about the strings in the binary?

Figure 1: Strings defined in the binary.
Figure 2: Strings defined in the binary.

 

Hmmm, in the spirit of keepings things simple let us assume that the first string, The flat is flag{, is part of the final success message. Checking this string’s cross references in the binary, we can see that it is only being called in location in the code, .text:080483C9. This is located in the function starting at 0x08048390. That function looks like this:

Figure 3: Function that calls the password checking function and prints appropriate messages.
Figure 3: Function that calls the password checking function and prints appropriate messages.

The above output shows some of my comments and IDA’s comments as well. Let’s analyse what this function does!

Firstly, we can see that the output messages are being displayed in the same function, immediately after a Jump-if-Zero (jz) instruction. Moreover, JZ is preceded by a test eax, eax instruction and we know (due to the wonder that is known as calling conventions) that eax is where functions store their return value. So which function returned its value in eax? And, more importantly, what will make that function return not-zero?

Continuing backwards with our analysis we can see that the last function called was check_pass (as I helpfully named it after inspecting and analysing it – unknown beforehand!), at location 0x08048801. At this point, by reading the disassembly of Figure 3 we can deduce that the following pseudo-code is being executed:

void get_input_and_check(){
  char[] input;
  gets(input);
  if ( check_pass( &input )){
    char[] msg;
    strcpy(&msg, 'The flag is flag{');
    strcat(&msg , input);
    strcat(&msg, '}');
    puts (&msg);
  }else{
    puts('Wrong input.');
  }
}

 Verifying the verifier

At this point, we’re nearly there! We have figured out how the binary behaves, and now we just need to input the magic word. I tried please, but it didn’t work and so we’ll have to get our hands dirty! The password verification procedure looks like this from a distance:

Figure 4: Verifier from a distance.
Figure 4: Verifier from a distance.

Huh, interesting. It looks like this function is, roughly, composed of two large loops. By inspecting the code, I deduced that the first of the loops is responsible for sanity checking and transforming the input string using a custom version of ROT13 (named here custom_ROT13), while the second part checks if the transformed string passes the password correctness check.

 

If we step into the first loop, we shall see the following:

Figure 5: Password check, part1!
Figure 5: Password check, part1!

The seasoned  reverser will quickly spot an interesting fact! In the functions beginning, we see a mov ecx, 0Fh instruction and, shortly after, a xor esi, esi instruction (in order to zero-out esi) . Furthermore, at the end of the code fragment, the test that will escape the loop will compare the register esi to 0Fh (or decimal 15), while also incrementing esi. This made some alarm bells go off for me as it resembled a length-checking procedure, meaning that our key is likely 15 bytes long (excluding the trailing null byte).

The function behaves in the following way. Our input string is located at [ebx], with esi being an index into this character array. The first check will check if the current character being processed is less than the ordinal value of ASCII ‘a’ and the second check if the value is less than ‘z’, and if either of the two hold then these characters will be replaced with the logical AND of 1 or 2 (for each case respectively) and then sent to custom_ROT13. However, if your character is in the a-z range, then it will just be replaced with its custom_ROT13 equivalent and then stored in the location [ebp+esi – 0x58], a fact that I think will be useful. After all 15 characters had been processed, then we would proceed to the next part of the loop.

Figure 6: Password check, part2!
Figure 6: Password check, part2!

Alright, we are getting close to solving this (or so I thought!)! It is important to remember now that any checks or performed on the string are performed on the transformed version of our password. This part of the code confused me a bit, as the reasoning behind the checks and operations wasn’t immediately obvious. So, here we go!

In this second part of the loop, we see the number 0Fh feature prominently around checks that will terminate the loop, so this must mean that our string is indeed 15 characters long! The first fragment of the second loop takes pairs of two from our transformed input and subtracts the second character from the first. It then proceeds to test this value with a value located at [ebp+eax*4-0x4C] (in this case eax functions like an index into an array and a loop counter). Getting closer! At this stage eax is compared with 0Eh (14), and I imagine that this is happening because we need to treat the last character differently because it will get subtracted by the null byte. At this point I am fairly sure that we know the solution: the transformed input text must, pairwise, satisfy the numerical differences stored in [ebp+eax*4-0x4C].

 custom_ROT13

Some of you may wonder what is custom about this ROT13. Well, after doing some cryptanalysis I found out that the function will be passed any of the following input:

  • custom_ROT13(0) = 0
  • custom_ROT13(1) =94
  • custom_ROT13(2) =24
  • custom_ROT13(a-z) =the ROT13’d value in the space a-z.

I don’t know why 0,1 and 2 were treated differently like this, but there you have it. So, how do we beat that? The code for the function looked horrible so I thought that I’d not read it (I didn’t need to either, as we already know the differences in the numbers we must get).

Rather than manually stepping forward and bypassing the checks of the test, we can script up GDB to do it for us! The script looks like this:

while $eax < 16
    x/w $ebp+(4*$eax)-0x4c
    set $eax=$eax+1
end

Running this script within GDB will produce the following output:

0xffffce20:  -1  
0xffffce24:  17  
0xffffce28:  -11 
0xffffce2c:  3
0xffffce30:  -8  
0xffffce34:  5
0xffffce38:  14  
0xffffce3c:  -3  
0xffffce40:  1
0xffffce44:  6
0xffffce48:  -11 
0xffffce4c:  6
0xffffce50:  -8  
0xffffce54:  -10 
0xffffce58:  0

The way to interpret these differences would be diff = char[i+1] – char[i], or more intuitively that the transformed second character is, in the first example, the previous character from the first transformed character (a difference of -1). Assuming we are correct on the length of our flag (fifteen characters), then we could ignore the last 0 difference as it would probably stand for the terminating null-byte. The other fourteen differences could be the differences between our target characters.

Now, since we are lazy, we must find an efficient way of programming the solution. We could do it manually, but it would take ages. This took some time for me to figure out how to do, and some counselling from SkyBound, but in the end I managed to logically piece it together! Fortunately enough, this is the type of solution that we can brute-force! My idea was that, since we have a sequence of differences of characters, we effectively have a chain that we can use in order to construct the original sequence of characters (as we can go back and forth between them). The results can also be further narrowed down by the fact that our letter can only be alphanumeric and must also be ROT13-able. Putting the following in a Python script gives us:

#!/usr/bin/python

import string
import codecs
import operator 
diffs = [ -1, 17, -11, 3, -8, 5, 14, -3, 1, 6, -11, 6, -8, -10]

def compute_string(letter):
  current_letter = letter
  result = '' + letter
  for i in diffs:
    char = chr(ord(current_letter) + i )
    current_letter = char
    result += char
  return result

for a in string.ascii_lowercase:
  res = compute_string(codecs.encode(a,'rot_13'))
  if reduce(operator.and_ , map(lambda x: x in string.ascii_lowercase,res)):
    try:
      print 'Letter {:s} generates path {:s}, plaintext {:s}'.format(a, res, codecs.encode(res,'rot_13'))
    except:
      pass #going to hell for this

And this resulted in:

$ ./brute.py 
Letter o generates path bargjbgursyntlb, plaintext onetwotheflagyo
Letter p generates path cbshkchvstzoumc, plaintext pofuxpuifgmbhzp

Closing thoughts

The solution was indeed onetwotheflagyo, so my assumptions and analysis were correct 🙂

The custom transformation made this challenge interesting for a number of reasons! Firstly, the password was transformed and compared with its equivalent value. This is how passwords are stored and compared properly, where a system will store an equivalent value of the password (it’s hash) and will compared the hashed value of the user-supplied password with the stored value it has. In proper cryptographic hashing systems there exists an equivalence and irreversible relation between a password and its hash, with the hash effectively providing proof that a user knows the secret without exposing that secret value.

In our case, however, the transformation function had some weaknesses which allowed us to reverse the equivalence relation. Firstly, the fact that the search space was so small (only 15 bytes long with 26 possible characters, a-z) did not make it prohibitively expensive for us to search that whole space. The serious flaw, however, was the fact that the transformation function was a linear function that would operate on two characters at a time and with no regard for the rest of the string. This linearity property is what allowed us to go from the transformation values back to the original string. As an example consider the transformation function defined as:


f(a,b) = b-a = n,  n is an integer.

Having a small search space, we could go through every b and subtract n from it in order to get a. Given that we have a list of n‘s, we only needed to go through all the a-z characters and add those with the corresponding n at each position, and then take the ROT13 version of it. While the approach of comparing an equivalent value to a secret was correct, the whole operation failed due to the bad “crypto”. This was fun 🙂 !

Advertisements
PoliCTF 2015 – reversemeplz

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s