Monday, August 7. 2006FSecure Khallenge  Level 3
Last weekend FSecure sponsored a Reverse Engineering challenge at Assembly 2006. I was the 12th person to finish it which means no prize for me. Nevertheless it's good enough for a site update. In this update I'm going to give a brief overview of the Level 3 challenge, how it works and how to get the correct password. I'm not going to explain how the first two levels work. They were quite simple.
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 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 statemodifying 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 nonzero 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 nonzero 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 statemodifying 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!Trackbacks
Trackback specific URI for this entry
No Trackbacks
Comments
Display comments as
(Linear  Threaded)
Turns out the graph was representing a 2D labyrinth. Check FSecure weblog for a cool picture.
Yeah, I saw it but forgot to post the link. As Attila Suszter posted on his blog (see below) the choice for '2', '4', '6', and '8' makes a lot of sense as those are just the numpad keys used to navigate through the maze. It's pretty cool.
Excellent description of the solution, just wanted to emphasize one point: the level3 challenge contains a lot of obfuscated code, adding more complexity to the REjob, compared with the level1 & level3 challenges.
Yep, there's some weird code in there. During my analysis I wondered how the author did that. As the program is a C or C++ program I wondered if he used inline assembler or postprocessed the code manually.
The code is pretty simple actually. The checking routine is just the following:
CODE: int check1(int arg0, int arg4) { if (arg4/25==9) return (arg0>>1)&1; if (arg4/6==2) return (arg0)&1; if (arg4/20==3) return (arg0>>3)&1; if (arg4/4==7) return (arg0>>2)&1; }; The "obfuscated" code you see is the optimized divisions And the decryption of the email address uses 64 bit integers, I think.
Right, right. I don't know what Didier Stevens was talking about but I thought he was talking about stuff like the following which is pretty weird.
CODE: mov eax, edx and eax, 0 mov [ebp+var_24], eax Or CODE: mov edx, ds:state
add edx, offset TransitionTable mov al, 0FFh and al, [edx]
Well, that's probably just gcc optimizer sucking
Congratulations to all winners! Here is another sematic draft about challenge.

Calendar
QuicksearchArchivesContact
Links
Top Exitswww.theinterweb.com (499)
en.wikipedia.org (218) www.amazon.com (186) www.slideshare.net (87) www.zynamics.com (70) theinterweb.com (48) www.offensivesecurity.com (36) nostarch.com (35) github.com (28) www.s9y.org (23) Syndicate This BlogBlog AdministrationCategories 