ASIS CTF Quals 2015 - Grids (programming 300) Writeup

Hint:

In each stage send the maximun [sic] size of area that can be covered by given points as a vertex of polygon in 2D.

nc 217.218.48.84 12433

When we connect to the server, we're given the following instructions:

In each stage send the maximun size of area that can be covered by given points as a vertex of polygon in 2D.
Are you ready for this challenge?

Sending the string "yes", we're told "OK, OK, lets start" and after a pause, we're given our first set of points, formatted as so:

The points:
[[8, 1], [1, 5], [7, 6]]
What's the area?

This turns out to be a straight-forward programming challenge. We need two pieces of background information:

  1. Given a bunch of 2D points, the polygon with some set of those points as vertices that maximizes area will be the Convex Hull of the points.

  2. The area of a polygon with n vertices (x[i], y[i]) can be easily calculated as detailed here by:

    0.5 * Σ (x[i-1] + x[i]) * (y[i-1] - y[i])   (indices mod n)
    

My solver implementation was written in Perl, using Math::ConvexHull to calculate the relevant subset of points:

solve.pl

 1 #!/usr/bin/perl
 2 
 3 use strict;
 4 use warnings;
 5 use diagnostics;
 6 use feature 'say';
 7 use TcpSocket;
 8 use Data::Hexify;
 9 use Math::ConvexHull qw'convex_hull';
10 use constant {
11      X => 0,
12      Y => 1
13 };
14 $|=1;
15 
16 my $host = '217.218.48.84';
17 my $port = 12433;
18 
19 my $response;
20 my $sock = TcpSocket->new($host, $port);
21 my $p;
22 
23 $sock->tryread();
24 $sock->tryread();
25 say $sock "yes";
26 
27 while(1)
28 {
29      $response = '';
30      my $last = '';
31      while($response !~ /\]\]/)
32      {
33              my $foo;
34              my $ret = $sock->sysread($foo, 2000);
35              $response .= $foo;
36              if($response ne $last)
37              {
38                      say "intermediate:";
39                      say Hexify($response);
40                      $last = $response;
41                      exit if($response =~ /answer rapidly/);
42              }
43      }
44      say Hexify($response);
45      $response =~ s/^[^\[]*\[//;
46      $response =~ s/\][^\]]*$//;
47      say $response;
48      my @points;
49      while($response =~ /\[(\d+), (\d+)\]/g)
50      {
51              push @points, [$1, $2];
52      }
53      say "Points:";
54      say "  $_->[0], $_->[1]" foreach (@points);
55 
56      my $convex_hull = convex_hull(\@points);
57      say "Convex Hull points:";
58      say "  $_->[0], $_->[1]" foreach (@$convex_hull);
59      my $area = 0;
60      foreach my $i (0 .. $#$convex_hull)
61      {
62              $area += ($convex_hull->[$i]->[X] + $convex_hull->[$i-1]->[X]) *
63                      ($convex_hull->[$i]->[Y] - $convex_hull->[$i-1]->[Y]);
64      }
65      $area /= 2.0;
66      $area = sprintf("%.1f", $area);
67      say "Area: $area";
68 
69      say $sock $area;
70 
71      $response = $sock->tryread(0.01);
72      say Hexify($response);
73 }

The biggest annoyance and waste of time for me in solving this challenge is that even though the points are given as whole numbers, and nothing hints at it at all, the server would not accept whole numbers as correct. For instance, if the area was 2, the answer of "2" would be treated as incorrect but the answer "2.0" was accepted. This wasted a significant amount of time for me and it was only after I noticed the pattern did I add the sprintf on line 66 and start submitting answers that were accepted.

There may still be a minor bug in my code or in Math::ConvexHull because it would occasionally submit an answer that was rejected, but it was relatively rare. Despite the ~15 minute runtime, the incorrect answers were just a minor inconvenience and restarting the program was faster than hunting down a subtle bug.

After solving 99 puzzles, the program spit out:

0000: 47 72 65 61 74 20 3a 29 20 0a 43 6f 6e 67 72 61  Great :) .Congra
0010: 74 7a 21 20 41 53 49 53 7b 66 33 61 38 33 36 39  tz! ASIS{f3a8369
0020: 66 34 31 39 34 63 35 65 34 34 63 30 33 65 35 66  f4194c5e44c03e5f
0030: 63 65 66 62 38 64 64 66 36 7d 0a                 cefb8ddf6}.

The final flag being: ASIS{f3a8369f4194c5e44c03e5fcefb8ddf6}

Posted on May 11, 2015, 9:27 p.m. by tecknicaltom