Steve’s Blog

Everyday I wake up for work at 6:00am and get home at around 8:00pm. Since this only leaves me with two hours of spare time I try to get something constructive done during both 70 minute train rides. As much as I try, however, a little Minesweeper always manages to get played. While playing the other day, I was examining a small subset of the grid when I noticed that when I calculated all the possible mine positions for that isolated subset, it became apparent that there was a spot that couldn’t have a mine (normally when I play, I only examine a single cell to determine where mines may or may not be located). It was during this game that I decided to write a Minesweeper solver.
And it works pretty simply. When you examine a particular cell containing a number in a game of Minesweeper, it tells you how many adjacent spaces contain mines. For example, if you were to come across this configuration:

  A B C
1|? 0 0
2|0 1 ?
3|0 ? 0

You would know that there is one bomb which lies in either location A1, B3, or C2. Later it will become useful to also note which spaces do not contain mines. This will break each possibility into two groups: one group contains the spaces which have mines, the other contains spaces which do not. So our example above would be stored as:

mine-group: (A1), not-mine-group: (B3 C2)
mine-group: (B3), not-mine-group: (A1 C2)
mine-group: (C2), not-mine-group: (A1 B3)

As it turned out, writing code to divide these three unknown spaces into two groups was the hardest part. The function which does it is called ‘GenCombo’, and the function works by being passed in a list of elements to be divided – (a b c) for example – and a list of the group sizes, which in the above case would be size one for the ‘mine’ group, and size two for the ‘not mine’ group. The function then recursively pops an element off the first list and appends it to a particular group.

Now that the program can determine the possible configurations of a particular cell, there must be a way to combine them in order to reduce the total number of mine configurations. The particular configuration that made me realize how to do this looked like this:

  A B C D
1|? ? ? 0
2|0 1 1 0
3|0 0 0 0

The possible configurations for the number at position B2 are as follows:

mine-group: (A1), not-mine-group: (B1 C1)
mine-group: (B1), not-mine-group: (A1 C1)
mine-group: (C1), not-mine-group: (A1 B1)

Lets call these combinations C(B2).

The possible configurations for the number at C1 are:

mine-group: (B1), not-mine-group: (C1)
mine-group: (C1), not-mine-group: (B1)

This is C(C1).

To combine these, we take each possible pairing for each possibility and check for contradictions. To demonstrate, lets combine the first two possible configurations. To do this, we simply combine both ‘mine’ groups together and combine both ‘not mine’ groups together.

  (mine-group: (A1), not-mine-group: (B1 C1))
+ (mine-group: (B1), not-mine-group: (C1))
= (mine-group: (A1 B1), not-mine-group: (B1 C1 C1))

As we can see, there is a contradiction in this example in that there is an element that appears both in the ‘mine’ group AND in the ‘not mine’ group. What about two other pairs?

  (mine-group: (B1), not-mine-group: (A1 C1))
+ (mine-group: (B1), not-mine-group: (C1))
= (mine-group: (B1 B1), not-mine-group: (A1 C1 C1))

Aha, there are no contradictions, making this a viable combination. In total, there is one other viable combination for this example:

mine-group: (C1 C1), not-mine-group: (A1 B1)

If one were to plug this input into the code, the output returned would be in this form:

(
	(		; possible configuration 1
		(B1)	; mine group
		(A1 C1)	; not mine group
	)
	(		; possible configuration 2
		(C1)	; mine group
		(A1 B1)	; not mine group
	)
)

As you can see, it’s an ugly parenthetical mess. However its actually very simple: The function returns a list of possible configurations. Within each of these configurations, there are two groups. The first is the ‘mine’ group, and the second is the ‘not mine’ group. Within each of the groups, there is a number of ordered pairs which points to a place on the game board.

And that’s basically it. The game board is stored as a list, so the above example would be stored as: ‘(? ? ? 0 0 1 1 0 0 0 0 0). A function goes through each element in the list and generates the possible configurations for each individual cell, which would look like this:

'(nil nil nil nil
nil ( ((A1) (B1 C1)) ((B1) (A1 C1)) ((C1) (A1 B1)) ) ( ((B1) (C1)) ((C1) (B1)) ) nil
nil nil nil nil)

Phew. Next, a function takes this result, removes the nils, and reduces the list using
the Combine2Possibilities function, which would produce the output listed above.

Despite the output of this function being very ugly, it’s pretty versatile. Using some additional printing code, you can display the output in a number of different ways. In the example code, the original game state is printed first. Following the calculations, a list of possible mine location sets is printed out. But this output is hardly useful, so after that is a list of definite mine positions – positions that appear in every possible mine location set, as well as a list of definite not-mine positions. At the bottom is the most readable of all: the original game state with all definite mines and not-mines added.

Minesweeper Solver
(Note that in the code locations are represented as an ordered pair, not A1, B1, etc,.)

At the bottom is an example of it’s output using the example data provided in the code. ‘n’ means ‘not a mine’ – it’s possible to calculate this value for certain positions (those with no surrounding ‘?’s) but I’ll leave that as an exercise for the reader :)

Board before solution:
        1 ? ? ? ?
        1 ? ? 3 ?
    1 1 2 ? ? ? ?
    1 ? ? ? ? 1 ?
    1 2 ? 3 ? ? ?
      1 ? ? ? ? ?
    1 2 2 1 1 1 1
    1 ? 1
    1 ? 1
