Ark's Blog

数学とか競プロとかCTFとか参加記とか備忘録とか

ようこそ

CTFZone 2019 quals write-up -Labyrinth-

CTFZone 2019 qualsにチーム「./Vespiary」として参加しました。結果はScore 714で41位。

ctf.bi.zone

隙間時間にやっていたというのもあるけど、全然貢献できなかったのでくやしい。

1問(+α)解いたので、自分が解いた問題のwrite-upをかきます。

Welcome to CTFZone!

問題文にフラグが書いてあります。いつもの

ctfzone{2019}

Labyrinth

単純なオンライン迷路探索問題... と思いきや色々罠あり。

  • 迷路はグリッド上
  • #:壁
  • :通行可能なマス
  • @:現在位置
  • E:ゴール(ただし、迷路終盤までゴールの記号がなにかは不明)

基本的な方針は、迷路のマップ情報を補完しながらDFSで迷路探索を行います。

ソースコード

import socket
import sys

sys.setrecursionlimit(10000)

client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
client.connect(("ppc-labyrinth.ctfz.one", 4340))

buff = 2**10

H = 700
W = 201

isWall = [[False for i in range(W)] for j in range(H)]
used = [[False for i in range(W)] for j in range(H)]

lastX = -1
topY = 0

def read(y, x):
    global lastX, topY

    text = ""
    while True:
        s = client.recv(buff).decode("utf-8")
        if len(s) == 0:
            break
        text = text + s
        if len(text) >= 41*202:
            break
        if text[0] != "#" and text[0] != " " and text[0] != "@":
            break

    lines = text.splitlines()
    for line in lines:
        print(line)
    print("")

    if len(lines) == 0:
        return False

    if lines[0][0] != "#" and lines[0][0] != " " and lines[0][0] != "@":
        return False

    offset = -1
    for i in range(0, len(lines)):
        x2 = lines[i].find("@")
        if x2 >= 0:
            offset = i
            if x >= 0:
                assert(x == x2)
            else:
                lastX = x2
            break

    topY = max(topY, y + offset)

    for i in range(0, offset + 1):
        y2 = y + (offset - i)
        if y2 >= H:
            continue

        for x2 in range(0, len(lines[i])):
            isWall[y2][x2] = ((lines[i][x2] != " " and lines[i][x2] != "@") or y2 == 0)

    return True

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
ds = ["up", "down", "right", "left"]

def write(directions):
    line = ""
    for d in directions:
        if len(line) > 0:
            line += ","
        line += ds[d]
    print("> " + line)
    client.send(line.encode('utf-8'))

read(0, -1)
write([0]) # go up

firstY = 1
firstX = lastX
read(firstY, firstX)

used[firstY][firstX] = True

finished = False
directions = []
def rec(y1, x1):
    global finished

    if finished:
        return

    exists = False
    for direction in range(0, 4):
        (y2, x2) = (y1+dy[direction], x1+dx[direction])
        if y2 < 0 or y2 >= H or x2 < 0 or x2 >= W:
            continue
        elif isWall[y2][x2]:
            continue
        elif used[y2][x2]:
            continue
        used[y2][x2] = True

        directions.append(direction)
        shouldRead = (y2 + 2 > topY)
        if shouldRead:
            write(directions)
            print((y2, x2))
            if not read(y2, x2):
                finished = True
                return
            directions.clear()

        if rec(y2, x2) or shouldRead:
            directions.append(direction^1)
            exists = True
        else:
            directions.pop()
    return exists

rec(firstY, firstX)

ただし、このままだと

Exception: You have been blown up on a mine

と言われて怒られます。

どうやら、通行可能なマスのどこかに見えない地雷がしかけられているらしい。 幸いにも迷路情報は固定なので、地雷を踏むたびにその場所を覚えて、次回以降は地雷を避けて迷路探索を行います。また、地雷はy座標が500より大きい場所にちらばっているようなので、これも利用します。

修正版がこちら:

import socket
import sys

sys.setrecursionlimit(10000)

client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
client.connect(("ppc-labyrinth.ctfz.one", 4340))
client.settimeout(3)

buff = 2**10

H = 700
W = 201

isWall = [[False for i in range(W)] for j in range(H)]
used = [[False for i in range(W)] for j in range(H)]

MINE_FILE_NAME = "mine.txt"

lastX = -1
topY = 0

