Reversing 500 challenge of CSAW CTF 2013
Impossible - 500 Points
WTF, his hp is over 9000! Beat the game to get your key.
On this challenge, we are provided with a single file, the filetype can be found out by looking at the strings within the file:
1 2 3 4
# strings impossible.nds [...] /home/kiwi/devkitPro/libnds/include/nds/arm9/background.h [...]
searching for parts of this string in - fill in your favourite search engine -, it becomes obvious that its a Nintendo DS game ROM.
First we load the rom into an emulator, we chose DeSmuMe, lets load the game(this is the console output):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
# desmume-cli --console-type=debug impossible.nds Slot 2: NONE Failed to set format: Invalid argument Microphone init failed. DeSmuME 0.9.8 svnr0 dev+ SoftRast Initialized with cores=1 File doesn't appear to have a secure area. ROM game code: #### ROM crc: 569666ED ROM serial: Homebrew ROM internal name: . DeSmuME .dsv save file not found. Trying to load an old raw .sav file. Missing save file impossible.dsv DEBUG_reset: 004F81B0 DeSmuME .dsv save file not found. Trying to load an old raw .sav file. Missing save file impossible.dsv INIT MAINMENUSTATE BEGIN RUN LOOP INIT GAMESTATE ADD ENT } repeated 36 times RENDER WTF \ pairwise repeated 8 times RENDER SHIP / ADD ENT } repeated 32 times RENDER WTF \ pairwise repeated 8 times RENDER SHIP / ADD ENT } repeated 32 times [...]
and this is how it looks:
At the bottom, in green, we have our own ship, at the top there is an invisible ship spraying out particles, that when hitting our ship destroy it.
But our ship can also fire off particles, the invisible ship just has much more power and hitting it will not harm it much.
Its obvious that we cant win because we die too fast and dont have enough fire power.
Time for IDA! (with a small loader from https://github.com/patois/NDSLdr especially suited for NDS images)
After some manual tweaking we can find the strings of the debug output and even references.
The number of times the "ADD ENT" message in the debug output is roughtly repeated matched the number of particles, the hidden ship sprayed out so we will follow this event.
The only reference to this debug string is in the function sub_2002820(now called s_add_ent):
The s_add_ent function in turn is referenced in 3 functions, two of these functions respectively call our function two times, the last(now called s_iteresting) of the 3 functions called it once inside of a loop.
That loop looks interesting because it repeats the call to s_add_ent 32 times!
We changed the number of iterations of this loop to 1 and tried the game again:
Success! Now we have much time to destroy the enemy... But we also need much time... :(
Anyway, the most referenced variable in this function is var_1c and it looks like a pointer to a struct(the references accessed (*var_1c) + X, so we looked at this memory region(gdb is helpfull here).
One of the values became smaller everytime we hit the enemy, so this was the hp!
We changed it to 1 and fired a last shot but nothing happened.
After some digging around at the memory address we found the key in cleartext: