solution to spacemision crackme

spacemision.txt

This was a very fun crackme! Instead of providing a simple "password: " prompt or something like that the author actually wrote a tiny game to play with.


	# ./spacemision
	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!


So as it looks like this is some sort RPG. Let's go to r2!


	:> pd 20 @ main
	┌ (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 [rbp - 9], 0
	│           0x00400baf      488d8550ffff.  lea rax, [rbp - 0xb0]
	│           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 [rip + 0x202574], 1 ; [0x60314c:1]=1
	│      │    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 [rbp - 0x10], eax
	│      │    0x00400bef      b800000000     mov eax, 0
	│      │    0x00400bf4      e8d4fdffff     call sub.calloc_9cd         ; void *calloc(size_t nmeb, size_t size)


Ok we need to store something into a file called "robot_instructions" inside our current working dir. Further down the main function we see a lot of calls to this function:


	:> pd 1 @0x00400c27
	│           0x00400c27      e825feffff     call fcn.00400a51


If we analyze this function, we notice that it's building the char map for the game. We can have a look at it:


	:> px@0x01b1d027
	- offset -   0 1  2 3  4 5  6 7  8 9  A B  C D  E F  0123456789ABCDEF
	0x01b1d027  2020 2020 2020 2020 2020 2020 2020 2020                  
	0x01b1d037  580a 5820 2020 2020 2020 2020 2020 2020  X.X             
	0x01b1d047  2020 2020 2020 2020 2020 2020 2020 2020                  
	0x01b1d057  2020 2020 2020 2020 2058 0a58 2020 2020           X.X    
	0x01b1d067  2020 2020 2020 2020 2020 2020 2020 2020                  
	0x01b1d077  2020 2020 2020 2020 2020 2020 2020 2020                  
	0x01b1d087  2020 580a 2020 2020 2020 2020 2020 2020    X.            
	0x01b1d097  2020 2020 2020 2020 2020 2020 2020 2020                  
	0x01b1d0a7  2020 2020 2020 2020 2020 2020 0a20 2020              .   
	0x01b1d0b7  2020 2020 2020 2020 2020 2020 2020 2020                  
	0x01b1d0c7  2020 2020 2020 2020 2020 2020 2020 2020                  
	0x01b1d0d7  2020 2020 200a 2020 2020 2020 2020 2020       .          
	0x01b1d0e7  2020 2020 2020 2020 2020 2020 2020 2020                  
	0x01b1d0f7  2020 2020 2020 2020 2020 2020 2020 0a20                . 
	0x01b1d107  2020 2020 2020 2020 2020 2020 2020 2020                  
	0x01b1d117  2020 2020 2020 2020 2020                           


Once it has finished building the map, we can see the start of the game loop further down the main function. Inside the mainloop we can also see what chars are evualated from the robot_instructions file.


	:> pd 14 @ 0x0040163f
	│           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


The chars "^<>v" are obviously used to move our robot around, but the char "y" does not fit in and thus will get special attention. When this char is found the following function will be called:


	:> pdf @ fcn.00400aea
	┌ (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 [rbp - 0x14], edi
	│           0x00400af1      8975e8         mov dword [rbp - 0x18], esi
	│           0x00400af4      8b45ec         mov eax, dword [rbp - 0x14]
	│           0x00400af7      c1e006         shl eax, 6
	│           0x00400afa      6625c007       and ax, 0x7c0
	│           0x00400afe      89c2           mov edx, eax
	│           0x00400b00      8b45e8         mov eax, dword [rbp - 0x18]
	│           0x00400b03      01c0           add eax, eax
	│           0x00400b05      83e03e         and eax, 0x3e
	│           0x00400b08      09d0           or eax, edx
	│           0x00400b0a      668945fa       mov word [rbp - 6], ax
	│           0x00400b0e      c745fc000000.  mov dword [rbp - 4], 0
	│       ┌─< 0x00400b15      eb36           jmp 0x400b4d
	│      ┌──> 0x00400b17      8b45fc         mov eax, dword [rbp - 4]
	│      |│   0x00400b1a      4898           cdqe
	│      |│   0x00400b1c      0fb784009030.  movzx eax, word [rax + rax + 0x603090] ; [0x603090:2]=460
	│      |│   0x00400b24      663b45fa       cmp ax, word [rbp - 6]
	│     ┌───< 0x00400b28      751f           jne 0x400b49
	│     │|│   0x00400b2a      8b45fc         mov eax, dword [rbp - 4]
	│     │|│   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 [rbp - 4]
	│     │|│   0x00400b3f      4898           cdqe
	│     │|│   0x00400b41      668994009030.  mov word [rax + rax + 0x603090], dx ; [0x603090:2]=460
	│     └───> 0x00400b49      8345fc01       add dword [rbp - 4], 1
	│      ↑│      ; JMP XREF from 0x00400b15 (fcn.00400aea)
	│      |└─> 0x00400b4d      837dfc06       cmp dword [rbp - 4], 6      ; [0x6:4]=-1 ; 6
	│      └──< 0x00400b51      7ec4           jle 0x400b17
	│           0x00400b53      90             nop
	│           0x00400b54      5d             pop rbp
	└           0x00400b55      c3             ret


Note that our current position is passed to this function as arguments. We also see a loop that is run 7 times. So this function might actually check whether we found a bomb!
However, it is obfuscated a bit but already have everything what we need. To get the (obfuscated) bomb positions:


	:> px 14 @ 0x603090
	- offset -   0 1  2 3  4 5  6 7  8 9  A B  C D  E F  0123456789ABCDEF
	0x00603090  cc01 c205 4e00 8601 9403 e000 1c06       ....N.........


What we can do now is rebuild the algorithm and brute force the bomb positions. Consider the following python script:


	b=[0x01cc,0x05c2,0x004e,0x0186,0x0394,0x00e0,0x061c]
	
	def fun(x,y):
	    x = x << 6
	    x = x & 0x7c0
	    y *= 2
	    y = y & 0x3e
	    y = y | x
	    return y
	
	for i in range(0,40):
	    for j in range(0,20):
	        if fun(i,j) in b:
	            print(str(i) + "/" + str(j))


So here be bombs:


	# python space.py
	1/7
	3/16
	6/3
	7/6
	14/10
	23/1
	24/14
	33/7
	35/16
	38/3
	39/6

	
The script found 11 bombs while in the game it only checks against 7 bombs. I found this odd and spoke to the author of the crackme and it turned out to be a bug in the crackme itself. Caused by:


	y *= 2
	y = y & 0x32

So the y coordinate is always forced to be in the range of 0..31 but at this point you should already know that the maps row width is acutally 40 chars. This results in the fact that certain bombs can be found twice (x coordinate remains the same while y is differnt, but it doesn't matter) and it is up to the player, for which bombs he wants to go.

So filled the bombs into the map. The chars "@ABCD" are representing bombs. For the bombs "ABCD" we can choice which one of the A, B, C, and D we want to go for:


	XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
	X                   \  @               X
	X                    \########         X
	X     Co                              CX
	X v  \OO                               X
	X       \                              X
	X___-##@                               X
	XA#  ##/\/\/\/\/\/\/\/\          A     X
	X_#__##                |               X
	X  | ##  ____#----__---|               X
	X  |    /##  |@#       |               X
	X  |    |    |         |/\  /\/\/\/\/\/X
	X   \==/     |##       |               X
	X            |         |/\/\/\/\/\/\/\ X
	X####__########_####### @              X
	X                      \/\/\/\  /\/\/\/X
	X  B                               B   X
	X                                      X
	X                                      X
	XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


So we know where the bombs are (@ABCD), how to control our robot (^<>v), and how to diffuse a bomb (y). What's left is to find a path that defuses all bombs while not using to many chars:


	:> pd 14 @ 0x00401885
	│       |   0x00401885      817dfcb30000.  cmp dword [rbp - 4], 0xb3   ; [0xb3:4]=-1 ; 179
	│       └─< 0x0040188c      0f8ea6fcffff   jle 0x401538
	│           0x00401892      488b45e8       mov rax, qword [rbp - 0x18]
	│           0x00401896      4889c7         mov rdi, rax
	│           0x00401899      e822eeffff     call sym.imp.puts           ; int puts(const char *s)
	│           0x0040189e      488b45e8       mov rax, qword [rbp - 0x18]
	│           0x004018a2      4889c7         mov rdi, rax
	│           0x004018a5      e806eeffff     call sym.imp.free           ; void free(void *ptr)
	│           0x004018aa      8b45f0         mov eax, dword [rbp - 0x10]
	│           0x004018ad      89c7           mov edi, eax
	│           0x004018af      e83ceeffff     call sym.imp.close          ; int close(int fildes)
	│           0x004018b4      b800000000     mov eax, 0
	│              ; JMP XREF from 0x00400bcc (main)
	│           0x004018b9      c9             leave
	└           0x004018ba      c3             ret


As stated in the prologue, our roboter is running low on fuel. This means that we can perform 180 movements to defuse the bombs. Of course there are multiple ways to solve it. Here's how i did it:


	# cat robot_instructions
	^>>>y^>>>vvvv<<y^<<<<v>vv>>>^^>>>>>>>>>>>v<<v<<^yvv>>>vvvv<<vv>>>>>>>>>>>>>>>>>>>>y<<<<^^<<<<<<<y>>>>>>>>>>>>>>^^<<<<<<<<<<<^^>>>^^^>>>y<<<^^^^^^^<<<<<<<y
	
	# ./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
	You saved us all, thank you!