with open(MINE_FILE_NAME) as f:
    lines = f.readlines()
    for line in lines:
        xs = line.split(",")
        isWall[int(xs[0])][int(xs[1])] = True

def read(y, x):
    global lastX, topY

    text = ""
    while True:
        try:
            s = client.recv(buff).decode("utf-8")
            if len(s) == 0:
                break
            text = text + s
            if text.find("Exception: You have") >= 0:
                print(text)
                with open(MINE_FILE_NAME, mode="a") as f:
                    f.write("{0}, {1}\n".format(y, x))
                exit(1)
            if text.find("Exception: Can not move to the wall") >= 0:
                print(text)
                exit(1)
            if len(text) >= 41*202:
                break
            if s.find("@") >= 0 and len(text)%202 == 0:
                break
            if text[0] != "#" and text[0] != " " and text[0] != "@":
                break
        except socket.timeout:
            print("time out!!")
            if topY < 600:
                exit(1)
            break

    if len(text) == 0:
        return True

    lines = text.splitlines()
    for line in lines:
        print(line)
    print("")

    if len(lines) == 0:
        return False

    if lines[0][0] != "#" and lines[0][0] != " " and lines[0][0] != "@":
        return False

    offset = -1
    for i in range(0, len(lines)):
        x2 = lines[i].find("@")
        if x2 >= 0:
            offset = i
            if x >= 0:
                assert(x == x2)
            else:
                lastX = x2
            break

    topY = max(topY, y + offset)

    for i in range(0, offset + 1):
        y2 = y + (offset - i)
        if y2 >= H:
            continue

        for x2 in range(0, len(lines[i])):
            isWall[y2][x2] |= (lines[i][x2] == "#" or y2 == 0)

    return True

dy = [1, -1, 0, 0]
dx = [0, 0, -1, 1]
ds = ["up", "down", "left", "right"]

def write(directions):
    line = ""
    for d in directions:
        if len(line) > 0:
            line += ","
        line += ds[d]
    print("> " + line)
    client.send(line.encode('utf-8'))

read(0, -1)
write([0]) # go up

firstY = 1
firstX = lastX
read(firstY, firstX)

used[firstY][firstX] = True

finished = False
directions = []

def rec(y1, x1):
    global finished

    if finished:
        return

    exists = False
    for direction in range(0, 4):
        (y2, x2) = (y1+dy[direction], x1+dx[direction])
        if y2 < 0 or y2 >= H or x2 < 0 or x2 >= W:
            continue
        elif isWall[y2][x2]:
            continue
        elif used[y2][x2]:
            continue
        used[y2][x2] = True

        if y2 == tmpY and x2 == tmpX:
            po = True

        directions.append(direction)
        shouldRead = (y2 + 2 > topY or y2 > 500)
        if shouldRead:
            write(directions)
            print("(y, x): ({0}, {1})".format(y2, x2))
            if not read(y2, x2):
                finished = True
                return
            directions.clear()

        if rec(y2, x2) or shouldRead:
            directions.append(direction^1)
            exists = True
        else:
            directions.pop()
    return exists

rec(firstY, firstX)

実行中の画面はこんな感じ↓ f:id:ark4rk:20191202061940p:plain

地雷データはmine.txtに書き出しています。何度もこれを実行するのはつらいのでshell scriptで自動化します:

#!/usr/bin/env bash

for i in `seq 1 5`
do
    echo "try: $i"
    if python solver.py; then
        break
    fi
    sleep 1
done

これでも5000兆時間かかってしまうので、最後に遭遇した地雷の場所を使ってからめっちゃ枝刈りをします。

import socket
import sys

sys.setrecursionlimit(10000)

client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
client.connect(("ppc-labyrinth.ctfz.one", 4340))
client.settimeout(3)

buff = 2**10

H = 700
W = 201

isWall = [[False for i in range(W)] for j in range(H)]
used = [[False for i in range(W)] for j in range(H)]

MINE_FILE_NAME = "mine.txt"

lastX = -1
topY = 0

with open(MINE_FILE_NAME) as f:
    lines = f.readlines()
    for line in lines:
        xs = line.split(",")
        isWall[int(xs[0])][int(xs[1])] = True

