The DefCon 22 quals have come and gone, and I was a new participant this year. Thankfully, I didn’t leave with a big fat goose egg on my forehead, but I didn’t do so great either. Most of my teammates answered all the questions before I got anywhere near the 3rd or 4th step of the challenge, and most of the reversing proved to be beyond me.
I did solve one challenge all on my lonesome however. I solved 3DTTT before any of my teammates had done it, which surprised me as I found it relatively simple (and just a matter of prioritization).
The challenge itself consisted of connecting to a server that wanted to play a game of 3D Tic-Tac-Toe. There was about a 3-second time limit on moves, which made it obvious that the play had to be automated. Furthermore, you had to win an unknown number of rounds, and if you ever had -10 wins it disconnected you. So the idea was to 1) Play fast and 2) Play good.
Difficult on the surface, but much easier than you’d expect. Classic Tic-Tac-Toe is what is called a “Solved Game”. A “Solved Game” means that the players can force a pre-determined outcome by making certain moves, regardless of their opponent’s strategy. In classic tic-tac-toe, specifically, it’s possible to force a draw in a EVERY GAME, regardless of which player starts – and if the second player doesn’t make the correct move every turn, it’s a guaranteed win for player 1.
3D tic-tac-toe is a little more difficult, but still within the realms of being solved. Here is an example game board
Top Level ------------- | | | | ------------- | | | | ------------- | | | | ------------- Middle Level ------------- | | | | ------------- | | | | ------------- | | | | ------------- Bottom Level ------------- | | | | ------------- | | | | ------------- | | | | -------------
Now, 3DTT is a little different. It works on points, and each complete line is 1 point. Whoever has the most lines when all boards are filled wins.
So who has the advantage, player 1 or player 2? Well, what’s the most advantageous place on the board?
In normal Tic-Tac-Toe, the center square is the most valuable square, because it can be used to make the most lines (4, two X’s, and 2 +’s). Every other square on the board can only be used to make TWO or THREE lines (Corners- Three, Middles- Two).
This holds for 3DTTT as well!
Corners on the top and bottom levels can be used to make 2 diagonals (1 on the same level, 1 across all 3 levels), 4 straights (2 on each axis, on the same board and across all boards), and 1 completely vertical across all boards. 7 total potential wins. These are Very strong places to hit!
Centers on the Top and Bottom level can be used to complete: 1 vertical, 2 straight on the same level, and 2 straight across all levels. 5 Total potential wins! These are moderate assets, but still quite strong. They actually enable you to set up a constant string of wins, regardless of where you move, so these are really important.
Corners on the center level can be used to make 1 vertical, 2 straights, and 1 diagonal. 4 total potential wins. WEAK place to hit!
Middles on the top and bottom can be used to make 1 vertical, 2 straights on the same level (think T), and 1 straight across all 3 boards. 4 Total potential wins. WEAK!
Middles in the center can only 1 vertical and 2 straight lines. 3 potential wins! WEAK WEAK!
Oh but that leaves one last place we haven’t discussed yet…
The center square on the center board… 1 vertical, 2 straight on-level, 2 diagonal on-level, 4 diagonal all-levels, 4 straight all-levels… This single square enables you to obtain a whopping THIRTEEN POTENTIAL WINS.
So player one has a SERIOUS advantage, because he can immediately REMOVE 13 wins from his opponent’s potential pot, while enabling himself to hit a win every other move (which we will cover shortly).
So cool… move 1: Center Board, Center Square. Check.
move 2: Center square of either the top/bottom board, whichever has not been taken
move 3: (maybe) center square of top/bottom board, if it has not already been taken.
Now what? Well… the 3d nature of the game enables player 1 to have constant check-mate situations. In a single player game, this board is an instant win for the X’s:
Middle Level
-------------
| X | | X |
-------------
| | O | |
-------------
| O | | X |
-------------
No matter WHERE the O’s move next, it’s an instant lose, right? Well, if you own the center square on the center board, and the center square of another board – on your next move, you’ll either you complete an on-level line, or a cross-level line. This is very important early game.
Looking at our list of squares, we see our most powerful spaces are the corners, so we prioritize those for the next set of moves
move: corner a
move: corner opposite of a on same board OR corner on opposite layer (1->3 or 3->1) and opposite end. INSTANT POINT!
We do this until the corners are gone, and move on to the middles!
You can also see that middles on the top and bottom are as powerful as corners in the center board, so we can simplify our algorithm a little by just playing every possible corner first. Not completely optimal, but way easier to implement.
Basically, you repeat this exact same strategy for the middles, and when you’re finished, you’ve completed the entire game and start the next one.
At this point, we COULD add some logic to prioritize wins or blocking your opponent, but the fact is, you’ve already removed enough potential point’s from your opponent (the defcon computer) to secure victory about 70-75% of the time. So at this point… just let the thing run and start working on the next challenge! Woo!
The following code managed to win 50 games in a matter of about 5 minutes. Granted, i was running on a university server with a very strong business connection, so take that for what it is.
Also I got lazy with my “prioritized wins” algorithms, so the corners and middles don’t play EXACTLY as mentioned above, but close enough. Still enough to get the flag very very quickly.
GO GO SIMPLE COMBINATIONS/PERMUTATIONS!
I explained here that the most optimal squares to pick were based on the number of potential wins they unlocked, and that’s all very much in the spirit of tic-tac-toe… but how does it apply to netsec/hacking/exploitation at all? At first glance, this is just a silly game of competing algorithms.
Well, think about all the protocols we use on a day-to-day basis, and how many rules they run by. Race conditions are a good example. If you can get your computer to return spoofed DNS responses faster than 8.8.8.8, you’re playing better and faster than your opponent.
But do you always have to play perfect? No. Personally I would have liked to see the defcon computer detect perfect players and refuse to play against them, forcing them to slow down/run imperfect games in order to bypass the security system.
If you’re loud about your attack, you get caught. If you make yourself look normal, you blend in.
Just some food for thought.