ASIS CTF 2015 Quals - grids

• ASIS CTF
• 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}