Put The Flags Out! — Hacking Minesweeper

Background

Two weeks from today, the first Low Level & Security Celebration will take place. This event is organized by Baot and its goal is to attract more women into the low level and security fields.

I was given the amazing yet terrifying task of teaching the Reverse Engineering workshop. When I started planning the workshop’s last session — I had no idea what to do. I was looking for an interesting challenge that I could use in my workshop.

A dear friend of mine, Aviad Carmel, is a super-skilled reverser and my reverse engineering mentor. He suggested that I hacked Minesweeper, such that when Minesweeper starts up, all mines are marked with flags.

It took me one week, tens of hours, many Windows API Google-searches and way too many breakpoints to finish, but I finally did it.

I was so excited I had to tweet something, which proved as a great thing to do as I received many likes, comments, retweets and GitHub-link requests. I even got to know a very talented, young researcher who (in a strange coincidence) hacked Minesweeper too and published his own post about it!

But that was all intro — let’s get to the point. I am about to do 2 things in this post:

1. show you the hard, long, Sisyphean way I took in order to solve the challenge;
2. tease you with two follow-up challenges.

Let’s go.

I Did It My Way

As I just said, my way took forever, or so it felt like. I went from IDA to OllyDbg and back to IDA, put breakpoints on every suspicious line, filled my notebook with addresses I later forgot and basically got lost. a lot.

Aviad noticed my frustration and wrote me something on WhatsApp which I then scribbled on a sticky note right below my screen:

The most important thing is to persist, to not give up, truly believe that there is no chance for the computer to beat you. There is no such thing as “difficult”, perhaps just “takes more time”.

Aviad’s words and a cup of coffee keep me highly-motivated.

My strategy went something like this:

• Find the code that draws a flag upon a right-click (let’s call this function draw_flag).
• Find the code that draws the board, (let’s call this function draw_board).
• Change the function draw_board such that whenever a mined square is met — draw_flag is called with the proper parameters.

It was tedious, but eventually I found the line that draws a flag on a square when it is right-clicked on. When stepping over this line with an F8 — the flag immediately appeared on the board.

The highlighted line is the one that draws a flag on a square.

According to MSDN, the function on this line — BitBlt — “performs a bit-block transfer of the color data corresponding to a rectangle of pixels from the specified source device context into a destination device context”.
HUH?! This was Greek to me but I guessed that the function copied pixels from a source to a destination and that source device context was the argument I cared about.

The value of this hSrcDC argument is fetched from an array located at 1005A20, using an offset which is stored in the EDX register. When drawing a flag, this offset equals 0x0E (see the screenshot above and notice line 1002676 and the EDX register).

My next guess was that this BitBlt function was used not only to draw a flag, but to draw a mine or an empty square as well. I used IDA’s xrefs (cross-references) feature to detect where BitBlt is used elsewhere:

I went to the second location in the code where BitBlt was called. To my pleasant surprise, the call appeared in a block which was a part of a loop. This strengthened my assumption that the initial board was drawn using this function.

This time, the value of hSrcDC was set by accessing the same hdcSrc array with an offset stored in EAX. Examining the value of EAX, I could say that:

EAX = *(EBX + ESI) & 1F

0x1F is a literal, but what are EBX and ESI? Looking at the two blocks before, I saw that EBX was a fixed location in memory (1005360) and ESI was the loop variable. I examined the address 1005360 in memory and found something that looked a lot like a mine-field:

I noticed two things:

• Each pair of 0x10’s is exactly 9-bytes distant. So 0x10 must be a delimiter for rows on the board.
• There were exactly ten 0x8F’s, which suggested that 0x8F is a value representing mines. This left 0x0F to represent an empty square.

By ANDing with 0x1F on line 10026E9 (see IDA screenshot), both 0x0F and 0x8F end up being 0x0F, but I wanted them to be 0x0E, remember?😉

This AND instruction was too strict and it was the key to what I was trying to achieve. I needed to make this AND instruction more flexible and take into consideration the value of the currently-processed square. The logic I wanted to implement was this:

if board_location[square_position] == 0x8F:
   draw_flag
else:
   draw_empty_square

The existing AND instruction takes 3 bytes of opcode. My logic was way beyond 3 bytes. I needed a code-cave to my rescue.

I searched the executable file for a slot in the code section with enough null bytes which I could replace with my own code. Using a hex-editor and a nice online assembler, I added my opcodes, corresponding to the following x86 instruction sequence:

1004A60   CMP AL, 8F
1004A62   JNZ SHORT patched_minesweeper.01004A66
1004A64   MOV AL, 0E
1004A66   PUSH DWORD PTR DS:[EAX*4+1005A20]
1004A6D   JMP patched_minesweeper.010026F3

Notice how this assembly code implements the pseudo-code from above:

1. AL is compared to 0x8F (a mine value).
2. If it is not a mine, go on with the original code, namely draw an empty square.
3. If it is a mine, replace 0x8F with 0x0E (the value required for drawing a flag).

In order to run my new code, I needed to use a JMP instruction from the original code. But even the JMP opcode takes more than 3 bytes, meaning I had to override not only the AND instruction but also the one following it. I padded the remaining bytes with NOPs and added the overridden instruction to my patch (see line 1004A66 above).

So the original code was modified to look like this:

010026E9    JMP patched_minesweeper.01004A60
010026EE    NOP
010026EF    NOP
010026F0    NOP
010026F1    NOP
010026F2    NOP

Minesweeper was now patched to mark mines with flags. The end.

You will Do It the Other Way

Now the fun part.

When I talked to Aviad to share my solution, he told me that I had taken a long and winding road. Apparently, there is a hack which is significantly more elegant and efficient than what I did. If you want to give it a try, please do.

Here are 2 hints:

1. It’s a one-liner.
   Namely, you can change one line only to make the game start with flags on all mined squares.
2. Instead of changing how the mine-field is printed, change the mine-field itself. How would you create it if you were the Minesweeper programmer?

One Last Riddle

When I opened my patched version of Minesweeper, I wanted to perform a sanity check. I clicked on a flag and expected the game to be over (since flags mark mines). That didn’t happen, and the game was over only after clicking on a second flag. Why?

You are more than welcome to contact me for questions, notes, suggestions, etc.

Good luck and thanks for reading :)