def read(y, x):
    global lastX, topY

    text = ""
    while True:
        try:
            s = client.recv(buff).decode("utf-8")
            if len(s) == 0:
                break
            text = text + s
            if text.find("Exception: You have") >= 0:
                print(text)
                with open(MINE_FILE_NAME, mode="a") as f:
                    f.write("{0}, {1}\n".format(y, x))
                exit(1)
            if text.find("Exception: Can not move to the wall") >= 0:
                print(text)
                exit(1)
            if len(text) >= 41*202:
                break
            if s.find("@") >= 0 and len(text)%202 == 0:
                break
            if text[0] != "#" and text[0] != " " and text[0] != "@":
                break
        except socket.timeout:
            print("time out!!")
            if topY < 600:
                exit(1)
            break

    if len(text) == 0:
        return True

    lines = text.splitlines()
    for line in lines:
        print(line)
    print("")

    if len(lines) == 0:
        return False

    if lines[0][0] != "#" and lines[0][0] != " " and lines[0][0] != "@":
        return False

    offset = -1
    for i in range(0, len(lines)):
        x2 = lines[i].find("@")
        if x2 >= 0:
            offset = i
            if x >= 0:
                assert(x == x2)
            else:
                lastX = x2
            break

    topY = max(topY, y + offset)

    for i in range(0, offset + 1):
        y2 = y + (offset - i)
        if y2 >= H:
            continue

        for x2 in range(0, len(lines[i])):
            isWall[y2][x2] |= (lines[i][x2] == "#" or y2 == 0)

    return True

dy = [1, -1, 0, 0]
dx = [0, 0, -1, 1]
ds = ["up", "down", "left", "right"]

def write(directions):
    line = ""
    for d in directions:
        if len(line) > 0:
            line += ","
        line += ds[d]
    print("> " + line)
    client.send(line.encode('utf-8'))

read(0, -1)
write([0]) # go up

firstY = 1
firstX = lastX
read(firstY, firstX)

used[firstY][firstX] = True

finished = False
directions = []

# Sugoi edagari
pruned = False
tmpY = 595
tmpX = 57

def rec(y1, x1):
    global finished, pruned

    if finished:
        return

    exists = False
    for direction in range(0, 4):
        (y2, x2) = (y1+dy[direction], x1+dx[direction])
        if y2 < 0 or y2 >= H or x2 < 0 or x2 >= W:
            continue
        elif isWall[y2][x2]:
            continue
        elif used[y2][x2]:
            continue
        used[y2][x2] = True

        if y2 == tmpY and x2 == tmpX:
            po = True

        directions.append(direction)
        shouldRead = (y2 + 2 > topY or (pruned and y2 > 500))
        if shouldRead:
            write(directions)
            print("(y, x): ({0}, {1})".format(y2, x2))
            if not read(y2, x2):
                finished = True
                return
            directions.clear()

        if rec(y2, x2) or shouldRead:
            directions.append(direction^1)
            exists = True
        else:
            directions.pop()
    return exists

rec(firstY, firstX)

ゴールに到着するとフラグが表示されました。

ctfzone{a6f5781532ae745ac3ff1e7967a9a4be}

これ、正攻法なのかな。

ソケット通信に慣れてなかったり、通信が不安定だったり、responseが返ったり返ってこなかったりで、本質でないところがつらかった。

ちなみに100個くらい地雷を発見した... ↓ mine.txt

518, 88
527, 90
530, 88
529, 88
556, 95
556, 97
553, 98
553, 96
555, 98
550, 95
550, 97
550, 86
552, 84
564, 83
548, 92
576, 88
577, 90
573, 90
570, 84
583, 80
578, 79
579, 78
576, 82
594, 85
587, 84
589, 86
586, 81
586, 80
585, 78
582, 82
578, 84
585, 84
543, 92
574, 79
568, 86
566, 88
571, 92
566, 89
568, 85
566, 84
565, 88
562, 82
566, 79
565, 78
559, 78
560, 78
564, 77
563, 76
562, 76
558, 82
560, 86
562, 87
558, 86
557, 82
552, 80
554, 80
561, 74
560, 74
558, 74
558, 72
556, 72
558, 70
546, 79
550, 80
552, 76
506, 84
525, 88
553, 76
549, 82
549, 94
546, 93
546, 94
546, 88
546, 85
545, 92
537, 90
542, 94
541, 96
537, 94
541, 86
541, 84
544, 82
540, 82
542, 79
555, 72
552, 70
591, 72
588, 71
589, 72
587, 68
586, 70
586, 66
584, 66
598, 64
598, 69
597, 66
591, 66
592, 62
598, 60
595, 56
596, 56