Static Analysis of OJ's Police Quest

Roughly one week ago (end of November 2018), OJ published a CTF challenge, the goal (rather simple) is to exploit this binary. I'm trying to write those article while I reverse/exploit this game. In this first article I will focus on static analysis to gather information that will be usefull later to find and write an exploit.

Static analysis

I always like to spend a lot (too much ?) time on static analysis, try to guess how the code would behave when run. In this binary, symbols were not removed and it's hence much easier for us to find the relevant part of the source code.

Rooms

The setup function creates the links between the various rooms of the game we can already spot six rooms (study, kitchen, bathroon, hall, library and bar) from the function's body. Using the game's symbols (use_* functions), we can safely deduce that there are five items available in this game:

• Revolver

• Bullet

• Tissue

• Target

• Magnifying glass

After a deeper look to the 'GET' action (action_get), we are able to spot the link between an item and a room. A room can have a single item type, but there can be more than one item in the room. We are now able to write a type for a room in our game:

We can now apply this type to the list of rooms at offset 0x02051C0 (all_rooms):

As said, a room can have an item, and when it does, the pointer to the item datastructure is stored in the field called room_item, and the item structure looks like:

It was actually not that straightforward to re-create this, but my goal here is not to give an IDA tutorial, but to describe the steps I performed looking at an unkown binary. The first two fields are explicit, the count is the number of this item in this room followed by a function pointer that points to one of the create_* function, used to create an item that can be use by the user.

Creating an item

As shown previously, there is a link between a room and an item. From the rooms' list we can see that the first item we are interested in is located in the study room: the Revolver. In the setup function (or playing around in the game), we see that the study room is connected to the north of the hall room (the starting room).

When using the GET action in a room, many checks are performed, the first one checks that the room's item pointer is not null, compares the name given by the user to the item's one, checks that the item's count is not 0. Then it tries to find the item in the user's stuff (we will come back to that later).

There are three possible outcomes to this last check:

• the player already has the object with a count that is not 0 (he/she did not use the item yet), then the object can not be picked.

• the count is 0, then the user once had this object, but used it, and the item can be picked up again (the counter is simply incremented).

• the user never had this objet: this is the first time the user uses the GET action on this item's type. The game will create a new datastructure representing this item (which is not the same as the datastructure used by the rooms to keep track of their items).

To create an new item, the user must give it a name, the function then creates a hash (more info that later), tries to find an item with this hash in the user's stuff (I did not really figure the usage of the hash yet, so I can't explain why). If none is found, the item_create_fn function pointer that can be found in the item_room structure is called.

In order to be added to the user's stuff, the item is created on the heap (which can be interesting as, don't get me wrong, we are still trying to exploit this binary) by the item_create_fn function of the room_item structure.

User's stuff

Before we dig into the create_* function, I need to describe a bit the stuff symbol that can be found in this binary.

Found at address 0x0205320, this symbol represent the user's stuff. Surprisingly, it is a single 64bits pointer. In fact in this game, the stuff is a linked list of items, the stuff symbols simply points to the first item in the list, and each one points to the next (actually the list is reverse, the most recent item is the first one), we can deduce that from the end of the action_get:

In this picture, IDA shows revolver.prev_item but it could actually be any of the item, they all share common fields in their first 0x18 bytes. The revolver structure that would be inserted into the linked list when the user picks the revolver up looks like:

In this structure we find a pointer to the next/previous item in the list, a pointer to the room's item that was picked by the user, a pointer to the room's name and the item's hash (the one that was computed from the user's input). We can also find data related to a specific item, in this case, the serial number of the revolver as well as a boolean is_loaded that will be set to true only if we load a bullet into our revolver.

The last field of the structure is hidden_string this is filled for each item by the corresponding create_* function and does mostly nothing (I probably missed something here, but I can't find what yet).

Now that we have a rough overview of the user's stuff mechanism, let's focus on the functions that create those items.

create_* functions

As said previously, the goal of those functions is to create and fill an item when it's picked by the player. All of those function do at least a heap allocation using calloc and then, if needed, will set a few item specific fields. We find the hidden_string in all the item except the magnifying glass. The bullet and revolver item have an extra field storing the serial number. This serial number is a hex digit of length 18 (including the 0x prefix) that will be prompted to the player.

Conclusion

To conclude this part on user's item: each room can be linked to an item_type, when the user gets the item for the first time, a new object is created on the heap and added to the player's stuff, this item is a node of a linked list and contains information about its type and some information that I could not make any sense of yet.

While reading through this part of the binary, I did not find any vulnerability: bounds seems to be checks, safe functions are used, we can control many parameters. On the other hand, having some data on the heap open the door to a whole new range of exploit if something goes wrong: heap exploits.

Using an item

The action_use is the common entry point to any item usage, it goes through the list of available items and compares each name with the one given by the player (USE Revolver for instance). If such an item exists, the player must give (inside the get_matched_object function) the ID of the item. This is basically the value of the secret hash computed from the name given during the action_get. The get_match_object function then asks for the secret used to generate the hash, to make sure the player knows the original value that was used during the item's creation. The function then goes through the user's stuff and return the matching object (based on the hash). If the item exists, the corresponding use_item_fn is called. A full execution of this scenario is described below:

> GET Revolver

What secret name shall we give this Revolver? > test
This Revolver has no serial number. What serial number should we give it? > 0x1234567891234567
You sureptitiously acquire a single Revolver, we've given it the secret hash of 0xCC9EE3AB.

You are currently standing in the Study. To the SOUTH lies the Hall.

What do you want to do?
LOOK MOVE USE GET INVENTORY

> USE Revolver

What's the ID of the Revolver you want to use? > 0xCC9EE3AB
What's the secret of the Revolver that matches the ID? > test
You can't shoot a gun that hasn't got any bullets in it. Numpty.

The following picture shows where the item's specific use function is called, it's actually computed from the counter of the matching item, and, using some arithmetic, moved to the correct address in the all_items array.