Лаборатория RuCTF 2013 Quals - PPC [200]

, 16 марта 2013

In this task we were given a hostname and a port. The connection using netcat shows us a picture of a ship in ASCII art, two lines: “10x10x10” and “<x>:<y>:<z>\n”, and some lists of triples of length 4, 3, 2 and 1. This all is an obvious invitation to play a three-dimensional version of the Sea Battle game with a robot on the other side of the wire.

The Unknown Information

As in the prevailing amount of CTF tasks there are a lot of suggesting one should make to achieve the success. The main questions in this particular challenge are the following:

  • What do the lists at the beginning of the connection mean?
  • How are you supposed to make a move?
  • How will you understand if you hit a ship or even sank it?
  • How are you supposed to respond upon the moves of the robot?
  • How will you understand that the game is over?

Basically, there are three assumptions about the lists. Firstly, they could be an example of how one should organize the ships. However, this is unlikely due to the random changes made in numbers upon every subsequent connection. Secondly, the lists could reveal the ship placement of the robot, but this makes absolutely no sense to the game. Finally, one can conclude that the authors of the game have saved us from troubles with generating the correct locations of the ships and are providing us with one. This seems legit providing that the robot is not cheating.

Making a move is the most simple part. The line “<x>:<y>:<z>\n” in the preamble of the connections reveals the format: one should use coordinates of the hit separated with colons and terminate them with a newline.

To discover the responses on successful actions one should initiate several games with simple algorithm of hitting one cell of the battlefield. This analysis shows that the robot sends “Hit” when you hit a ship and “Hit and Die” if your hit has also sunk the ship. There is one extra type of responses, “Incorrect move”, which appears when you send a string of wrong format or hit the same cell twice.

Regarding your responses to the robot, you should not worry. The robot, knowing your ships placement, uses this information to make the decisions about the statuses of his actions on his own. You can tell that it does it seeing lines with several hits separated by semicolons, all of which except the last one are on your ships. Of course, the robot uses the knowledge about your ships dispositions only to handle the unnecessary routines for you and uses no opportunity to cheat. How nice of him!

The last question is about the end of the game. Actually, you can calculate the end by your own counting the successful hits, but the robot tells “You win! Play again” upon your victory in a match. The new game starts then immediately within the same connection. It turns out, one should win ten times in a row to be given a flag and score up.

The Algorithm

The main issue in this task is to implement an algorithm which will beat the robot ten times in a row. Obviously, there are numerous strategies one can think of, but the robot seems to play randomly, and any reasonable heuristic will do the job. Here is the algorithm of SiBears team described.

Firstly, we try to hit all the cells in some fixed order, i.e. starting with the first cell of the first row of the first plane of the game field and finishing with the last cell of the last row of the last plane. It reveals that this simple strategy is sufficient to encounter first ship part of the robot soon enough.

Secondly, when we have hit—and have not sunk—a new ship for the first time, we try to hit all the cells adjacent to the first one in a fixed order. This is done to continue hitting the same ship. On the second successful hit of the ship—which is still not the one to sink it—we start to hit the cells at the beginning and the end of the shaping ship. The same strategy applies when there are three successful hits of the same ship without it being sunk.

Finally, when the ship is sunk, the list of successfully hit cells is cleared, and the strategy returns to walking on the battlefield in the fixed order.

The program implementing the strategy is written in Python programming language and is attached below for your consideration.

#!/usr/bin/env python2.7

import sys
import socket
import os
import random
import time
import copy
import re

class Agent(object):

    def __init__(self, host, port, debug = True):
        self.s = None
        self.host = host
        self.port = port
        self.debug = debug
        self.answers = []

    def start(self):
        self.s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
        self.s.connect((self.host, self.port))

    def run(self, command, args):
        self.answers = []
        write_index = 0
        for c in command:
            if c == "r":
            elif c == "w":
                write_index += 1

    def finish(self):

    def read(self):
        result = self.s.recv(1000)
        if self.debug:
            print "->", result
        return result

    def write(self, what):
        if self.debug:
            print "<-", what

def ship_str(ship):
    return "{ " + " ; ".join([":".join(map(str, cell)) for cell in ship]) + " }"

def place_ship(cursor, size):
    def ship_from_cursor(cursor, size):
        ship = []
        for i in xrange(size):
            cell = cursor[:]
            cell[0] += i
        return ship

    if cursor[0] + size < 10:
        return ship_from_cursor(cursor, size), [cursor[0] + size, cursor[1], cursor[2]]
    if cursor[1] < 9:
        return place_ship([0, cursor[1] + 1, cursor[2]], size)
    return place_ship([0, 0, cursor[2] + 1], size)

class MyCube(object):

    class Ship(object):

        def __init__(self, cells):
            self.cells = dict()
            for cell in cells:
                self.cells[cell] = False

        def hit(self, cell):
            self.cells[cell] = True

        def is_dead(self):
            for dead in self.cells.itervalues():
                if not dead:
                    return False
            return True

    def __init__(self, ships):
        self.ship_by_cell = dict()
        for ship in ships:
            s = Ship(ship)
            for cell in ship:
                self.ship_by_cell[cell] = s

