True to its name, Mess was a real mess to reverse engineer. It also serves as good practice for IDA Pro structure and function pointer usage.
The key insight is that many or most calls in the binary occur indirectly, thus rendering IDA Xrefs mostly useless and the calls non-trivial to follow.
The binary builds structures for each size of call (one parameter, two parameters, three parameters, etc.). The structures have the following form:
DWORD Function pointer DWORD First parameter DWORD Second parameter ....
When it comes time to make a call, the binary allocates a structure or uses an existing one, sets the parameter fields, then calls another method which sets up the arguments and calls the function. I spent a lot of time trying to identify all of these structures, their corresponding functions, and the arguments they took. I was able to determine that the binary included some form of a brainfuck interpreter, but after a while I decided it wasn't worth spending the time to know every detail.
I decided to switch to a more dynamic approach. Thankfully, earlier in my reversing, I saw an interesting call:
if(ptrace(PTRACE_TRACEME, 0, 0, 0))
{
//Give the brainfuck interpreter one type of initialization
} else {
//Give the brainfuck interpreter another type of initialization
}
I assumed this was likely setting up a false key if the program was started in gdb. It is interesting to me they constructed the challenge in this way because I think you could still attach to it in gdb after starting it alone without changing the key.
Regardless, in order to be safe, I patched out the branch to always act as if a debugger was not present.
I then moved on to trying to identify the success branch and the failure branch. This was made easy by examining strings. If you enter the correct key, you get a "congratulations" message, but if you enter the incorrect key, you get an "incorrect choice" message.
Working backwards in IDA and forwards in a debugger, it was found that the key is also interpreted as brainfuck. However, if a character in the key is not a valid brainfuck character, it does an interesting computation:
if(current_character ^ something_unknown != 'a')
{
//Fail
}
Instead of trying to reverse and understand what the unknown byte being XORed was, I simply ran it in a debugger with a breakpoint on that instruction. In this manner I was able to figure out what each character of my input string was XORed with and compared to 'a'.
Character by character, I was able to XOR 'a' with the unknown character and get the next character for the input. It was a tedious process, but within a few characters it was obvious I was on the path to get the key:
ar3n't_funct10n_p01nt3rs_fun