r2con 2017 Crackmes - Spacemission
This was my first year attending r2con, and I can assure you I’m 100% coming back next year! It was lots of fun, I learned a lot in the trainings and the talks were super interesting. But, as a complete noob with radare2 (and reversing in general), one of the things I enjoyed the most were the Crackmes. Well, actually the crackme, because I only managed to solve one, the easiest of them: spacemission. Here I will try to explain how I approached this challenge from beginning to end, of course using radare2 during the whole process!
Hello, chief reverse engineer
After downloading the binary, let’s copy it into a docker container (one never knows) and execute it right away. The following appears on screen:
$ chmod +x spacemission && ./spacemission
Hello, ...?
Hello, chief reverse engineer root of the spaceship rbinsegfaulter?
Can you hear, me?
Oh, these speakers seem to be broken.
No matter, if you hear me, or not, this is probably our last chance to survive!
We got attacked from the evil aliens from the binja-system!
Their attack was surprising for us. They killed almost all of us, none of our engineers survived.
Before they left, they planted bombs in the ground, each of them with enough destructive power to blowup the planet
But there is hope, one of our bomb disposal rovers out there is still instact, and waiting in idle for transmition of instruction.
I know, you are just a reverse engineer, but at least you are an engineer, and the only one in reach, who can help us, now.
If you can hear this message, hurry up and create an instruction file for the rover.
Note, that the battery, of the rover is very low.
Restart this communication program, to transmit the instruction file
Good luck!
Ok, sounds fun! We have to save this poor planet from destruction by disarming the bombs left behind by these evil aliens. But, mmm, how do we do it?
The binary seems to ignore any parameter passed to it on invocation, so it seems that we need to follow the instructions given to us and create an instruction file. But we don’t even know the name of the file, not to say the contents of it, so it’s time to load the binary into radare2 and see what happens!
$ r2 -d spacemision
Process with PID 517 started...
= attach 517 517
bin.baddr 0x00400000
Using 0x400000
asm.bits 64
-- You can mark an offset in visual mode with the cursor and the ',' key. Later press '.' to go back
[0x7f1922718c30]>
Let’s analyze everything since the binary isn’t too large, and then navigate to the main function to see what’s there:
[0x7f1922718c30]> aaa
[x] Analyze all flags starting with sym. and entry0 (aa)
TODO: esil-vm not initialized
[Cannot determine xref search boundariesr references (aar)
[x] Analyze len bytes of instructions for references (aar)
[x] Analyze function calls (aac)
[x] Use -AA or aaaa to perform additional experimental analysis.
[x] Constructing a function name for fcn.* and sym.func.* functions (aan)
ptrace (PT_ATTACH): Operation not permitted
= attach 517 517
[0x7f1922718c30]> s main
[0x00400ba0]> pd 20
/ (fcn) main 3355
| main ();
| ; var int local_b0h @ rbp-0xb0
| ; var int local_80h @ rbp-0x80
| ; var int local_18h @ rbp-0x18
| ; var int local_10h @ rbp-0x10
| ; var int local_9h @ rbp-0x9
| ; var int local_8h @ rbp-0x8
| ; var int local_4h @ rbp-0x4
| ; DATA XREF from 0x0040078d (entry0)
| 0x00400ba0 55 push rbp
| 0x00400ba1 4889e5 mov rbp, rsp
| 0x00400ba4 4881ecb00000. sub rsp, 0xb0
| 0x00400bab c645f700 mov byte [local_9h], 0
| 0x00400baf 488d8550ffff. lea rax, [local_b0h]
| 0x00400bb6 4889c6 mov rsi, rax
| 0x00400bb9 bf571d4000 mov edi, str.robot_instructions ; 0x401d57 ; "robot_instructions"
| 0x00400bbe e87d0d0000 call fcn.00401940
| 0x00400bc3 85c0 test eax, eax
| ,=< 0x00400bc5 740a je 0x400bd1
| | 0x00400bc7 b800000000 mov eax, 0
| ,==< 0x00400bcc e9e80c0000 jmp 0x4018b9
| |`-> 0x00400bd1 c60574252000. mov byte [0x0060314c], 1 ; [0x60314c:1]=0
| | 0x00400bd8 be00000000 mov esi, 0
| | 0x00400bdd bf571d4000 mov edi, str.robot_instructions ; 0x401d57 ; "robot_instructions"
| | 0x00400be2 b800000000 mov eax, 0
| | 0x00400be7 e864fbffff call sym.imp.open ; int open(const char *path, int oflag)
| | 0x00400bec 8945f0 mov dword [local_10h], eax
| | 0x00400bef b800000000 mov eax, 0
| | 0x00400bf4 e8d4fdffff call sub.calloc_9cd ; void *calloc(size_t nmeb, size_t size)
[0x00400ba0]>
Alright, it seems pretty clear how our file must be named. The string robot_instructions before the sym.imp.open call is a pretty decent hint! Let’s create it and try again:
$ touch robot_instructions
$ ./spacemision
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X \ X
X \######## X
X o X
X \OO X
X \ X
X___-## X
X # ##/\/\/\/\/\/\/\/\ X
X_#__## | X
X | ## ____#----__---| X
X | /## | # | X
X | | | |/\ /\/\/\/\/\/X
X \==/ |## | X
X | |/\/\/\/\/\/\/\ X
X####__########_####### X
X \/\/\/\ /\/\/\/X
X X
X X
X X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
BOOOOOOM!!!
Cool! Even our inactivity caused the bomb to explode, we at least got what seems like a map in our screen. Now we should try to understand how our rover is moved, i.e. what commands we have to write into the robot_instructions file.
Up, Down, Left, Right
Once opened, a file must be read, so a good place to look at should be around sym.imp.read calls.
[0x00400ba0]> axt sym.imp.read
call 0x4009c2 call sym.imp.read in sub.read_9a6
Ok, sym.imp.read is called inside the function sub.read_9a6, where is that function called from?
[0x00400ba0]> axt sub.read_9a6
call 0x401633 call sub.read_9a6 in main
Aha! Let’s take a look:
[0x00400ba0]> s 0x401633
0x00401633]> pd 20
| 0x00401633 e86ef3ffff call sub.read_9a6 ; ssize_t read(int fildes, void *buf, size_t nbyte)
| 0x00401638 8845f7 mov byte [local_9h], al
| 0x0040163b 0fbe45f7 movsx eax, byte [local_9h]
| 0x0040163f 83f85e cmp eax, 0x5e ; '^' ; '^' ; 94
| ,=< 0x00401642 742f je 0x401673
| | 0x00401644 83f85e cmp eax, 0x5e ; '^' ; '^' ; 94
| ,==< 0x00401647 7f13 jg 0x40165c
| || 0x00401649 83f83c cmp eax, 0x3c ; '<' ; '<' ; 60
| ,===< 0x0040164c 0f84b3010000 je 0x401805
| ||| 0x00401652 83f83e cmp eax, 0x3e ; '>' ; '>' ; 62
| ,====< 0x00401655 7479 je 0x4016d0
| ,=====< 0x00401657 e916020000 jmp 0x401872
| |||`--> 0x0040165c 83f876 cmp eax, 0x76 ; 'v' ; 'v' ; 118
| |||,==< 0x0040165f 0f84c8000000 je 0x40172d
| ||||| 0x00401665 83f879 cmp eax, 0x79 ; 'y' ; 'y' ; 121
| ,======< 0x00401668 0f84ed010000 je 0x40185b
| ,=======< 0x0040166e e9ff010000 jmp 0x401872
Perfect, it seems our guessing was right! The file seems to be read, one byte at a time,and then compared to one of the following characters: ^,<,>,v,y. The first four seem quite obvious: the rover probably goes up, left, right and down respectively each time one of these characters is read. A quick test shows we are right, as a little arrow appears on screen performing the moves we introduce into the robot_instructions file.
But, there’s that y command which doesn’t directly translate to any movement (the rover stands still). Maybe we should dive a bit more and see what the code does when a y is read.
The y command
Following the jmp address we can try to see what happens with this command:
[0x00401633]> s 0x40185b
[0x0040185b] pd 6
| 0x0040185b 8b15e3182000 mov edx, dword [0x00603144] ; [0x603144:4]=0
| 0x00401861 8b05d9182000 mov eax, dword [0x00603140] ; [0x603140:4]=0
| 0x00401867 89d6 mov esi, edx
| 0x00401869 89c7 mov edi, eax
| 0x0040186b e87af2ffff call fcn.00400aea
| ,=< 0x00401870 eb04 jmp 0x401876
Hmmm. Two values are read from memory (0x00603144 and 0x00603140), moved to registers and then a function is called. Following the breadcrumbs:
[0x0040185b]> s fcn.00400aea
[0x00400aea]> pd 34
/ (fcn) fcn.00400aea 108
| fcn.00400aea (int arg_6h);
| ; var int local_18h @ rbp-0x18
| ; var int local_14h @ rbp-0x14
| ; var int local_6h @ rbp-0x6
| ; var int local_4h @ rbp-0x4
| ; arg int arg_6h @ rbp+0x6
| ; CALL XREF from 0x0040186b (main)
| 0x00400aea 55 push rbp
| 0x00400aeb 4889e5 mov rbp, rsp
| 0x00400aee 897dec mov dword [local_14h], edi
| 0x00400af1 8975e8 mov dword [local_18h], esi
| 0x00400af4 8b45ec mov eax, dword [local_14h]
| 0x00400af7 c1e006 shl eax, 6
| 0x00400afa 6625c007 and ax, 0x7c0
| 0x00400afe 89c2 mov edx, eax
| 0x00400b00 8b45e8 mov eax, dword [local_18h]
| 0x00400b03 01c0 add eax, eax
| 0x00400b05 83e03e and eax, 0x3e
| 0x00400b08 09d0 or eax, edx
| 0x00400b0a 668945fa mov word [local_6h], ax
| 0x00400b0e c745fc000000. mov dword [local_4h], 0
| ,=< 0x00400b15 eb36 jmp 0x400b4d
| .--> 0x00400b17 8b45fc mov eax, dword [local_4h]
| || 0x00400b1a 4898 cdqe
| || 0x00400b1c 0fb784009030. movzx eax, word [rax + rax + 0x603090] ; [0x603090:2]=460
| || 0x00400b24 663b45fa cmp ax, word [local_6h]
| ,===< 0x00400b28 751f jne 0x400b49
| ||| 0x00400b2a 8b45fc mov eax, dword [local_4h]
| ||| 0x00400b2d 4898 cdqe
| ||| 0x00400b2f 0fb784009030. movzx eax, word [rax + rax + 0x603090] ; [0x603090:2]=460
| ||| 0x00400b37 83c801 or eax, 1
| ||| 0x00400b3a 89c2 mov edx, eax
| ||| 0x00400b3c 8b45fc mov eax, dword [local_4h]
| ||| 0x00400b3f 4898 cdqe
| ||| 0x00400b41 668994009030. mov word [rax + rax + 0x603090], dx ; [0x603090:2]=460
| `---> 0x00400b49 8345fc01 add dword [local_4h], 1
| !| ; JMP XREF from 0x00400b15 (fcn.00400aea)
| |`-> 0x00400b4d 837dfc06 cmp dword [local_4h], 6 ; [0x6:4]=-1 ; 6
| `==< 0x00400b51 7ec4 jle 0x400b17
| 0x00400b53 90 nop
| 0x00400b54 5d pop rbp
\ 0x00400b55 c3 ret
Wow, this one’s a little bigger. Let’s try to understand it step by step. First, the two values previously read from memory (now saved into edi and esi) are moved into two local variables, local_14h and local_18h. Then, a series of transformations are applied to these values. Summarized:
local_14his shifted 6 bits to left (or multiplied by 64) and then bitwise-and‘ed with the constant value0x7c0. The resultant value is saved intoedx.local_18his summed to itself (or multiplied by 2), bitwise-and‘ed with the constant value0x3eand then bitwise-or‘ed with the previous value stored inedx. The resulting value is saved inlocal_6h.
At this point, the transformation is finished and a loop begins, using local_4h as the iterator, beginning with 0 and ending with 6, so that’s 7 iterations. In every iteration, memory is accessed at the base address of 0x603090 plus 2 * the current iteration (that’s 0, 2, 4…). The value obtained from memory is compared to the transformed value that’s in local_6h.
Let’s stop here for a moment and make and educated guess. From what we have seen, when a y is read, two values are passed to a function. Since this is a 2D game, the probable candidates for this two values are the coordinates X and Y. This can be confirmed dynamically, setting breakpoints with db at the beginning of the function and seeing that, by writing y<y into robot_instructions, the execution stops twice: exi has the same value both times (0x4), but edi decreases in 1 the second time (so it has the value 0x3). This seems to indicate that esi (local_18h) contains the Y coordinate and edi (local_14h) the X coordinate.
If this is true, what is happening next seems pretty obvious: X and Y are transformed (hashed/obfuscated) into a single value, and that is compared to a value read from memory. If they are the same, that memory address is written with something else. If not, the loop continues and the next memory address is compared to the value obtained from the current coordinates, up to 7 comparisons. Then the function ends.
Whew, did you read all that? Well, if you did, you probably know what’s up by now, but if you didn’t here’s a little TL;DR:
- The
ycommand attempts to deactivate a bomb in the current location - 7 positions are obtained from memory, so probably there are 7 bombs in the whole map
This is getting interesting! We only have to get the 7 bomb positions from memory and we are done, right? Well, not quite.
The 7 bombs
By placing a breakpoint at 0x00400aea, we can see the 7 values compared to our obfuscated coordinates and save them. These are the obtained values:
0x1cc 0x5c2 0x04e 0x186 0x394 0x0e0 0x61c
Of course, these are obfuscated with the same transformations applied to the current coordinates, so we still don’t have the positions for the 7 bombs. At this point, I thought of writing a “deobfuscation” function that could obtain the coordinates for every obfuscated value. But after some minutes of trying, I started to see maybe there was an easier way.
We are playing in a 40x20 map. That’s 800 possible XY combinations where our rover can be at a given time, without taking obstacles into consideration. That is a very reasonable value to try a “brute-force” attack, as if the positions of the bombs where hashed and we were trying to crack them. And coding the obfuscation function is way easier, as it’s only a matter of translating assembly to Python. The following script accomplishes exactly that:
def obfuscate(x, y):
temp = x*64
temp = temp & 1984
temp2 = y*2
temp2 = temp2 & 62
return temp | temp2
values = [ 0x1cc, 0x5c2, 0x04e, 0x186, 0x394, 0x0e0, 0x61c ]
for x in range(40):
for y in range(20):
value = obfuscate(x,y)
if value in values:
print x,y,hex(value)
values.remove(value)
Drum roll, please!
$ python bombs.py
1 7 0x4e
3 16 0xe0
6 3 0x186
7 6 0x1cc
14 10 0x394
23 1 0x5c2
24 14 0x61c
Hacker voice: Got it.
A matter of optimization
We are done! Our reversing skillz are the best ever! We are l33t h4ck3rs! Now we just have to write a path that walks over all the positions, deactivates all bombs and we won, right? Right?
Well, it seems not. Remember that message at the beginning that mentioned the rover’s battery is limited? That means we have a limited number of movements before the battery dies. Uh, oh.
Yes, it’s only a matter of finding the optimal way. And yes, there is a “trick” that I discovered by chance but that can be found in the code: the _ characters in the map are special, in the sense that they are not the same kind of obstacle as the rest of them (X, #, - and so on). If the rover walks into a _ from up to down, it jumps above it instead of stopping. Cool! That’s actually the only way of reaching the bomb at (1,7), and it was the only reason I discovered this. Later, I checked in the code that the v command has a special treatment just for this case.
But even with this trick, I kept writing paths of >190 movements, and the battery of our rover only lasts for 179. Here I started thinking on finding the optimal path programatically, but a part of me refused the approach as over-complicated. “It’s only a one star challenge, it should be easier”, I thought. And then began a deep navigation into the assembly, trying to find other special obstacles that maybe allowed for “teleportation” from one point to another, like wormholes or something.
Needless to say, that led to nowhere. After an undisclosed amount of hours, I fell back into the good old manually counting positions and discovered a few optimization errors in my path. I reduced it to 185, then 183, and then, finally, 179 movements. It ultimately looked like this:
$ cat robot_instructions
^>>y
<<vv<v>vvv>>^>^>^>>>>>>>>>>v<v<<<^y
v>>vv<vv>>>>>>>>>>>>>>>^^<<<<<<y
>>>>>>>>>>>>>>^^<<<<<<<<<<<^^>>>^^^^^^^^^<<<<<<<y
>>>>>>>vv<<<<<<<<<<<<<<<<<<<<<vvv<<y
^<<<<<<vy
vvvvv>>>>vv<<y
Was it victory?
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X \ X
X \######## X
X o X
X \OO X
X \ X
X___-## X
X # ##/\/\/\/\/\/\/\/\ X
X_#__## | X
X | ## ____#----__---| X
X | /## | # | X
X | | | |/\ /\/\/\/\/\/X
X \==/ |## | X
X | |/\/\/\/\/\/\/\ X
X####__########_####### X
X \/\/\/\ /\/\/\/X
X < X
X X
X X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
You saved us all, thank you!
Yay!
Conclusion
To wrap up, I got a lot of fun with this challenge. It was my first time using radare2, and almost my first reversing challenge too. I learned quite some r2 commands in the process, and lost a little fear on reading assembly ;-)
The final part of finding the optimal path was a little frustrating, and I still feel maybe there was a way to automate the process. But well, sometimes banging your head against the wall is what you need to take a deep breath and reconsider your options.
Big thanks to condret for providing the challenge, to pancake and the rest of the r2con2017 organization for setting up such a wonderful event, and to t0n1 and as0ler for offering their help when I got stuck.