ひよこになりたい

Security CTF Programming Server Network and so on

SECCON 2014 quals Online あみだくじ Writeup

先日のSECCON 2014 quals OnlineのProgramming 300 あみだくじを試合終了後にときましたので、置いておきます。

二時間程度かかりました。もうちょっと早く綺麗に解けるようにならないとな・・・。

Prog300 あみだくじ

問題ファイル:amida

実行ファイルが渡されるので、解いてねと言う問題。

書いたプログラムが以下。(python3)

# -*- coding: utf-8 -*-
import sys
from subprocess import Popen, PIPE

# 元の文章を渡すとhead(数字行), mondai(あみだ本体), tail(*行) のリストを返す
def transform(original):
    # 最初のNo~と最後の空白行を削除
    # top => 最初の行, bottom => 最後の行
    original = original[1:-1]
    top = list(original[0])
    bottom = list(original[-1])

    # あみだが横に倒れている場合
    if "".join(top).find('--') != -1:
        trans = []
        for m in original:
            t = m.replace('-', '#')
            t = t.replace('|', '-')
            t = t.replace('#', '|')
            trans.append(t)
        trans = list(map(list, zip(*trans)))  # 転置
        original = ["".join(tr) for tr in trans]
        top = list(original[0])
        bottom = list(original[-1])

    # 最終行が数字で始まっていたら上下を反転
    if bottom[0] == '1' or bottom[0] == '8':
        trans = []
        for m in original:
            trans.insert(0, m)
        original = trans
        top = list(original[0])
        bottom = list(original[-1])
   
    # 1 2  3  4    5 6 7    8 のように空白が開いている場合は、各行から冗長部分を削除
    if (top[0] == '1' or top[0] == '8') and "".join(top).find('  ') != -1:
        i = 0
        j = 0
        while i < len(top) - 1:
            while top[j:j + 2] == [' ', ' ']:
                for k in range(len(original)):
                    tmp = list(original[k])
                    del tmp[j + 1]
                    original[k] = "".join(tmp)
                del top[j + 1]
            i += 1
            j += 1

    head = list(original[0])
    body = original[1:-1# headとtailを除いた部分
    tail = list(original[-1])

    return (head, body, tail)

def main():
    p = Popen(["./amida"], stdout=PIPE, stdin=PIPE, shell=True)

    while True:
        print('=' * 50)

        # 標準出力から問題を取得する
        msg = ""
        while True:
            c = p.stdout.read(1)
            if not c or c == b'?':
                break
            msg += c.decode('utf-8')
        print(msg)

        original = ["".join(list(m.replace('\x00', ''))) for m in msg.split('\n')]
       
        # 整形処理
        head, body, tail = transform(original)
        print("#" * 30)
        print("".join(head))
        print("\n".join(body))
        print("".join(tail))
        print("#" * 30)

        # solve
        for i in range(len(body)):
            for j in range(len(body[0])):
                if body[i][j] == '-':
                    # swap
                    tmp = head[j - 1]
                    head[j - 1] = head[j + 1]
                    head[j + 1] = tmp

        answer = head[tail.index('*')]
        print("Answer:", answer)

        # 答えを投げる
        p.stdin.write((answer + '\n').encode())
        p.stdin.flush()

           
if __name__ == '__main__':
    sys.exit(main())

渡された問題を標準出力から読み取り、整形して、解いて、標準入力から渡しています。

結局あみだくじは橋が出てきたら数字を入れ替えて行って、入れ替え終わったら*の位置と照合するだけでいいので、整形のほうがメインになってきます。

この問題、問題が進んでいくたびに上下が逆になったり、橋の間隔が大きくなったり、横になったりするので、それぞれに応じて整形してあげなければいけませんでした(ここが一番つらかった)

問題の出現順序が変わらなかったので、「一問あたりの制限時間あるけどどうせ100くらいなら手作業でいけるっしょ〜w」と思い、競技中は順番に入力して解いてたんですが、100問超えくらいから徐々に怪しくなって、160問くらいでつらくなったのでやめました。

その後、やっぱスクリプト書こう!!ってことで書き始めたんですが、もう考える気力と集中力は残ってなかった。結局解けず・・・(あたがわさんに任せとけばよかったなぁ・・・)

実はPythonのsubprocess.Popen使って標準入出力を制御する方法がわからず、ぐぐっても見つけきれなかったので始めは

$ netcat -l -p 40000 -e ./amida

して、それに対してTelnetlibから入出力を受け取って解いてました w

メンバーさんに聞いたらやっぱりPopenでできるみたいだよ!とURL付きで教えてくれたので、それを参考に組みました。勉強が足りないな・・・・。