CTF Writeup - Flare-On 2017 - 05: pewpewboat.exe

• Name - pewpewboat.exe
• Category - Reverse Engineering
• Points - 1
• Binary - Download here

The challenge is a 64-bit ELF binary, despite it's file extension. Launching it we get a Battleship game!

The goal is to beat the game by sinking all the ships, which we have no visibility of, in each level by inputting coordinate values. Completing the first level we are greeted with:

Note that the solution spells out the letter 'F'! We try to input the Md5 hash of the 4-char string to no avail. At this point we're not sure what's meant by NotMD5Hash so let's look at the binary under IDA. The main() function starts by loading some stack strings and initializes some stuff for the game; it then goes into a main loop which has 2 important functions (green basic block): sub_403047() which sets up the next level and sub_403C05() where we get to actually play the level:

The function sub_403C05() further contains another loop which iterates for each coordinate we supply:

Each time we input a coordinate, the loop displayed above does the following:

1. Sets up the curses text-based user interface (sub_4031E1)
2. Displays the grid (sub_403263)
3. Processes the coordinate to determine if we've hit a ship or not, checks if we have completed the level and displays the appropriate messages (sub_4038D6)
4. Asks the user to input the next coordinate (sub_40377D)

The first objective is to find what is meant by NotMd5Hash so we can progress further into the game. The function that deals with this is sub_403530(); the stack string NotMd5Hash("%s") at the beginning gives it away. Let's look at the first part of this function:

The green basic block is looped over 4 times and randomly generates the 4 characters for the NotMd5Hash string. It then goes to the yellow basic block which computes the MD5 hash of the 4-char string (whattt!???), prints out the NotMd5Hash string and waits for our input. But we've already tried the MD5 and it didn't work! Let's check what comes next:

The blue basic block loops over each byte of the 16-byte Md5 output, NOT's the value and stores the hex representation of it. The result is then compared to our input in the purple basic block. So this is what is meant by NotMd5Hash! The values of the output are NOT'd. The following is a python script to compute this:

import md5

m = md5.new("GHND").digest()
print ''.join(["%02X" % (256 + ~ord(x)) for x in m])

At this point we can continue playing the game and try to beat each level by guessing the coords. Of course we're not doing that as it is very time consuming and painful. So, the next step is to find a way to reveal where the ships are for each level. A good way to checking this is to trace what happens to our input coord and how a HIT or MISS is determined based on this input.

Our input is read in sub_40377D():

unsigned __int64 __fastcall sub_40377D(__int64 a1)
{

    [ .. snip .. ]

    printf(format, &v6);
    if ( fgets(&s, 17, stdin) )
    {
        row = (char)(s & 0xDF) - 0x41;
        col = v5 - 0x31;
        if ( row < 0 || row > 7 || col < 0 || col > 7 )
        {
            sub_403411(&s, 17LL);
        }
        else
        {
            *(_QWORD *)(a1 + 8) |= 1LL << (8 * (unsigned __int8)row + col);
            *(_BYTE *)(a1 + 28) = s & 0xDF;
            *(_BYTE *)(a1 + 29) = v5;
        }
    }
    return __readfsqword(0x28u) ^ v28;
}

The function reads our input at line 7 and maps the row and column to a number between 0 and 7 on lines 9 and 10. For example, 'B6' translates to row = 1 & col = 5 whilst 'E2' translates to row = 4 & col = 1. Both values are then validated on line 11 to ensure they're on the board. Finally, at line 17, the values are combined into a single value that represents the input coordinate. This is the important part as it will be used to determine a HIT or a MISS. The following is a python 1-liner, which we'll use later on, to compute this value:

singlify = 1 << (row * 8 + col)

We now move onto the part where a HIT or MISS is determined. This happens in sub_4038D6() which also decides what message is displayed to the user based on their coord input:

The decision happens in the yellow basic block. On the 4th line of this block, RAX holds a level configuration number which determines the location of all the ships. This value is AND'd with our coord number. If the number remains the same, then it goes to the green basic block which signifies a HIT, if not it goes to the red basic block which displays the message 'You missed :('. If we put a breakpoint and collect the configuration number for the first level we get: 0x0008087808087800.

We now combine everything we know. The following is a python script which, given a configuration number, determines all the hits and also displays them on a grid:

def draw_ships(input):    
    hits = []

    for row in range(8):
        for col in range(8):
            singlify = 1 << (row * 8 + col)
            if singlify & input == singlify:
                hits.append(chr(row + 0x41) + chr(col + 0x31))
                print "X",
            else:
                print "_",
        print
    print
    return hits
    
ship_config = 0x0008087808087800

print draw_ships(ship_config)

Running the script gives us:

Command Prompt

C:\>python solution.py _ _ _ _ _ _ _ _ _ _ _ X X X X _ _ _ _ X _ _ _ _ _ _ _ X _ _ _ _ _ _ _ X X X X _ _ _ _ X _ _ _ _ _ _ _ X _ _ _ _ _ _ _ _ _ _ _ _ ['B4', 'B5', 'B6', 'B7', 'C4', 'D4', 'E4', 'E5', 'E6', 'E7', 'F4', 'G4'] C:\>

Notice that this coincides perfectly with what we've gotten when we played the game manually (check 2nd image from above). With these 2 scripts we're now guaranteed to hit all the ships before running out of ammo and also solve the NotMd5hash challenge each time. Make sure to put a break point to collect the configuration number at each level and get a list of HIT coords from the script.

Going through the 10 levels, we collect the string 'FHGUZREJVO' from the solutions, and the game displays the following message:

Removing the PEWs we get:

Aye! You found some letters did ya? To find what you're looking for, you'll want to re-order them: 9, 1, 2, 7, 3, 5, 6, 5, 8, 0, 2, 3, 5, 6, 1, 4. Next you let 13 ROT in the sea! THE FINAL SECRET CAN BE FOUND WITH ONLY THE UPPER CASE.

This is referring to the string 'FHGUZREJVO'. After we do what we're told we end up with 'BUTWHEREISTHERUM'. Feeding this to the game instead of a coordinate: