in ctf reverseengineering

CSAW 2017 Finals -Write Up [rusty_road]

This year was UMBC's first year qualifying for CSAW finals and it was a blast. Thanks to the organizers it was a great event! Shout-out to my teammates: Chris,Seamus, and Zack.

Rusty Road [Reverse Engineering]

Challenge Description:

Traverse these roads, win and obtain the flag

Material:

x86_64 Rust Binary

Solution:

Seamus and I both worked on this problem. After reading the description we knew that this challenge would have to do with some type of maze like game. Running the binary we are greeted with this message:

start

After opening it in IDA we saw that the only valid moves were "U","D","L", and "R". The fail message you receive is:

fail

We then continued to look at it in IDA to determine the game logic. We wanted to see if we could reverse engineer the board generation algorithm to determine how it is created and write a solver for it. This was our first time reverse engineering a rust binary and after a a few minutes we knew we did not enjoy it :). It is very similar to reversing a C++ binary in the sense that name mangling and many calls to library functions make it confusing fast. Here is an example of what the disassembly looks like:

example

This binary was not stripped so we could quickly narrow down the interesting functions:

interestingfunctions

Looking at the board_algo function we saw that it was doing stuff with vectors and putting them in a hash map. We attempted to try and view these vectors using gdb and printing them out. But printing the data in these vectors did not make much sense to us. We did not see any patterns to these values, for example "1" = wall to the right..etc. After some time and laziness, we wanted to see if we could solve this without figuring out what the board looks like.

We saw that in the traverse function it was going through our input, ex "RRLUD" and it was keeping track of our x and y and keeping track of something called path_sum.

One of the checks is to see if the player is at the a certain coordinate at the end of all of the moves. This can be seen in the following two screenshots, in the disassembly you can see that it calls a function called PartialEq with our coordinates after all moves and a variable called ref_e

coor

Using gdb we can print out what is in ref_e:

coor2

So we see that at the end of all moves we should be at [9,9]. The first argument is our coordinates after all of our moves.
To get out of the traverse function we must satisfy these requirements:

  1. Only have valid moves in input
  2. At the end of all moves be at [9,9]

Path_sum is not checked in the traverse function, it is returned after passing the above checks.

path_sum

traversereturn

We then see that the returned path_sum is checked against some magic number named smallest. Smallest = 0x622C

With some trial and error we noticed that path_sum is the sum of each move made where each move has a different value. But we noticed two things that made our solve possible:

  1. The first move, if done consecutively, does not affect the coordinates. For example "DDDDDDDU" should theoretically be at position [0,-5] but it is actually at [0,1].
  2. The moves "D" and "R" always add 2 to path_sum. The other moves change in value based on the location in the input it is at. For example "U" or "L" in index [6] might add 50 to path_sum but at index [9] it would add 80 to it.

Because of those two things we were able to create a solution that satisfies both, being at [9,9] after all moves and have a path_sum that equals: 0x622C .

After more trial and error we came up with this input:

DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDUDUUUUUUUUURRRRRRRRR

We created enough "UD" moves (Up and down cancel each other out for position) so that our path_sum with "UUUUUUUUURRRRRRRRR"(get to [9,9]) at the end of it would be close to 0x622C. Calculated how far that path_sum was from 0x622C and divided that by 2 to get how many "D"s we would need at the beginning to equal that. The reason we could not just append "D"s to the front of UUUUUUUUURRRRRRRRR was because there was a check for length of input. It would take to many "D"s to get close to 0x622C so we had to use the "UD" moves to get path_sum higher while keeping our input under a certain length.

win

We are then greeted with the win message. When we run the same input against the server we get our flag.

After talking to the challenge writer the intended solution was to write a recursive solver after reversing how the board is made. But sometimes laziness prevails :).