こんにちは、新入生の「てぃだ」です。
この度、CPCTF2024に参加してきたので、それについて少しだけ書こうと思います。
CPCTFって？
簡単に言うと、「CTF (CatchTheFlag) + 競プロ」で競う大会です。
公式の紹介記事もあるのでぜひ読んでみてください。↓
kaitoyama
About Me
- 競プロは高校時代に少しだけやったことがありました。
- CTFはガチの初見。
解いた問題
解いた問題とその解法的なものを、解いた時間順に載せておきます。
数日経ってすっかり記憶が吹っ飛んでしまったので、憶えている範囲でしか書けませんが、ご容赦ください...... m(_ _)m
Attack! Attack! Win!
関数のアドレスがコンソールに出てたので、入力値を負にしてフラグを吐く関数を実行させました。
About half
条件をそのまま書きました。
Compound World
作れる文字列は高々2500通りなので、全部やって set<string> に突っ込みました。
Substitution
適当にずらしたとかいう感じではなさそうだったので、出現頻度から e は p に置き換えられていると推測して、あとはパズルのように地道に対応表を作っていきました。
You're が Rug'dp、Well done! が Cpvv muzp! だと分かった後はすぐに答えを出せました。
Typing game
文字ごとに KeyboardEvent を発行する関数を書いて、多分おそらくメイビーおおよそ正規のやり方でフラグを手に入れました。
他の方の writeup を見て思いましたが、これソースコード見ればすぐだったな......
mokomoko
「赤いもこもこ 植物」でggると、なにか公園が出てきたので、あとはストリートビューで周囲を見渡して確証を得ました。
netcat
「これさっきやったよな......」と思いながら nc コマンドを打ちました。
omu-napo
画像データに座標が載っていたので施設はすぐに特定できましたが、どのお店か探すのに15分程かかってしまいました。
peeping
バイナリエディタで見てみると、フラグがそのまま書いてありました。
ここまでで、Newbie の問題は全て解ききりました。
Balanced Choice
まさか Easy の最初でDPをすることになるとは思ってもいませんでした。
ぱっと見てDPを使うんだろうということまでは分かりましたが、上手い解法が浮かばず悩むこと1時間、「そういえば石の数はそんなに多くないよな」と思い、そこからなんとかプログラムを書き上げました。
ちなみに、恥ずかしながらDPのやり方 (添え字の取り方) を完全に忘れていたので、ナップサックの解説を読みながら書きました。
CPC To F
先ほどの問題でゴリゴリのDPを使わされたのに気を取られてか、この問題もDPで解く方針でやってしまいました。
それで一応解けるのですが、CPが3回以上連続している部分の処理を書いたり、条件分岐をごにょごにょやっていたらかなり時間がかかってしまいました。
ちなみに実行速度は15msとなっており、正攻法と大きく離れている割には結構速いのでは！？と思っています。
ところで、どうやらこんな解法をしている奴は自分だけっぽいので、下に細かい実装の話を書いておきます。
細かい話
CPC...PC となっている部分を列挙して、その各部分に対し、ひとつ前の部分との間にどのような文字が挟まっているかを考えました。
そして、DPですが、
count[i][0]:=i+1番目のCPC...PCまでの部分文字列のうち、少なくともi番目のCPC...PCの 最後のCPCをFに変換したときのCPCTFの個数の最大値。count[i][1]:= 〃 最後のCPCを変換しなかったときのCPCTFの個数の最大値。
という定義をしてDPを行いました。
このような定義にしたのには理由があり、隣り合う CPC...PC の間の文字によって以下のような条件分岐をする上で都合が良かったからです。
- 間の文字が
Tだった場合 - 〃
TF%だった場合 (%はCPC...PCを含まない任意の文字列) - 上記以外の場合
これで実装は終わり......ではありません！まだ重要な部分が残っています。
それは「 CPC...PC の中で PC が何回繰り返されているか」です。
これが3回以上の場合は、先頭の CPC を F に置き換えても末尾の CPC に影響はありませんが、1回または2回の場合ではそうはいきません。
これを考慮して実装することで、ようやくACが得られたのでした。
(実は、この考慮を忘れて3回ほどWAを叩き出しました......)
CPCT...
調べてみるとどうやら printf(buf) がよろしくないらしいので、 %d などを打ってみるとなんかたくさん文字が出てきたので、その後も試行錯誤してなんとかフラグを得ました。(何を打ったか忘れてしまいました......)
Doctor yellow
東工大の近くで新幹線が川を越えているあたりをGoogle Earthで調べました。
ところが、EarthとMapでは座標が微妙に違うらしく、何度打っても正解にならずしばらく悩んでしまいました。（Mapの方の座標が答えだったようです）
Dokoda?
fukushin と調べると店が出てきたので、店舗情報を見ながら片っ端から最寄り駅の名前を打ち込んで、フラグを得ました。
後になって、WiFiの情報が載ってるサイトがあるということを知ったのですが、これは初耳でした。
Just reversing?
コードを読んでみると上位4ビットと下位4ビットを反転させていることが分かったので、バイナリを読みながら手動でやりました。
Let's buy some array
コードの中にあからさまに eval が書いてあったので、コンソールからPOSTリクエストで文字列を送り付けてフラグを得ました。
Read novels
name に ../flag を指定してフラグを得ました。
Old Maid
双方向連結リストを用いて、貪欲法で解きました。
std::list<T> を使おうとしたのですが、なんか実行時エラーが出たりしてよく分からんかったので、この問題だけ C# でやりました。
一般的に連結リストは動作がかなり遅いので、もしかしたらTLE になるかもと少し心配でしたが、なんとかなりました。
veeeeeeery long text
grep しました。
恥ずかしながら、コマンドを１ピコメートルも知らない人間なので、普通にggりました。
leaving
熱海辺りで新幹線の停車駅を探し、あとは適当にggって見つけた時刻表サイトで時刻を照らし合わせました。
Time is money
タイトルの通り「時は金なり」なのですが、僕はこの問題に2時間強かけました。
時間と必要な金額をまとめて持っておけばよかったのに、なんと別々に持ってしまったので、TLE を連発してしまい、いい感じに処理を削るのに苦労しました。
これ以降は全てCTFの問題を解きました。
Car Flow を解いてる人も結構いたみたいなんですが、ぱっと見た感じよく分からなかったので、僕はCTFの問題に当たることにしました。
Great view
「見晴台 ゲーム 聖地」と調べるとすぐに出てきました。
Patlite
都営バスの番号が見えたので、経路を調べ、ゆりかもめが近くに通っている場所を探すと、どうやら新橋駅付近だと分かったので、あとはストリートビューで歩き回って見つけました。
ちなみに、この問題を解いた時刻はなんと朝3時半で、「これから寝たら昼起き確定かもしれないな」と内心思っていましたが、以外にも10時に目が覚めました。
turning over
なんかBlenderで弄り回してたら出てきました。
Register
どうやらUSBキーボードからの入力をキャプチャしたものらしいということは分かったのですが、この信号をどう戻すか悩んで時間が掛かってしまいました。
対応表らしきものをネットの海からなんとか掘り出して、無事にフラグを得ました。
white has much imformation
3種類の文字だけで構成されていると分かったので、文字別に背景色をつけてみるとなんかバイナリっぽい部分が見えたことから、頑張ってバイナリエディタに手打ちで突っ込んでフラグを得ました。
参加者アンケート
アンケートに回答するだけでフラグが貰えました。なんでだろう？
反省点
反省点が一つだけあり、それは「もっとツールを使ったりスクリプト書けばよかった」ということです。
他の方の writeup を見てみると、ツールを活用してる方や、逆変換等のプログラムを書いている方が意外といて、自分ももっとツール使えばよかったなと思いました。
スクリプト系言語は久しく触ってなかったので、そこも少し反省......
さいごに
率直に楽しかったです！！（小並感）
東工大に入る前から traP ではあの班に所属したい、あの班はちょっと興味ないかなとか考えてたんですが、実際にCTFを体験して、「あっCTF班良いかも……！！」ってなってます。
ここまで読んでいただきありがとうございました。