Possible mine location sets:
((5 0) (8 0) (7 0) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 0) (7 0) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (7 0) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (7 0) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (7 0) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (7 0) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (8 0) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (8 0) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (8 0) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (8 0) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (6 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (6 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (8 0) (7 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (6 1) (8 0) (7 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (8 0) (7 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (8 0) (7 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (7 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (7 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (8 0) (3 3) (6 3) (5 3) (4 5) (7 5) (3 7))
((5 0) (8 1) (6 1) (8 0) (3 3) (6 4) (5 3) (4 5) (7 5) (3 7))

Definite mine locations:
((3 7) (7 5) (4 5) (5 3) (3 3) (5 0))

Definite not mine locations:
((3 8) (8 5) (6 5) (5 5) (4 4) (4 3) (6 2) (7 2) (8 2) (8 3) (7 4)
 (8 4) (5 1) (5 2))

Board after solution:
        1 X ? ? ?
        1 n ? 3 ?
    1 1 2 n n n n
    1 X n X ? 1 n
    1 2 n 3 ? n n
      1 X n n X n
    1 2 2 1 1 1 1
    1 X 1
    1 n 1

3 comments

Recently, a SecurID came under my acquisition. For those unfamiliar, SecurID is a small device that fits on any key chain and displays a six digit number that changes once per minute. The six digit number it displays is based on a seed number that is created when the device is deployed and known only by the device (hopefully) and the party deploying the technology. The deploying party then keeps a big database of each person’s user name, SecurID serial number, SecurID seed number, and SecurID pin, which can be modified via an 800 number. When you want to authenticate to certain services, you provide your pin number, followed by the currently displayed six digit number on the SecurID. The authenticating party then uses the seed to calculate the number that should be on the SecurID at that time and compares it to the PIN and SecurID number you submit.

By doing this you are (theoretically) proving to the authenticating party that you are who you claim to be with two factors of authentication: something you know (your PIN) and something you have (your SecurID). This makes it more secure than only a single factor of authentication, such as a password. Since the SecurID is physical, a hacker would need to steal or tamper with the device to beat the additional authentication method.

In this case, however, the line between something you have and something you know is, in my opinion, a bit blurry. Because the device holds some information that makes it unique – it’s random seed – one could extract this information from the device where it can be emulated in software. Fortunately for SecurID, it’s never connected to a computer, ensuring that an attacker must have physical access to bypass this security measure. (There is however, the issue of the seed being stored in the authenticating server, which is a potential target of attack)

But once an attacker does get physical access, there is little stopping him, in my opinion, from fraudulently authenticating himself. Let’s say, for example, that an attacker acquires another user’s SecurID and username. If the deploying party requires a four digit PIN then there are 10,000 possible codes that can be entered. Lets assume that the deploying party has only allowed one incorrect login per generation cycle. This means that to brute force the PIN number, the maximum amount of time it would take is 10,000 minutes. 10,000 minutes * 1 hour / 60 minutes = 166.7 hours. 166.7 hours * 1 day / 24 hours = 6.94 days. Which means that at most you would need to wait for a week to successfully brute force a SecurID login, assuming you have the device and username with a one minute code generation interval on the device.

But what if I have to enter a six digit PIN? That’s 1,000,000 possible combinations. 1,000,000 minutes * 1 hour / 60 minutes = 16,666.7 hours. 16,666.7 * 1 day / 24 hours = 694.4 days. Hmm, that’s much better. However, the longer you make the required PIN, the harder time the average user is going to have trying to remember it. It’s also been shown that people remember words better than remember a string of numbers, which is why I think SecurID should use passwords rather than a PIN. However, the more characters that need to be entered during authentication, the more time an average user needs to input this information, so there’s a balance that needs to be achieved. Four digit PINs are good because it’s the same size as a bank PIN, and similar brute force deterrent mechanisms can be used, such as disabling login after n failed attempts.

It’s not that I think SecurID is a bad technology; quite the opposite. Instead, I think that ‘something you have’ is almost invariably ‘something you know’ (whether you know it, or the device does, it’s somewhere). This also goes for the third factor of authentication, which is ‘something you are’. What is a thumb print but information? (And something you are is immutable – if someone makes a copy of your thumb print and masquerades as you, what are you going to do? Get a new thumb print?)

That said, I think SecurID is a great technology with a slim chance of being exploited. RSA did a good job of making it unable to be connected to a computer, which eliminates the possibility of being able to remotely discover the device’s seed number.

3 comments

So I recently finished a two week long program at Dartmouth called SISMAT (Secure Information Systems Mentoring and Training) where I learned about a plethora of computer security related topics. Overall I had a really great time and met some really cool people. Each day was structured with two lectures in the morning and one or two labs in the afternoon. The topics presented included web vulnerabilities, software vulnerabilities, sniffing/network analysis, ethics in computer security, and public key infrastructure. Going in I wasn’t expecting my Linux skills to improve, but they did with all the labs and the RTFM mentality of the instructors (and I mean that in a good way).

Starting tomorrow I begin part two of SISMAT; that is, I start my first day at my internship at Ernst & Young in New York City. I’m both excited and nervous to be working at the Advanced Security Center, although I think most of the nervousness is due to my unfamiliarity with New York city. I am, however, looking forward to learning during the month I will be interning since I have had plenty of experience developing web apps for The College.

No comments