F-Secure Khallenge - Level 3

Alright. The third level of the RE challenge was a 6.50 KB large unpacked console EXE file. Start it and it asks for a password. The goal was to find a valid password. Even though the file is already very small, most of the code in there is actually part of the standard C library. Only four functions are important if you want to find the password.

Most of the actual calculations are performed in the function at address 0x4013D6. This function takes the password the user entered and checks whether the password is correct or not. Depending on the return value of this function, the main function decides whether to print "You did it!" or "Nope.". Click here to get a graph overview of the function.

The "You did it!" message is displayed in case the return value of function 0x4013D6 is not zero. There are two conditions that need to be met inside the function to return this value. Between the offsets 0x4015BC and 0x4015E1 the file checks whether a byte in memory has a certain value and whether the length of the password is less than or equal to 0x3E.

The byte value check looks like this:

.text:004015BC                 mov     edx, ds:state
.text:004015C2                 add     edx, offset TransitionTable
.text:004015C8                 mov     al, 0FFh
.text:004015CA                 and     al, [edx]
.text:004015CC                 mov     [ebp+Multiple32Please], al
.text:004015CF                 movsx   eax, [ebp+Multiple32Please]
.text:004015D3                 shr     eax, 5
.text:004015D6                 and     eax, 1
.text:004015D9                 test    al, al
.text:004015DB                 jz      short BadValue

A byte is read from a table. Afterwards comes a check that tests whether the 6th bit of the byte is set. If it's not set, we get a bad return value.

The first thing I did was to find out which table values are actually values that pass the password check. There are only four of those good values in the table: 0x61 (at position 0x6A), 0x21 (at position 0xA9), 0xA1 (at position 0x123) and 0x62 (at position 0x13C).

The code above uses the value in ds:state as an index into the table. Apparently ds:state needs to be 0x6A, 0xA9, 0x123 or 0x13C at this point. So how do we get the correct value in there?

There are only three locations in the code that modify ds:state. The first location is in the function 0x401290. This function runs at the beginning of the password checking function. It doesn't take parameters and it doesn't read from memory. That means the function does the same thing every time it runs. The only thing the function does is to put 0x5B into ds:state in some fancy way. The other two locations that modify ds:state are in function 0x40138A. This function subtracts a value from or adds a value to ds:state. This value and whether it's added or subtracted depend on the two parameters of the function.

This state-modifying function is called from four locations in the main password checking function. The two parameters it takes are all four possible combinations of 0 and 1. Whether the function is called or not depends on two conditions. The first condition is that the currently processed character from the password is either '2', '4', '6' or '8'. Only these characters modify the state. In fact, as it turned out, only these characters are of any importance. The password contains no other characters. The second condition is a bit trickier.

This is the moment the fourth and last function (0x4012CC) comes into play. This function takes two parameters. One constant that's unique for each of the four valid characters. This parameter basically identifies the current character inside the function. The second value is the table value of the current state, aka table[state]. With the help of these two parameters the function calculates a boolean flag. If it's true, the state can be altered. If it's false, the state will remain the same.

The function uses four simple rules to determine the result. If the current letter is '2' the table[state] value must be non-zero for (table[state] >> 3) & 1, if the letter is '4' the expression is (table[state] >> 2) & 1, if it's '6' the expression is (table[state] >> 1) & 1 and if it's '8' the expression is just table[state] & 1.

Assuming that everything goes well and the function returns a non-zero value, the function at 0x40138A can now subtract from or add to the state. It turns out that the character '2' adds 0x1D to the state, '4' decrements the state, '6' increments it, and '8' subtracts 0x1D from it.

OK, so what do we have so far? Only characters '2', '4', '6', and '8' are relevant for the password. The password must be less than or equal to 0x3E letters long. The initial value of ds:state is 0x5B, valid end values of ds:state are 0x6A, 0xA9, 0x123 or 0x13C. It's now necessary to find a way from state 0x5B to any of the four valid end values bearing in mind that only characters '2', '4', '6', and '8' modify the state and they modify it only if the conditions in function 0x4012CC are true.

So, how does it all work? Assume you're in state 0x5B. What are your options here? First you need to read the byte value at table offset 0x5B. The value is 0xDF. (0xDF >> 3) & 1 is 1. That means it's possible to go from state 0x5B to state 0x5B + 0x1D = 0x78 by starting the password with the letter '2'. (0xDF >> 2) & 1 is also possible. Apparently the letter '4' transfers state from 0x5B to 0x5B - 1 = 0x5A too. (0xDF >> 1) & 1 is 1 too. Ergo the letter '6' modifies state 0x5B to 0x5B + 1 = 0x5C. Last but not least 0xDF & 1 is 1 too. State 0x5B - 0x1D = 0x3E can be reached too. All four potentially state-modifying letters modify ds:state. That means the password could start with '2', '4', '6', or '8'. Now you need to recursively do this for all states until you reach one of the four valid end states.

I solved this by creating a directed graph from the table. There's one vertice for each table index and there are edges from each vertice to all vertices that can be reached from there. The edges are constructed according to the conditions inside function 0x4012CC. I stored it all in an adjacency matrix.

The last step is to find a path from the start state (0x5B) to one of the four potential end states (0x6A, 0xA9, 0x123 and 0x13C). It turns out that three of those four vertices are unreachable from vertice 0x5B. Only vertice 0x123 can be reached from there. Finding the right password is equivalent to finding a path from 0x5B to 0x123. Remember the second password condition though. The length of the password must be less than or equal to 0x3E characters. A shortest path algorithm on the directed graph gives the answer. I've chosen nothing fancy but the standard algorithm. The shortest path between two vertices x and y is the shortest path between all vertices that can be reached in one step from x and y: shortest_path(x, y) = shortest_path[all neighbours a of x](a, y).

The shortest possible password is in fact 0x3E characters long. There are a few more paths from the start state to the end state by the way. Unfortunately all of them take more than 0x3E steps.

I've actually taken this as an excuse to try out the GraphViz library for the first time. If you want to see the state transition diagram of the graph click here but I have to warn you that the PNG is gigantic. It's 426 KB and 3245 x 10041 pixels large.

Click here to get some C++ code that creates the graph from the table, finds the shortest path, and prints the correct password.

OK. Once the correct password is entered, the program decrypts the mail address stored in the EXE file and tells you to send an email to it. That's it. Congratulations to the winners of the contest!