Project SEKAI CTF 2023に初心者チームで出た
経緯
いつもボードゲームや謎解きをして遊んでいるグループでProject SEKAI CTF 2023にチームで参加する人を募集していたので参加してみた。 プロセカはやったことなかったが、コンテストページのUIがプロセカ仕様?ですごく凝っていた。
前回のチャレンジは↓ takeo1116.hatenablog.com
僕は前回と同じくreverseカテゴリの問題を一人で解いていた。
Azusawa's Gacha World
問題概要
Unityでビルドされたガチャアプリが与えられる。
小豆沢こはねHAPPY BIRTHDAYガチャを引くことができるが、100石しか持っていないので1回しか引くことができない。ガチャ詳細を見ると最大レアリティである「[Happy Birthday!!2023] 小豆沢こはね」の出現確率が0%となっており、100万回引くと必ず手に入ると書かれている。
解法
Unityアプリなので、Managedディレクトリにあるdllをいじればなんとかなるだろうと当たりをつける。 見るとライブラリ系のDLLに交じってAssembly-CSharp.dllというファイルがあるので、とりあえずこれをGhidraにかけてみるもC#なので逆コンパイルまではできなかった。かろうじて石消費の処理を見つけてガチャを引くたびに石が増えるようにバイナリエディタで書き換えることはできたが、石が無限だったところでガチャを100万回引くことはどちらにしろ現実的ではない。
調べると、DnSpyというツールを使えばdotnetの逆コンパイルだけではなく書き換えまでできるということだった。
早速使ってみると、バイナリやアセンブリを解さずにdllの中身を直接コーディングするかのように書き換えることができた。 編集し終わったあと、対象のdllファイルをDnSpyからRemoveしないと反映されないことに注意。
難読化されていないdotnetアプリは逆コンパイルすると変数名やリテラルまでそのまま残っているというのは知らなかったので驚いた。 なんにせよ、これで100万回目だけを引くことができるので、100石で「[Happy Birthday!!2023] 小豆沢こはね」を手に入れてAC。
Teyvat Travel Guide
問題概要
netcatのコマンドと、解析用のバイナリファイルが与えられる。
解法
与えられたバイナリを実行すると、48×48のマップが表示される(幅の都合で省略)。 左上にX印がついているが、説明などは表示されない。
Start travelling... +---+---+---+---+---+---+-- | X | | | | | | +---+---+---+---+---+---+-- | | | | | | | +---+---+---+---+---+---+-- | | | | | | | +---+---+---+---+---+---+-- | | | | | | | +---+---+---+---+---+---+-- | | | | | | | +---+---+---+---+---+---+-- | | | | | | |
問題タイトルやコンテストページのフレーバーから、左上に自分がいて、マップを歩くゲームだと解釈した。 入力待ちになっているのだが、何かを入力しても
The loneliness of death...
と表示されて終了してしまう(死んだということだろう)
何もわからないのでGhidraで解析して探っていくことにした。逆コンパイルしてみるも、関数名などの情報がすべて失われているので非常に読みにくい。 画面に"Start travelling..."という文字列が表示されていることから、この文字列が格納されている場所を調べることで目的の関数を見つけることができた。 これを手掛かりにコードを解析したり、実際に動かしたり、バイナリを書き換えて挙動を調べたりすることでかなり時間をかけつつもゲームのルールを理解できた。
- プレイヤーは48×48のマップの左上にいる。
- プレイヤーは値を持っており、333からスタートする(これをHPと解釈した。)
- 1ターンごとに"R"または"D"を入力することで、右か下に1マスずつ進むことができる(それ以外を入力すると即死する。)
- 各マスには値が設定されており、踏んだマスの値がHPに加算される(基本的には負の値なのでダメージとなるが、正の値もある。)
- HPが0以下になったら死ぬ。
- 残りHPがちょうど1の状態でマップの右下(The edge of tayvat)にたどり着くとクリアとなる。
ゲームをクリアするためには各マスのダメージを知る必要がある。 逆コンパイルしたコードを調べれば生成ロジックが分かりそうだが、読むのが難しいので動的にメモリを参照できないかと考えた。
Linuxで動作しているプロセスのメモリを動的に解析する方法を調べたところ、gdb-pedaが便利ということだったので導入した。 gdb-pedaを使うと命令単位でブレークポイントを設定して、その時点でのメモリの状態を参照することができる。
Ghidraでアセンブリのニーモニックを見ながらマップ配列のアドレスがレジスタにロードされる場所に当たりをつけ、そこにgdb-pedaでブレークポイントを設定することでメモリアドレスを取得、そこからの配列の値を調べることができた。
配列の値が分かったら、実際にマップ上を移動してメモリ上でHPの変化を見ながらマップに対してどういう並びで値が設定されているのかを調べていく。 今回の場合マップには48×48=2304個のマスがあるが、配列の先頭から2304個が各マスに順番に入っているのではなく、配列の途中に0が16個並んでいる箇所が2つあり、その32個の0は無視されているようだった。 よって、左上には配列の0番目の値が、右下には配列の2335番目の値がダメージとして設定されているということになる。
こうしてすべてのマスのダメージ値が分かったら、左上から右下へ死なないように歩くときの最小ダメージ値は簡単なDPで求めることができて、その答えは332となる。 経路復元をすると
DDDDDRRDDRRRDRDDRDRDDRRDRRRRRDRRDDRRDDDRDRRDRDRRRDDRRRDRDRRRRDDDRRRDDRRRRRDDDDDRRDDRRDDRDDDDDD
となるので、この通りに移動すればゲームをクリアしてflagをゲットできた。
The edge of Teyvat... SEKAI{Klee_was_a_brave_girl_today!_I_found_a_really_weird-looking_lizard!_Want_me_to_show_it_to_you?}
結果
チームとしては、3004ポイント獲得で25位/981チームだった。 CTF初心者チームなのだが、僕以外のチームメイトのAtCoderレーティングが高すぎる(赤、橙、橙)ためにPPCジャンル(競プロっぽい問題が分類されるジャンル)の問題を全完していた。 僕が個人で取れたポイントは500ポイントなので、初心者なりの活躍といった感じだった。
前回のSECCON BeginnerでReverseジャンルの問題を練習したので今回もReverseの問題をやっていたが、2問目に解いたTeyvat Travel Guideは難しい寄りの問題だったらしく31チームしか解けてなかったので、それが解けたのは良かった。 最終日にPwnジャンルのCosmic Rayという問題にチャレンジしていたのだが結局解けなかったので、後で復習したい。