ASIS CTF 2015 Quals -- grids
Post
Cancel

# 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.

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 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}`