SECCON CTF 2019 国内決勝 writeup

yharima チームで参加．
アタックポイント 1000 pts + ディフェンスポイント 631 pts の計 1631 pts で 7位でした（去年と同じ順位だった）．

今回は，問題ごとではなく思い出せる範囲で時系列順で書きます．
ソースコードは末尾にリンクを貼っておきます．

f:id:yharima:20191222234154j:plain

問題概略

壱: バイナリが与えられて UDP パケット投げるとフラグが書き込める
弐: 画像アップロードしてなんかするらしい（見てない）
参: 多種多様なアーキテクチャのバイナリが与えられて BOF するやつ
四: 予選の reversing 問題みたいなバイナリとトレースが与えられて再現するやつ
伍: sname game の AI を各チームでバトらせて1位だとディフェンスポイントが得れる
六: Jeopardy 形式で色々な問題があった

1日目

壱

とりあえず壱のバイナリを読む，がなんかポート番号がおかしい．
ローカルでいくつかの index を与えて起動しても問題文のポート番号の計算と合わない．
:thinking: となっていたら問題修正が入った，別のメンバーが nc してひとまずフラグゲット．

次のディフェンスポイントはどうやら UDP パケットと token 投げつけると次の port が与えられて10回?やるといいらしい，ということをバイナリ読んで理解する．
ただ，なんか途中でポート見失うとそのポート特定しないと何の応答もできなくなるので，半分詰んでしまうきつい問題だった．既にアタックフラグを取ったメンバーがやってたのでバイナリ読んだ情報だけ共有して次の問題へ．

どうやらこの問題，最後は UDP パケットを受け付ける時間が短くなっていくようで相当つらそうだった．

参

複数のアーキテクチャのバイナリが与えられる． BOF があるのでなんとかするっぽい感じだった．
ARM のバイナリは読めそうだったので色々 qemu とか入れて試行錯誤したけど，どう頑張ってもうまく起動しない．
起動しないと exploit 書くことすらできずひたすらスタート地点にも立てず無限に時間を溶かしてた．

伍

気分転換に見てみるとどうやら snake game の AI を使って他のチームの AI とバトらせて1位をとるとディフェンスポイントもらえるらしい．
とりあえず動作させて BFS したりする簡単な実装してみたけど1日目は全然勝てず終了した．

1日目と2日目の間

1pts も点数を取れないまま1日目が終わり，無力感を噛み締めながら UDX のフードコートでラーメンを食べた．

正直家に帰ってこのままでは人権すらなく，椅子を温めるだけになりそうで本気で危機感を感じる．
まずは， ARM のバイナリを動かすために色々ビルドしたりしたけどやっぱり動かない．
正確には動くけど gets 途中でなぜか落ちる．でもエラーコードは返さず正しく終了する．もうこれは無理だ…と見切りつける．

CTF だし伍の snake game の AI それなりの書けばディフェンスポイントで人権得れるのでは?と考え実装を始める．まさかあんな過酷な戦いになるとはこのときは思いもしなかったのであった…．満足するものがすぐにはできず，結局朝5時くらいまで実装していた．この時点では以下の実装になっていた．

Python 側は必要な出力だけを吐いて C++ で答えそ返す
1つ目の Apple をとるまでは最短のものを探す
それ以降は mini-max で探索（深さ9）
評価関数は勝利条件である自身と敵の長さの差（死ぬ場合はそちらのほうが評価値が高い）

2日目

8:30 に起床．正直くそ眠くてあんまり記憶がない．ただ，俺ディフェンスポイントとったらもう会場で寝るんだ…というお気持ちで会場へ．しかしここからが本当の戦いだった．

初めて1位になるまで

10時開始とともに AI を投入するも勝てない…．
評価関数が良くなく， Apple をとりにいくことを優先させる結果死んでしまうようだった．
元々構想としてあった，評価関数に movable_count というその時点でいる場所から移動可能なマスの総数を組み込んでみた．この時点では評価関数は以下．

優先するのは長さの差
長さが同じ場合は movable_count が大きいほう

