Tous les chemins mènent au flag

BreizhCTF 2019 - Prog (150 pts).

BreizhCTF 2019: Tous les chemins mènent au flag

Challenge details

Event	Challenge	Category	Points	Solves
BreizhCTF 2019	Tous les chemins mènent au flag	Programming	150	???

TL;DR

We had to win 500 game of “TicTacToe” playing with a bot. I wrote a python script but some teams managed to beat the bot by themself !

Methodology

First game

To understand the challenge I decided to run a netcat on the given ip/port.

nc ctf.bzh 42000

Turn number 1
Where would you like to place S (1-9):1

Humans: 0    Machines: 0
The board look like this:

  S  |     |     
================
     |     |     
================
     |     |     

Turn number 2

Humans: 0    Machines: 0
The board look like this:

  S  |     |     
================
  K  |     |     
================
     |     |     

Turn number 3
Where would you like to place S (1-9):

[SNIP]
Where would you like to place S (1-9):3

Humans: 4    Machines: 0
The board look like this:

  S  |  S  |  S  
================
     |  K  |     
================
     |     |  K  

Turn number 6

Humans: 4    Machines: 0
The board look like this:

  S  |  S  |  S  
================
     |  K  |  K  
================
     |     |  K  

HUMANS WIN!

Humans: 5    Machines: 0
The board look like this:

     |     |     
================
     |     |     
================
     |     |     

Turn number 1
Where would you like to place S (1-9):

[SNIP]

Scripting

There were 2 problems to solve. The first one was the parsing of the game and I decided to use pwn module for this. The second problem was the algorithm to choose the best movement, and I decided to use TicTacToe Master which implement Minimax algorithm. (Note, I’ve been looking for “Best Move TicTacToe python” on google to find the script).

I had to fix part of the given script due to the implementation with “S” and “K” in our game instead of “X” and “O” in the script. Here is the modified script (md5sum : dcfe7ef172cc3a708f968a9c830d9708)

And finaly here is my script using the getAIMove function of TicTacToe Master:

import TicTacToeMaster as ttt
from pwn import *

def getBestMove(board):
    return int(ttt.getAIMove(board, "S", "S")[0])

def extractMatrice(s):  # Convert board with ====|==== to list [1,2,3,4,5,6,7,8,9]
    s = s.split("\n")
    l1 = s[2].strip().replace(" ","").split("|")
    l2 = s[4].strip().replace(" ","").split("|")
    l3 = s[6].strip().replace(" ","").split("|")
    return  l1+l2+l3

HOST = "ctf.bzh"
PORT = 42000

r = remote(HOST, PORT)

def solveGame():
    bestMove = "1"

    while 1:
        rec =  r.recvuntil("(1-9)? ")  # Do the first movement
        print("[PLAY]  "+bestMove)
        r.sendline(bestMove)

        r.recvuntil("The board look like this:") # player
        x = r.recvuntil("The board look like this:") # bot
        if "HUMANS WIN!" in x:
            print(x)
            return
        
        rec = r.recvuntil("Turn number")
        #print(rec)
        m = extractMatrice(rec)
        #print(m)
        bestMove = str(getBestMove(m)+1)  # +1 due to list index
        

for i in range(499):
    solveGame()
r.interactive()

Once run, the script stop at the last game and let us play the final game 8).

Flag

breizhctf{???}

Zeecka