ASIS CTF 2015 Quals -- grids

Category: Programming
Points: 300

In each stage send the maximun size of area that can be covered by given points as a vertex of polygon in 2D.
nc 217.218.48.84 12433
mirror 1 : nc 217.218.48.84 12432
mirror 2 : nc 217.218.48.84 12434
mirror 2 : nc 217.218.48.84 12429

Took me a while to figure out that the challenge was asking us to solve a Convex Hull problem.

The service provide us a list of vertices (2-D). We’ll have to find the vertices that can form a convex hull and calculate its size of area. Fortunately, there’s a python library call scipy, which can be used to find a convex hull by giving an array of vertices. After we find all the vertices, we can simply calculate the size of area by using determinant.

from pwn import *
import ast
import sys
import numpy as np
from scipy.spatial import ConvexHull
from numpy import array

LOG = False

def my_recvuntil(s, delim):
    res = ""
    while delim not in res:
        c = s.recv(1)
        sys.stdout.write(c)
        res += c
    if LOG:
        print res
    return res

def cal_area(points):
    pairs = zip(points, points[1:]+points[0:1])
    return float(sum(x1*y2 - y1*x2 for (x1, y1), (x2, y2) in pairs)) / 2.0

HOST = "217.218.48.84"
PORT = 12434

r = remote(HOST, PORT)

r.recvuntil("challenge?\n")
r.send("yes\n")

cnt = 0
while True:
    log.info("Round: "+str(cnt))
    cnt += 1
    ps = log.progress("getting points from server...")
    s = my_recvuntil(r, "area? ")

    # parse the vertex list
    list_str = s[s.index("[["):s.index("What's"):].strip()
    real_list = ast.literal_eval(list_str)
    
    # get the convex hull point
    points = array(real_list)
    hull = ConvexHull(points)
    hull_points = [ real_list[c] for c in hull.vertices]

    final = cal_area(hull_points)
    log.success("answer: " + str(final))
    r.send(str(final)+"\n")
    print r.recv(1024)

r.interactive()

After solving 99 problems, we got the flag: ASIS{f3a8369f4194c5e44c03e5fcefb8ddf6}