これでしばらく動かしていると結構勝ち始め，ついに 12:20 くらいに1位に躍り出る．この時点でのスコアは 1801.8463296316543 だった．
嬉しくて写真撮影をする．

f:id:yharima:20191223001559j:plain

防衛1: 小手先パッチ

みんなそんな本気じゃないだろうし，ここからいい感じにメンテナンスしつつ大きくアルゴリズム変えなくても大丈夫だろう，と思っていたが1時間くらい?すると負け始めまたフラグが奪われる．

どうもゲーム内容をみていると，大きいマップが降ってきたときに生き残るよりも自身の長さを大きくしすぎる結果，ターン終了までに自身の tail のせいで詰んでしまうケースが結構あった（戦ってる AI は生き残ることに全力なような動きでこれは厳しいという感じ）．
しょうがないので小手先のパッチである，自身と敵の長さが10以上（10は適当に決めた）ある場合は評価関数の優先順位を入れ替えるようにした．具体的には以下．

優先は movable_count が大きいほう
同じ場合は長さの差

この小手先パッチは意外と活躍し，それなりに防衛した．

防衛2: 残りターン数の導入

元々気になっていた残りターンを拾えてなくて，勝てる試合なのにゲーム終了以降も探索して変な動きをした結果負ける，みたい試合があった．
やはり負け始め，このあたりの問題を起こしているケースがあったので Python のコードを読んでいるとやはり残りターン数は渡ってきているようだった．
最初から見ておけよ…というのは :hyakuriaru: のですが，面倒だったので…．サンプルに書いておいてほしかった．
ターン数が 0 の場合はその時点で結果を返すようにするとまた勝ち始める．もうこのあたりで消耗戦感ができてもう許して…って感じだった．もちろん許してもらえない．

最終防衛まで: alpha-beta 法の導入とセグフォ

もう許して…あとできることは，探索の深さを上げるくらいで alpha-beta 法くらいしかないな…と思ってしばらく様子みていると負け始める．
このあたりはもう3チームくらいとデッドヒートを繰り広げていて，フラグの激しい奪い合いだった．

alpha-beta 法を導入し，探索の深さを 9 から 13 へ．ローカルでは alpha-beta 法導入前の AI とバトらせていい成績が出たので投入する．
デプロイするとセグフォで死ぬ…なぜ?と思っている間にすごい勢いでスコアが下がっていく．
死にたい気持ちになりながら見てもよくわからず，もっかいビルドして投げ込むと動き始めた．変なバイナリなげちゃったのか結局何が問題だったのかわからなかった．

動き始めるとやはり深く読めるようになったのか，ここからは勝ち始め最後まで防衛に成功した．
KMC がすごい勢いで追い上げてきてもうひたすら祈っていた．

5秒前のスコア一覧は以下（10.5.1.45:9999 はうちのチーム）．

{
    "score": {
        "10.5.1.48:9999": 1149.9201212027613, 
        "10.5.1.42:9999": 1596.4466710856354, 
        "10.5.1.37:9999": 1076.2148700052967, 
        "10.5.1.43:9999": 1846.3636003307793, 
        "10.5.1.45:9999": 1939.8270648109706, 
        "10.5.1.47:9999": 1229.7707035460242, 
        "10.5.1.44:9999": 1926.9832289707224, 
        "10.5.1.38:9999": 1601.2914897880303, 
        "10.5.1.39:9999": 1167.5223517980698, 
        "10.5.1.33:9999": 1265.149764353398, 
        "10.5.1.41:9999": 1101.8125012462992, 
        "10.5.1.46:9999": 1656.1592175341061, 
        "10.5.1.40:9999": 1801.4429520529613, 
        "10.5.1.34:9999": 1611.6238491044064, 
        "10.5.1.36:9999": 1243.9137867412862, 
        "10.5.1.35:9999": 1785.5578274292523
    }, 
    "result": {
        "1st": [
            "10.5.1.45:9999", 
            "14ab47837ca97d08d89c49dde8fedb55"
        ]
    }
}