10/18-20に開催されたHackceler8（Google CTF 2024の決勝イベント）にチームKijitoraとして参加し、優勝することができた。賞金7331ドル*1も得た。これはそのWriteup兼参加記。*2
KijitoraはGoogle CTFのために結成された日本人合同の大きなチームで、私は今年からkeymoonさんに誘われて参加した。
予選は6/22-24に開催された。Kijitoraには強いCTFプレイヤーが沢山おり、私が焼きなマシーンをしていたら*3すごい勢いで問題が解かれて2位になり、ここでも賞金5432.1ドルを獲得した。8位以内だったため決勝に招待される。
決勝のオンサイト参加に立候補する人が全然おらず、他に行く人が居なかったら行きたいけど…と思っていたらkeymoonさんに引っ張り出された*4。結局keymoonさんとptr-yudaiさん、同様に引っ張り出されたArataさんの4人でスペインに行くことになった。内ptr-yudaiさんを除く3人は全員筑波大学生。
Hackceler8は予選とは全くルールが違い、CTFとSpeedrun(日本ではRTAと呼ばれることが多い？)を組み合わせたような感じで、ゲームに埋められたバグを見つけ出し、それを使ってステージをクリアするまでを競うというような大会である。
ルールを聞いただけでもかなり私の好きそうなコンテストで、せっかくスペインまで行くなら頑張ろうという気持ちだった。
~Day0
9/14 にベースとなるゲームが公開された。本番ではこのゲームのステージやギミックの一部が改変されるため、それに対応できるよう予め色々なチートを準備する。
軽く触ってみると、マリオとかのような所謂プラットフォーマーと言われるジャンルのゲームらしい。例として用意されているマップも単純に難易度が高いものが多く、チートなしの人力では確かにクリアするのは厳しそうだった。
いくつかマップがあり、各マップにいるNPCまでたどり着くとスターが貰える。スターを一定数集めるとボスへのポータルが解放されるという感じのようだった。また、毎試合いくつかコインが配置されており、それを取る事で以降の試合で相手チームに対して妨害アイテムが買えるらしい。
とりあえず前年のゲームや配信、公開されている出場チームのツールを見て、どのようなチートを実装する必要があるのか考える。
試合は45分の準備フェーズと、リモートサーバーにつないで実際にステージをクリアする45分の後半フェーズに分かれている。基本的にすべてのチームは準備フェーズ中にローカルでステージをクリアし、そのときのキー入力のリプレイを記録しておいて後半ではそれをリプレイするという流れになる。
そのためにキー入力を記録/再生する機能はほぼ必須である他、当たり判定の表示やゲームを1tickずつ進めるといったチートはどのチームも実装しており、確かにあると便利そうだった。
他に、フィールドにお絵描きできるアイテムがあったので自動でお絵描きできるツールを描いた。色合いがpietっぽいしpietを描かせる問題が出そうだなあと思っていたら本番では本当にpietを書かされた。
その他、ゲームを数tick前の状態に戻すといったUndo機能も実装した。これにはゲームの状態全てを保存しておく必要があり、更にゲームコードの変更にロバストでなければいけない。色々試行錯誤した結果、ゲームオブジェクトを丸々pickleしてunpickleすることにした。中にはネットワークまわりなどいくつかpickleできないオブジェクトも存在するため、それらは別で保存しておいてunpickleする時に元に戻す。
ほかのチームメイトは学園祭実行委員やCTFプラットフォームの運営などで非常に忙しそうにしている中、私はずっと暇人だったので一人ツールづくりに勤しんでいた。結果としてコードベースを一番把握しているのが自分になり、競技中にコードを書く必要があった場合は大体私の担当になった。
Day1
1日目は全チームが同時にプレイする形式の試合が3回行われた。この結果で順位が付き、1,2位、3,4位、はそれぞれ2日目以降のトーナメントで2試合、1試合分のシード権が与えられる。
3試合の結果はそれぞれ2位、1位、6位で、全体2位通過と悪くない結果だった。
面白かったのは2試合目のruinsステージ。鍵付き扉2つの先にNPCがいるが鍵は一つしかなく、どうにか鍵を増殖させるなどして両方の扉を開けなければいけない。
一度開けた扉をもう一度閉じると鍵が再度もらえるが、この際入口側に押し出されるため扉の中から鍵を抜くといったことはできなそうだ。
ここで、扉の開閉状態と鍵の所持状態はsave_fileファイルで管理されているのが気になった。サーバーにつなぎ直した時、扉と所持アイテムの状態はsave_fileファイルから読み取って初期化される。save_fileファイルはサーバー側でtickごとの一番最初で更新されているが、アイテムを取得した際などにも追加でセーブされる処理が走っている。
処理をよく読んでみると、扉を閉じたとき、扉の開閉状態が更新される処理は鍵の再取得の後であり、それがセーブされるのは次tickでのセーブ時である。よって、次tickの情報をサーバーに送信する前にゲームを切断すれば、サーバー側での最後のセーブは鍵を再取得した直後、扉が閉まる直前のものになる。よって、次回のゲーム開始時には鍵を持っていてかつ最初の扉が空いている状態になり、2つ目の扉も開けられるということになる。
この他にもこういうバグ実際のゲームでもありそうだな〜みたいな問題多く出題されており、それこそRTAとかが好きな人は有利だったかもしれない。
3試合目のボスはCTFでよくあるpath traversalでキーワードをリークする問題だった。なんとか倒せたものの、用意していた「サーバーにパケットを送るのを遅延させるチート」にボスを倒すとその後のパケットが送られないというバグがあり、クリアした判定にならなかった。それを直して再度ボスを倒すも、試合終了に数秒の差で間に合わなかった。
開始前は｢2日目で負けると3日目暇になって嫌だな〜｣とか思っていたので、とりあえず3日目まで行けることが確定して安心した。それと同時に、この時点で賞金圏内が確定したらしくびっくりだった。また、この時点で22枚とかなりコインを稼げていたのも良かった。
この日実際にツールを使ってみて、改善が必要な点を一通り洗い出して実装していった。
Day2
2試合分のシード権を得ているのでこの日は試合はないが、問題は全てのチームに配布との事なので練習として本番と同様の状況で問題を解いた。
オンラインで参加していたメンバーが少なかったのもあったが*5、2戦目では実際に対戦していたチームの全てに負けており、かなり次の日が不安になった。
特に、ゲーム内で別プロセスが実行されるarcadeというステージでは色々なチート機能を無効にするようにしており、ほとんど何も対策していなかったため、単純な解法の問題が解けなかった。どんな問題が出るか全く想像できなかったため安全側に倒していたが裏目に出た。その場でコードを書き換えてarcadeでもtickrate変更とtick停止を使えるようにしたが間に合わなかった。
試合後、すでに敗退したチームが既に自分たちのコードを公開していた。マジかよと思ったがどうやらCTFではそういうもんらしい。C4T BuT S4Dのツールを見ていると、経路探索機能のドキュメントとして登れないはずの壁を登っている動画を貼っていた。ベースのゲームには意図されたバグは仕込まれていないはずなのでかなり驚いたが、実際に手元で動かしてみると確かに壁を登れている。
ベースのゲームでそんなことができてしまうといくつかのスターが非想定で簡単に取れてしまうほか、なんなら実は意図的に仕込まれていて最後の大謎として出題されるのではないかと思い、挙動を解析して自分達のツールでも使えるよう組み込んだ。
どうやら2年前にもあらゆる壁を抜けられるバグがベースのゲームに存在しており、その時はすぐにパッチされて使えなくなったらしい。
https://github.com/C4T-BuT-S4D/hackceler8-2024
色々解析した結果、次のようなことがわかった。
まず、このゲームでは重力は移動によってプレイヤーが壁や床に触れてめり込んだ時、上下左右4方向に対して、その方向にどれだけ押し出せばプレイヤーが壁にめり込んでいない状態になるかを計算し、最も小さい方向（min push vectorと呼ぶ）に押し出す というロジックが存在する。
ジャンプ可能かの判定は、プレイヤーの座標を1だけ下にずらした時、min push vectorが上方向であるような当たり判定が存在するならcan_jumpをTrueにする。
というように処理している。
壁に向かってジャンプしてめり込み、ふたつの壁の境目でcan_jump判定を更新すれば壁ジャンプができそうである。ところが、ゲーム処理は、
- ジャンプ可能判定の更新
- プレイヤーの入力を反映
- min push vector方向に押し出してめり込みを解除
という順番で行われているため、ジャンプ可能判定の処理時点ではめり込みが解除されており一見壁ジャンプは不可能である。
しかし、コードをよく読むと、プレイヤーを押し出す時push vectorをintに丸めた値が0であれば押し出さないという処理がある。
これによって、1未満であれば壁にめり込むことができる。*6
プレイヤーの移動速度は2.3/tick、ダッシュすると1.5倍の3.45/tickのため、プレイヤーの座標 mod 1.15は常に一定となる。しかし、壁に当たることによってこの座標 mod 1.15の値(これをsubpixelと呼んでいた)を変えることができる。
これによって、適切な壁があれば、壁にめり込む量を1未満の間で0.05単位で調整することができる。
まとめると、
「上下に重なるふたつの壁境目で、1だけ下にずれたときに横方向のpush vectorより上方向のpush vectorの方が小さくなるように、予め適切な壁にぶつかってsubpixelを揃えておき、ちょうど壁にめり込みむところまで移動し、ちょうどジャンプ可能判定がTrueになるタイミングでジャンプキーを入力する。」
という手順で壁ジャンプが可能となる。
壁ジャンプするためのsubpixelが揃っている壁のビジュアライズと、ちょうど壁にめり込む所までだけ移動するのの自動化、can_jump判定がTrueになるタイミングでのジャンプの自動化を書いた。
決勝で実際に出題されたが、その時はcan_jumpの判定方法が変更されていて若干簡単になっていたようだった。
また、これについて解析している途中で、can_jumpがTrueになるタイミングですぐにジャンプするとlast_ground_posの値が更新されないバグも見つけ、これも決勝で出題されたため役に立った。
Day3
2日目までとは違いYouTubeに配信されているため、大きな講堂のようなところで箱に入れられて競技をすることになった。2日目までは他のチームの声でオンラインメンバーと繋いでいたVCが全然聞こえなかったが、今度はちゃんと防音されておりその点ではかなり良かった。
会場準備が押したらしく準決勝の開始10分前に会場入りして慌ててpcなどのセットアップをした。
Semifinals
準決勝はKalmarunionenとの対戦だった。
modをゲームクライアントに自動で適用させるpatcherが上手く動かず序盤で躓いたが、準備フェーズ中にocean、ruins、arcadeがクリアされた。
ボスに入った時点ではリードしていたが、相手に先にボスを倒されると負けるため全く油断できなかった。
しかし、オンラインのxrekkusuさんが突然「倒した」と言ってキー入力ファイルを上げた。早すぎて全く意味がわからなかったが、どうやらoceanのステージをクリアするのに使った｢しゃがみながらだと攻撃のクールタイムがなくなり秒間30回攻撃できる｣というバグがボスにも使えたらしい。急いでサーバーに繋いでボスを倒し、こちらのチームが勝利した。
あとから聞いた話だと相手チームも数分差でボス部屋まで到達しており、同じ方法を試そうとしていたところだったとの事で、本当に危なかった。
他のチームが戦っていた2試合目はバグを直しながら客席で観戦した。ボス問としてNPCとインタラクティブに会話するpwnが出るなど、うちのチームが得意そうな問題群が出て｢こっちの問題がやりたかった｣などと話していた。
Finals
決勝はZer0RocketWrecksとの対戦だった。
決勝までは30分ほど時間があると聞いておりゆっくり準備をしていたらいきなり問題ファイルが共有されて試合が始まり、慌ててpcなどのセットアップをした。
開始から15分ほど、ruinsが前日に用意した2段ジャンプチートでクリアできるらしい。
beachも前日に用意した自動ジャンプを使うと上手くいくらしく、25分ほどで準備フェーズ中にクリアされた。
cloudもサーバーに接続可能になる直前にクリアできたらしく、あとはarcadeかmazeのステージがクリアできるとボスポータルを解放できる。
今までのarcade問は全てPythonだったが、ここではバイナリが実行されていた。arcadeは私が担当するつもりだったが、バイナリでpwnっぽいとなると自分より適任がいるのでその人達に任せる。
mazeのpiet問がローカルで解けたと報告が入る。その後リモートでも特にバグらずに動き、これでボスが開放された。この時点で残り30分程度、得たスターの数は7-3で勝っていた。
ボスは一見ベースゲームから何も変更がないように見えたが、hpを半分まで減らすと第2形態に移行し全くダメージが入らなくなった。ボスに重なって攻撃する、近接攻撃する、第1形態の間に弾を貯めて一気に攻撃する、など色々試したが最後まで倒せず、ゲームが終わった。
終わった瞬間はボス倒せなかった……という気持ちだったが、よく考えるとボスに入る時点では勝っており、その後逆転された様子もないのでどうやら勝ったらしい。実感がわかないうちにインタビュワーが部屋に入ってきた。
優勝できるとは思っておらず、また予選はかなりキャリーされ気味だったので、ちゃんと活躍した結果の優勝というのもありかなり嬉しかった。
書いたツールはかなり便利に動いてくれた。ただし、ノリで適当に機能を継ぎ足していったら自分でも汚いと思う感じのコードになり、チームの人にももうちょっと手加減してくれと言われながらリファクタリングされるなどしたのはかなり反省だった。その割に本番は大きなバグなく動いてくれてよかった。
優勝チームは毎年ツールを公開してるよ！みたいな圧をかけられた(?)ので、作ったツールはGitHubに公開している。cloneして適当にmod.pyを実行すれば動くようになっているはずなのでぜひ触ってみてください。
github.com
