CSAW'18 CTF Qualification: Take an L
Challenge details
| Event | Challenge | Category | Points | Solves |
|---|---|---|---|---|
| CSAW'18 CTF Qualification | Take an L | Misc (Prog) | 200 | 192 |
Download:
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
This was a programming challenge looking like polyominos puzzle. To solve the challenge, I found a recursiv algorithm for the given problem: https://www.geeksforgeeks.org/divide-and-conquer-set-6-tiling-problem/
Methology
Explain as an algorithm problem
First thing to do was reading the description an think about the mathematic/programming problem we had. By running the challeng we got the following:
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)
I made few search about “puzzle” such as Tetris I found the “polyomino” wikipedia page. Our polyominos were “trominos”, I decided to search for a polyomino/tromino solver online.
Geek for Geek
As usual with algorithmic problems, I looked at the website “GeeksForGeeks”. With a litle research on google, I found exactly what I needed: a L-tromino solver for a given grid with a “black” (filled) cell.
Explanation of recursiv algorithm
The algorithm I decided to used was recursiv. The algorithm execute the following process: we put an “L” (L-tromino) on the middle of the grid, then we split the grid into subgrid and do the same process for each subgrid. The recursiv function stop when the grid is same size as our “L” (2*2). To fulfill the grid, the missing square of our “L” must be oriented in the direction of the occupied cell of the grid.
Here are a representation of the 2 firsts step for a 8*8 grid:
Step 1:
Step 2:
Code for a 64*64 grid
As 64 is a multiple of 4, we can use our algorithm. I decided to implement it in python, here is my code (not the best one I wrote…):
# -*- 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}