Session #5 - Hacking Minesweeper
The last part is a guided session to hacking Microsoft's famous Minesweeper game. You are welcome to check my blog-post where I told the story of solving this challenge. Also, you can download the patched version here.
I would like to give all the credit for this exercise to Aviad Carmel and thank him a lot for the help and support he has given me.
If you haven't heard of Minesweeper - now is the right time. Get acquainted with the rules and play it a couple of times :)
Our goal will be to make Minesweeper print flags where there are mines, right when starting up. Differently put, we would like to expose the mines on start-up by printing flags on the mined squares.
Finding the Minefield
Now let's get into the heads of the Minesweeper developers.
Say we had to create a minefield - namely, some matrix, or an array of arrays - how would we determine which squares contain mines and which don't?
Since this decision should yield different results with every run of the game, we can assume that some randomization function is used to generate the minefield. Let's go for rand function :)
-
Download Minesweeper from this link.
-
Drag-and-drop it to IDA Pro.
-
Click on the Imports tab to see the function that winmine.exe imports.
-
Double-click on rand to reach the idata section, where all the addresses of imported functions can be found.
-
Click on rand to highlight it and then hit 'x'. The cross-references to rand will then appear.
-
Click on 'Ok' to move to the code which calls rand.
-
Nice! We just found the only place where rand is called.
Rename the function by clicking on sub_1003940, hitting 'n' and typing in a name like rand_caller.
Approaches
We can think of (at least) 2 different approaches to solving the problem:
-
Change the minefield.
Suppose we have a minefield somewhere is the memory of the Minesweeper process. This minefield must contain the information regarding mine locations, right?
If we manage to somehow change this information, so that a square with a mine will be marked with a flag - we're done.
Pseudo-illustration:
minefield_before = [[empty, mine, ..., empty], [...], ..., [...]]
minefield_hacked = [[empty, flag, ..., empty], [...], ..., [...]]
-
Change the printing function.
As Minesweeper is a GUI application, it contains graphics and uses a function which prints those graphics to the screen.
If we manage to find this function and pass it the argument corresponding to flag whenever there is a mine - we're done.
Pseudo-illustration:
if minefield[i] == mine:
print_square(flag)
else:
print_square(empty)
We will take the first road. You may want, at a later point, to try the
second.
Find rand
Static Analysis of rand_caller
Now let's figure out what rand_caller is.
This function receives one argument which IDA calls arg_0.
The function calls rand which returns a random integer in
the EAX register.
Then cdq is called. This instruction converts a double-word
into a quad-word. Namely, it expands the value in EAX
such that this value is stored in EDX:EAX.
When idiv is called, it takes the value in EDX:EAX and divides it by the function's argument (note that [esp+arg_0] is a synonym to "what is stored in the address ESP + the stack offset of arg_0".
After this division, the quotient resides in EAX whereas the remainder (modulo) is in EDX. The fact that EDX is moved to EAX right before the function returns implies that the relevant value is the division remainder.
To sum up, rand_caller randomizes a number and then performs a modulo, which makes sure the result does not exceed the value in arg_0.
Finding the calls to rand_caller
So now we know what rand_caller does. Let's find out where it is used. I remind you - our current goal is to find the place in code where the minefield is created or initialized.
-
Click on the name rand_caller to highlight it and then hit 'x' to show all cross-references.
-
In the xrefs windows, it can be seen the rand_caller is called from two places in the code which are 8 bytes away from each other. Go there by double-clicking on one of the xref entries.
Now doesn't this look like an interesting code construct? ;)