BreizhCTF 2019: Tous les chemins mènent au flag

Détails du challenge

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

TL;DR

Il fallait gagner 500 parties de « TicTacToe » en jouant contre un bot. J’ai écrit un script python mais certaines équipes ont réussi à battre le bot elles-mêmes !

Méthodologie

Première partie

Pour comprendre le challenge, j’ai décidé de lancer un netcat sur l’ip/port fourni.

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

Il y avait 2 problèmes à résoudre. Le premier était le parsing de la partie et j’ai décidé d’utiliser le module pwn pour cela. Le second problème était l’algorithme pour choisir le meilleur coup, et j’ai décidé d’utiliser TicTacToe Master qui implémente l’algorithme Minimax. (Note : je cherchais « Best Move TicTacToe python » sur google pour trouver le script).

J’ai dû corriger une partie du script fourni à cause de l’implémentation avec « S » et « K » dans notre partie au lieu de « X » et « O » dans le script. Voici le script modifié (md5sum : dcfe7ef172cc3a708f968a9c830d9708)

Et enfin voici mon script utilisant la fonction getAIMove de 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()

Une fois lancé, le script s’arrête à la dernière partie et nous laisse jouer la partie finale 8).

Flag

breizhctf{???}

Zeecka