class Bot(object):

    dxs = [0, -1, 0, 0, 1, 0]
    dys = [1, 0, 0, 0, 0, -1]
    dzs = [0, 0, -1, 1, 0, 0]

    def check_coord(nx, ny, nz):
        return 0 <= nx and nx < 10 and 0 <= ny and ny < 10 and 0 <= nz and nz < 10

    def __init__(self):
        self.cube = [[[0 for x in xrange(10)] for y in xrange(10)] for z in xrange(10)]
        self.success_series = []
        self.cursor = [0, 0, 0]

    def move(self, cell, result):
        self.cube[cell[0]][cell[1]][cell[2]] = 1
        if result == "Hit":
            # print result
        elif result == "Hit and Die":
            # print result
            for prev in self.success_series:
                x = prev[0]
                y = prev[1]
                z = prev[2]
                for dx in Bot.dxs:
                    for dy in Bot.dys:
                        for dz in Bot.dzs:
                            nx = x + dx
                            ny = y + dy
                            nz = z + dz
                            if Bot.check_coord(nx, ny, nz):
                                self.cube[nx][ny][nz] = 1
            self.success_series = []

    def get_move(self):
        if len(self.success_series) == 1:
            # print "providing a move with one previous sucess: " + str(self.success_series[0])
            # print "Bot.dxs = " + str(Bot.dxs)
            # print "Bot.dys = " + str(Bot.dys)
            # print "Bot.dzs = " + str(Bot.dzs)
            x = self.success_series[0][0]
            y = self.success_series[0][1]
            z = self.success_series[0][2]
            for dx in Bot.dxs:
                for dy in Bot.dys:
                    for dz in Bot.dzs:
                        nx = x + dx
                        ny = y + dy
                        nz = z + dz
                        # print "    checking [%d, %d, %d] (%d, %d, %d + %d, %d, %d)" % (nx, ny, nz, x, y, z, dx, dy, dz)
                        # print "    (%s, %s, %s + %s, %s, %s)" % tuple(map(str, map(type, [x, y, z, dx, dy, dz])))
                        if Bot.check_coord(nx, ny, nz) and self.cube[nx][ny][nz] == 0:
                            return [nx, ny, nz]
        elif len(self.success_series) > 1:
            change_index = -1
            same_index_1 = -1
            same_index_2 = -1
            if self.success_series[0][0] != self.success_series[1][0]:
                change_index = 0
                same_index_1 = 1
                same_index_2 = 2
            if self.success_series[0][1] != self.success_series[1][1]:
                change_index = 1
                same_index_1 = 0
                same_index_2 = 2
            if self.success_series[0][2] != self.success_series[1][2]:
                change_index = 2
                same_index_1 = 0
                same_index_2 = 1
            result = copy.copy(self.success_series[0])
            index = self.success_series[0][change_index]
            while index >= 0 and Bot.check_coord(*result) and self.cube[result[0]][result[1]][result[2]]:
                index -= 1
                result[change_index] = index
                # print "    checking " + str(result)
            if index >= 0:
                return result
            # print "    continue checking..."
            index = self.success_series[0][change_index]
            result[change_index] = index
            while index < 10 and Bot.check_coord(*result) and self.cube[result[0]][result[1]][result[2]]:
                index += 1
                result[change_index] = index
                # print "    checking " + str(result)
            return result
        while self.cube[self.cursor[0]][self.cursor[1]][self.cursor[2]]:
            if self.cursor[0] < 9:
                self.cursor[0] += 1
            elif self.cursor[1] < 9:
                self.cursor[0] = 0
                self.cursor[1] += 1
                self.cursor[0] = 0
                self.cursor[1] = 0
                self.cursor[2] += 1
        return self.cursor[:]

if __name__ == "__main__":

    # Hit
    # Hit and Die

    # ships_req = [[5, 4], [10, 3], [15, 2], [20, 1]]
    # cursor = [0, 0, 0]
    # ships = []
    # for ship_req in ships_req:
    #     for n in xrange(ship_req[0]):
    #         ship, cursor = place_ship(cursor, ship_req[1])
    #         ships.append(ship)
    # ships = "\n".join(map(ship_str, ships)) + "\n"

    a = Agent("fight.quals.ructf.org", 10000, False)

    a.run("r", [])
    counter = 1
    while True:
        bot = Bot()
        a.run("r", [])
        result = ""
        while result != "You win! Play again":
            move = bot.get_move()
            a.run("wr", [":".join(map(str, move)) + "\n"])
            result = a.answers[-1].strip()
            bot.move(move, result)
            if not re.search(r"[0-9]:[0-9]:[0-9]", result):
                print "Game %d: %s" % (counter, result)
        counter += 1


The Technical Issues

The biggest issue in this challenge is the small timeout value set on the side of the robot. If you are lazy with sending the next move, it hangs the connection with the message “Timeout”. While it is nearly impossible to affect the quality of your connection, you can still optimize the algorithm to lessen one of the summands of the overall delay at least. We at SiBears have performed a couple of improvements to the code, after which it was able to beat the robot ten times in a row. Hurray!