DEF CON 22 CTF Quals: 3dttt

Unlike most of the challenges in DC22 quals, this one required no binary exploitation, no reversing, just writing a little code. You needed to play 3-D Tic Tac Toe, and you needed to play fast. Unfortunately, I didn’t record the sessions, so I don’t have the example output.

Basically, you just received an ASCII representation of each of the 3 boards making up the 3d-tic-tac-toe environment, and were prompted to provide x,y,z coordinates for your next move. However, you had only a very short period of time (fractions of a second) to send your move, so playing by hand was impossible. The winner of each board was the player with the most rows won, and it did go to the full 27 moves each time. Also, it’s important to note that the player always goes first, and that you have to win 50 rounds in order to receive the flag.

I chose this basic algorithm:

  1. On the first move, play in the very center of the boards (1,1,1)
  2. For each subsequent move, consider each available position.
    1. Consider each row that the position sits on.
    2. If the row has both X and O on it, award 0 – the row is a lost cause.
    3. If playing would win that row for us, or block a win for our opponent (they have 2/3), award 3 points.
    4. If we already have something on that row, or they already have something on that row, award 1 point. We’re either making progress or blocking.
    5. Otherwise, no points.
  3. Sum the row points for each position, and play in the highest scoring position.

I had no idea if this algorithm would work, but it was actually successful resulting in the flag on the first try.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#!python
import re
import socket

REMOTE = ('3dttt_87277cd86e7cc53d2671888c417f62aa.2014.shallweplayaga.me', 1234)

class TTT(object):

  def __init__(self, host, port):
    self.s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    self.s.connect((host, port))
    self.state = [[[' ', ' ', ' '] for i in xrange(3)] for k in xrange(3)]
    self._buf = ''
    self._moves = 0

    self._read_intro()
    self._read_state()
    self._print_state()

  def _read_intro(self):
    buf = ''
    while 'Play well and play fast....' not in buf:
      buf += self.s.recv(1024)
    self._buf = buf.split('and play fast....')[1]

  def _read_state(self):
    buf = self._buf
    while True:
      if '\n' not in buf:
        buf += self.s.recv(2048)
      line, buf = buf.split('\n', 1)
      m = (re.match(' x.*z=([0-2])', line) or 
          re.match('Choose .* x.*z=([0-2])', line))
      if m:
        z = int(m.group(1))
        continue
      m = re.match('([0-2])  (.) \| (.) \| (.)', line)
      if m:
        y = int(m.group(1))
        for x in xrange(3):
          self.state[z][y][x] = m.group(x+2)

        if y == 2 and z == 2:
          break

    self._buf = buf

  def _send_move(self, x, y, z):
    self.s.send('%d,%d,%d\n' % (x,y,z))

  def _print_state(self):
    print '\nMove: %d' % self._moves
    for board in self.state:
      print '[[' + ']\n ['.join(','.join(c for c in r) for r in board) + ']]'

  @staticmethod
  def _score_row(*row):
    x = 0
    o = 0
    for p in row:
      x += 1 if p == 'X' else 0
      o += 1 if p == 'O' else 0
    if x+o == 3 or (x and o):
      # All 3 filled or lost cause, we're fucked
      return 0
    if x == 2 or o == 2:
      # Either blocking or winning a row
      return 3
    if x or o:
      return 1
    # Empty row
    return 0

  @staticmethod
  def _find_diagonals(x, y, z):
    """This is terrible, but works."""
    # Diagonals of 2 degrees of freedom
    if x == y:
      yield ((0, 0, z), (1, 1, z), (2, 2, z))
    if x+y == 2:
      yield ((0, 2, z), (1, 1, z), (2, 0, z))
    if x == z:
      yield ((0, y, 0), (1, y, 1), (2, y, 2))
    if x+z == 2:
      yield ((0, y, 2), (1, y, 1), (2, y, 0))
    if y == z:
      yield ((x, 0, 0), (x, 1, 1), (x, 2, 2))
    if y+z == 2:
      yield ((x, 0, 2), (x, 1, 1), (x, 2, 0))
    # Now the 4 big diagonals
    if x == y == z:
      yield ((0, 0, 0), (1, 1, 1), (2, 2, 2))
    for dia in [
        ((2, 0, 0), (1, 1, 1), (0, 2, 2)),
        ((2, 2, 0), (1, 1, 1), (0, 0, 2)),
        ((0, 2, 0), (1, 1, 1), (2, 0, 2))]:
      if (x, y, z) in dia:
        yield dia

  def _score_move(self, x, y, z):
    if self.state[z][y][x] != ' ':
      # Not a possible move
      return -1
    # Straight rows
    score = self._score_row(
        self.state[z][y][0],
        self.state[z][y][1],
        self.state[z][y][2])
    score += self._score_row(
        self.state[z][0][x],
        self.state[z][1][x],
        self.state[z][2][x])
    score += self._score_row(
        self.state[0][y][x],
        self.state[1][y][x],
        self.state[2][y][x])
    # Diagonals
    for d in self._find_diagonals(x, y, z):
      score += self._score_row(
          self.state[d[0][2]][d[0][1]][d[0][0]],
          self.state[d[1][2]][d[1][1]][d[1][0]],
          self.state[d[2][2]][d[2][1]][d[2][0]])
    return score

  def _optimal_move(self):
    # Initial move, go for center
    if self._moves == 0:
      return (1, 1, 1)
    # Score each position
    bestpos = None
    max_score = -1
    for x in xrange(3):
      for y in xrange(3):
        for z in xrange(3):
          score = self._score_move(x, y, z)
          if score > max_score:
            max_score = score
            bestpos = (x, y, z)
    print bestpos, 'score:', max_score
    return bestpos

  def move(self):
    where = self._optimal_move()
    if where is None:
      m = re.search('You\'ve won [0-9]+ rounds', self._buf)
      if m:
        print m.group(0)
      self._moves = 0
    else:
      self._send_move(*where)
      self._moves += 1
    self._read_state()
    self._print_state()
    return True


if __name__ == '__main__':
  ttt = TTT(REMOTE[0], REMOTE[1])
  while ttt.move():
    continue
  print ttt._buf
  print ttt.s.recv(1024)