CSAW’18 CTF Qualification: Take an L

Détails du challenge

Event	Challenge	Category	Points	Solves
CSAW’18 CTF Qualification	Take an L	Misc (Prog)	200	192

Téléchargement : description.pdf - md5: 79b489dcacb5b0002ed34a270bdfe184

Description

Fill the grid with L’s but avoid the marked spot for the W

nc misc.chal.csaw.io 9000

The origin is at (0,0) on the top left

TL;DR

Il s’agissait d’un challenge de programmation qui ressemblait à un puzzle de polyominos. Pour résoudre le challenge, j’ai trouvé un algorithme récursif pour le problème donné : https://www.geeksforgeeks.org/divide-and-conquer-set-6-tiling-problem/

Méthodologie

Formuler comme un problème algorithmique

La première chose à faire était de lire la description et de réfléchir au problème mathématique/de programmation que nous avions. En lançant le challenge, nous obtenons ce qui suit :

nc misc.chal.csaw.io 9000

each L shaped block should be sent in its 
own line in a comma separated list
eg: (a,b),(a,c),(d,c)

grid dimensions 64x64
marked block: (18, 3)

J’ai fait quelques recherches sur les « puzzles » comme Tetris et j’ai trouvé la page wikipedia « polyomino ». Nos polyominos étaient des « trominos », j’ai décidé de chercher un solveur de polyominos/trominos en ligne.

Geek for Geek

Comme d’habitude avec les problèmes algorithmiques, j’ai consulté le site « GeeksForGeeks ». Avec une petite recherche sur google, j’ai trouvé exactement ce dont j’avais besoin : un solveur de L-tromino pour une grille donnée avec une case « noire » (remplie).

Explication de l’algorithme récursif

L’algorithme que j’ai décidé d’utiliser était récursif. L’algorithme exécute le processus suivant : on place un « L » (L-tromino) au milieu de la grille, puis on divise la grille en sous-grilles et on effectue le même processus pour chaque sous-grille. La fonction récursive s’arrête lorsque la grille a la même taille que notre « L » (2*2). Pour remplir la grille, la case manquante de notre « L » doit être orientée dans la direction de la case occupée de la grille.

Voici une représentation des 2 premières étapes pour une grille 8*8 :

Étape 1 :

Étape 2 :

Code pour une grille 64*64

Comme 64 est un multiple de 4, nous pouvons utiliser notre algorithme. J’ai décidé de l’implémenter en python, voici mon code (pas le meilleur que j’ai écrit…) :

# -*- coding:utf-8 -*-
from pwn import *
 
HOST = "misc.chal.csaw.io"
PORT = 9000

r = remote(HOST, PORT)

def send(c):
    """ Send new 'L' to server """
    print(c)
    r.sendline(c)


rec =  r.recvuntil("marked block: ")
print(rec)
black = eval(r.recvuntil("\n").strip())
print("Black cell: "+str(black))

n = 64 # Array Size
a = [[' ' for x in range(n)] for y in range(n)] # Init empty array
a[black[1]][black[0]] = "@" # Black case (filled one) (given when started)


def pgrille():
    """ Save current Grid to logs """
    out = ""
    out += "-"*n
    out += "\n"
    for l in a:
        out += str(''.join([x for x in l]))+"\n"
    out += "-"*n
    with open("logs","a+") as fi:
        fi.write(out+"\n\n\n")


def getBlack(a,x_start,y_start,x_end,y_end):
    """ Get position of "black" square of array / sub array """
    for j in range(y_start,y_end+1):
        for i in range(x_start,x_end+1):
            if a[j][i] == "o" or a[j][i] == "@":
                return i,j
    return None,None # Should not happen


def Tile(a,x_start,y_start,x_end,y_end):
    """ Recursive function, put an L in the middle and act recursivly.
    'L' are represented with 3*'o'. """
    xcenter_left = x_start+((x_end-x_start)/2)
    xcenter_right = xcenter_left+1
    ycenter_top = y_start+((y_end-y_start)/2)
    ycenter_bottom = ycenter_top+1
    
    xBlack,yBlack = getBlack(a,x_start,y_start,x_end,y_end)
    
    # Define "L" direction/orientation and send new triangle
    if xBlack <= xcenter_left: # Black cell on the left
        if yBlack <= ycenter_top: # Black cell on the top
            a[ycenter_top][xcenter_right] = "o"
            a[ycenter_bottom][xcenter_right] = "o"
            a[ycenter_bottom][xcenter_left] = "o"
            send("("+str(xcenter_right)+","+str(ycenter_top)+"),("+str(xcenter_right)+","+str(ycenter_bottom)+"),("+str(xcenter_left)+","+str(ycenter_bottom)+")")
        else: # Black cell on the bottom
            a[ycenter_top][xcenter_left] = "o"
            a[ycenter_top][xcenter_right] = "o"
            a[ycenter_bottom][xcenter_right] = "o"
            send("("+str(xcenter_left)+","+str(ycenter_top)+"),("+str(xcenter_right)+","+str(ycenter_top)+"),("+str(xcenter_right)+","+str(ycenter_bottom)+")")
    else: # Black cell on the right
        if yBlack <= ycenter_top: # Black cell on the top
            a[ycenter_top][xcenter_left] = "o"
            a[ycenter_bottom][xcenter_left] = "o"
            a[ycenter_bottom][xcenter_right] = "o"
            send("("+str(xcenter_left)+","+str(ycenter_top)+"),("+str(xcenter_left)+","+str(ycenter_bottom)+"),("+str(xcenter_right)+","+str(ycenter_bottom)+")")
        else: # Black cell is on the bottom
            a[ycenter_bottom][xcenter_left] = "o"
            a[ycenter_top][xcenter_left] = "o"
            a[ycenter_top][xcenter_right] = "o"
            send("("+str(xcenter_left)+","+str(ycenter_bottom)+"),("+str(xcenter_left)+","+str(ycenter_top)+"),("+str(xcenter_right)+","+str(ycenter_top)+")")
    
    pgrille() # Print in logs
    
    if abs(x_end-x_start) > 1: # If grid is big enough, go recursiv
        Tile(a,x_start,y_start,xcenter_left,ycenter_top)
        Tile(a,xcenter_right,y_start,x_end,ycenter_top)
        Tile(a,x_start,ycenter_bottom,xcenter_left,y_end)
        Tile(a,xcenter_right,ycenter_bottom,x_end,y_end)
    
Tile(a,0,0,len(a[0])-1,len(a)-1) # Start on full array
    
r.interactive() # Get shell

Flag

flag{m@n_that_was_sup3r_hard_i_sh0uld_have_just_taken_the_L}

Zeecka