CPCTF2024で新入生1位になりました!

こんにちは、24Bの@zoi_dayoです。4/20~21に開催されたCPCTFに参加してきたので、感想を書きます。

CPCTFとは?

運営陣が紹介記事を書いているので見ましょう。競プロとCTFを合わせたコンテストです。
競プロの問題をACすればFLAGが得られるようにして、うまくCTFと同じ土俵に乗せていてすごいな〜という感じです。

参加時の状況

競プロ

競プロは1年半くらやっていて、AtCoderで水色上位くらいです。あまり24Bの人々を把握できていないのですが、24Bでは5位くらいなのかなあ、と思っています。

CTF

CTFはコンテストへの出場はしたことがなかったです。前日までに、ネット上の例題みたいなのをちょっと解きました。(CpawCTFのLevel2までです)

一応、高校でWeb開発を全部任されたことがあり、ラズパイへのOSインストールとかポート開放、Webページの作成、最低限のLinux知識(キー生成してSSH接続して...くらい)はありました。
あと、gdbやwireshark、johnの存在とできることくらいは知っていました。

環境

大学に入って暇だったときにデスクトップにLinux(arch+hyprland)を入れておいたので、手軽に参加することができました。ただし知識がないのでギリギリ使える程度です。

メモ

コンテスト時間が30時間もあるので、しっかりメモを取りながらやらないと情報をなくしてしまいます。自分だけが入っているdiscordサーバーを作り、問題ごとにチャンネルを作って管理しました。

結果

なんか最後にサイトが落ちて30分延長されたりして怖かったですが、なんとか新入生内1位、全体9位になることができました。やった〜

グラフ見ればわかりますが、最後に頑張って追いついた感じですね。解かれるにつれて配点が下がっていくので、何もしていないのに差が詰まったり開いたりすることもありました。怖いね...

得点的には、比較的得意ということになっていた競プロよりもCTFで稼いだ感じですね、結構想定外 (CTFer少なそうだし競プロで勝てば逃げ切れる、くらいに思っていた)

ちなみに問題コーナーの正解時刻を見るとわかると思いますが、土日のほとんどすべての時間を吸われてしまいました...
来年以降CPCTFをガチろうと思っている人がいれば、絶対に課題を開始までに済ませておきましょう。

問題(解いた順番に)

真面目に解いていない問題(ヒント3まで連打してから考えた、など)は飛ばします。

10時開始でしたが、起きたら11時20分でした。とりあえずPCの前に座ります。短期コンテストじゃなくて良かった...

【Newbie/Pwn】Attack! Attack! Win! (10.00点 11時38分)

Cのコードが渡されるのでじっと読むと、なんかwin関数を実行すれば良さそうです。
input>3は対策されているので、inputが負なら対策をすり抜けて変なことができそうですね。
ncコマンドがなかったので入れて、謎のhocusPocusコマンドを実行してみると、メモリアドレスが出ます。
どうやら入力1でアドレス0x...70、2で0x...78と8づつになっていそうなので、winの0x...58を実行するためには-2で良さそうです。

【Newbie/Crypto】Substitution (10.00点 12時26分)

ぱっと見シーザー暗号に見えたのでやってみるとうまくいきません。CPCTF{になりそうな部分が見えるのでいろいろ考えますが、普通に換字式暗号だと思ってやってみます。
英語なのでどこかにtheがある気がするので、nzmかijpだなー、と思いながらCPCTF{の部分を見るとijpだとわかります。あとはいちいちsedコマンドをちょっとずつ編集しながら見ていくといつか答えが出ます。

【Newbie/Web】Typing game (10.00点 12時28分)

ちょっと経験があるWebなのでわくわく。とてもタイピングが早ければできそうですが、ツールを作るのも手間です。Webゲームなんて大抵はJavaScriptのガバガバセキュリティなのでソースを見ると、FLAGが書いてあります。

【Newbie/OSINT】mokomoko (10.00点 12時30分)

こんな問題もCTFにあるんだ...と思いながら、右クリック→「Googleで画像を検索」で終わりです。施設名「国営ひたち海浜公園」がわかるので、あとはこれのHPを開けばFLAGができます。

【Newbie/Shell】netcat (10.00点 12時32分)

netcatコマンド、さっき入れたなあ...などと思いながら実行します。ポート番号は:で繋げばOKです。

【Newbie/Reversing】peeping (10.00点 12時48分)

なんか文面が自慢げなので、おそらくif(input == "CPCTF{...}")というコードがあるのでしょう。というかそうでなければかなり面倒なので、stringsコマンドという最強ツールを実行します。

【Easy/Pwn】CPCT...... (120.72点 13時06分)

Newbieが10点しかないので、順位表を見るとあまり良い感じではありません。EASYを解きます。

Cのコードが貰えるのでじっと見ます。うーん、文字数制限がかけられていそうですね。
lengthを書き換えたいなと思いながら見るとlength = printf(buf);があり、printfってint返すんだっけ? とか思いながらprintf 脆弱性 ctfとかで検索するとテンプレート文字列がバグるという話が出てきます。

いろいろ試すと%s%aでCPCTF{1m_50rrY_bu7_i_Hav3_0nLy_45_ch4raCteRsが得られます。後は英語を読めばOKです。

終了後、%bとか使えばちゃんと最後まで出るよーとか聞いて面白かったです。

【Easy/OSINT】Doctor yellow (76.77点 13時15分)

合格発表日を調べると、撮影日が2024/3/9だとわかります。このときのドクターイエローのデータを調べるとこんなものが

夕方なので4~6時と予測すると、東京の近くかな〜という気がします。でも写真的に街のど真ん中ではなさそう。神奈川かな〜と思いながら東京方面から西にGoogle Mapで川を探すと、あります。

ここの座標でFLAGを作れます。
実は、これ画像検索だけで通るらしいです。そんな...

【Easy/Reversing】Just reversing? (106.00点 14時03分)

Cのコードが貰えるので読みます。どうやら、FLAGの各文字に対し、4bitづつに分けてひっくり返しているみたいです。ってことは同じことをもう一度すれば戻ります。
Cで書きます。が、適当にやると符号がついてしまいます。しょうがないので、char→intの変換を手で書きました。ひどい...

普通に負になったら256を足す、で良かったらしいです。

【Easy/Web】Let's buy some array (99.02点 14時10分)

ソースコードを見ると、脆弱性しかなさそうなeval()が存在して笑います。適当にgetenv()を送りたくなりますが、用意されてるページからは数字しか送れません。Postmanで送り込むとフラグが帰ってきます。

【Easy/Reversing】Number Guesser (133.09点 14時19分)

バイナリなのでデコンパイラに突っ込みます。

"c decompiler" で出てきたやつ ↓

uintなので全探索したい気持ちを押さえつつ、よく読むと一文字づつ確認しているゾーンがあるので、これをasciiコードとにらめっこすれば答えが出ます。

【Easy/Web】Read Novels (50.00点 14時22分)

パスを錬成して覗きに行く実装なので、../を使うと答えが表示されます。

【Easy/Forensics】white has much information (125.13点 14時30分)

名前からしてWhitespaceかな、と思いながらAtCoderのコードテストに放り込んでもうまく動きません。Stegsnowなるものを知りやってみても違いそう。結局、Whitespace→Textみたいなサイトに放り込んだらできました。

【Easy/OSINT】leaving (174.09点 15時00分)

新幹線が停まる駅で熱海行きか、と思いながら調べ、有名な駅名を目grepすると浜松駅が出てきます。あとは時刻表を調べるだけだ〜、と思うとなぜかすでに終点にいます。戸惑いますが、折り返しかな〜といい感じの時間に出る反対方面の電車を調べると合ってました。

【Easy/Forensics】Register (289.68点 15時45分)

pcapngはパケットキャプチャと知っていたので、wiresharkを入れて見てみます。HTTP通信なら勝ちだったのですがUSBで悲しみます。USBメモリかな〜と思いながらググるとどうやらキーボード入力っぽいので、変換テーブルを探しに行きます。

US配列のIDはいっぱい出てきますが、JIS配列がなかなか見つからず... 見つかってもとてもめんどくさい... という感じでした。おもしろ〜

ちなみにこれが一番高得点でした。.pcapngに反応できなかったのか、USB通信に気づいて諦めたのか、キー追うのがめんどくさすぎて諦めたのかわかりませんが、どこかで躓く人が多かったのかな?

【Easy/OSINT】Great view (146.27点 16時06分)

画像検索で「卯辰山公園見晴らし台」だとわかります。ググると「蓮ノ空女学院スクールアイドルクラブ」というのが出てくるので、作問者にプレイヤーがいるのかな、などと思いながらググります。
正式なリリース日時があまりわからず困ったのですが、公式ページのアナウンスにありました。第二次メンテ終了時刻が正式リリース日時なんですね。

【Medium/OSINT】Patlite (196.6点 16時22分)

どこかの屋内のバス停? と思いますが、そんな条件じゃわからないのでゆりかもめに注目します。(東京にわかすぎてゆりかもめが交通手段であることを知らなかった)
バスの行き先が渋谷だな〜と思いながら、でもヒントもないのでゆりかもめの駅を端から見ていきます。たいてい、駅が上空にぽつんとあってこんなに大きな屋根はないので、大きい駅にたどり着くまで続けると新橋駅に当たります。
ここでストリートビューすると、なんか青い壁+シャッター+ゆりかもめ施設が見当たるのでここで確定です。

このあたりでご飯(朝? 昼?)を食べます。

【Newbie/PPC】About half (10.00点 18時38分)

ここまでずっとCTF問題を解いていましたが、この時点で競プロ問(PPC)を解いているであろう人たちと同じくらいの点数が取れていたので、いいね〜と思いながら競プロへ移ります。

言われた通り、 $A \times 2 > B$ または $A < B \times 2$ を満たせばNo、そうでなければYesです。

【Newbie/PPC】Compound World (10.00点 18時44分)

10点にしては難しそう。でも、 $N \leq 50$ なので、できる文字列は最大2500個しかないです。
なら大概の計算は間に合うな、という感じなので、全部作ってsetに放り込めば、勝手に重複を削除した個数が出てきます。

【Easy/PPC】CPC To F (174.09点 19時08分)

パット見難しそう。でも、前から貪欲にCPCTFを数えたり作ったりするのが最適だな、と思います。なぜなら、仮にスキップしても何も嬉しいことがないからです。
でも、 $N \leq 5 \times 1 0^{5}$ と大きめです。C++のstringのreplace(長さが変わる)の計算量がどのくらいなのか知らなかったので、連結リストを自分で実装して、CPC→Fの置き換えを「後ろ3つを削除して一つ追加する」みたいにしました。
結果、セグフォしまくるしWAとTLEが祭りになるし大変でした。

【Easy/PPC】Time is Money (244.76点 20時29分)

どう見てもグラフの問題なんですが、それだけの問題ではなさそうです。道の通行にかかる時間に加えて、通行料がかかり、またそれを稼ぐ時間も必要です。
こういう問題では、基本的に「必要になったときに稼ぐ」ではなく「必要になったときに稼いでいたことにする」とするとうまくいくな、と思いながら考察すると、辺のコスト(かかる時間)を $T_{i}$ ではなく $T_{i} + \frac{C _{i}}{X}$ にすれば良さそうです。つまり、通行料を値段から時給換算して時間にするわけです。
でもこのダイクストラだと浮動小数点誤差でWAしてしまうので、整数範囲でやるために $T_{i} \times X + C_{i}$ とします。これだと、辺のコストの単位が円になる感じですね。
こうして構築した無向グラフに対してダイクストラを実行すればACです。

【Easy/PPC】Old Maid (191.89点 20時45分)

なんかややこしそうですが、結局のところ、「pの中から、一番最後以外で最も小さいものを探す」→「そいつとその次の要素をまとめてqの末尾に放り込む」→「以下無限ループ」が理論値だとわかります。
この、2つ除く、という操作がstd::vectorでは遅そうなので、これまたlistを自前実装します。(さっきから自前実装しかしていませんが、これはstd::listの使い方を知らないからです)
あとは↑をやると答えが出ます。
ちなみに、なぜ問題名がOld Maidなのかはまだよく分かってません。(英弱)

このあたりで、風呂に入ったりご飯を食べたりしたはずです。AtCoder Beginner Contestが開催されていたらしいですが参加しませんでした。

【Easy/PPC】Balanced Choice (211.42点 00時27分)

日付をまたいでしまいました...
ナップサックに見えますが、なにか設定が追加されています。うーむ困るなあとなりますが、 $W \leq 5000$ なので $O (W^{2})$ が通りそうです。つまり、2種類のタイプそれぞれに対してDPをして、あとは最悪でもそれぞれのWを全探索すれば答えが出そうです。
ナップサックDPの実装でミスをしまくってしまい、時間がかかった...

【Medium/PPC】Car Flow (270.5点 00時47分)

配列から新しい配列を作る、というのを繰り返して、そこからなにか計算した値が収束するのでそれを求めればいいようです。見たことのある式でもないため、実験かな〜と思いながら考えます。
まず、テストケースがとても弱い1つしか提供されていません。ここからも実験の香りがします。
どうやら[1,0,0]も[0,1,0]も[0,0,1]も $\frac{1}{3}$ になりそうなので、適当に $\frac{1 の個数}{N}$ なのでは? と思って提出します。

思ったよりACが多くて驚きです。
ランダムに色々出力するテストを書くと、例えばこんなのがあります。

[0, 1, 1, 1, 1, 1, 0]
[0, 1, 1, 1, 1, 0, 1]
[1, 1, 1, 1, 0, 1, 0]
[1, 1, 1, 0, 1, 0, 1]
[1, 1, 0, 1, 0, 1, 1]
[1, 0, 1, 0, 1, 1, 1]
[0, 1, 0, 1, 1, 1, 1]
[1, 0, 1, 1, 1, 1, 0]
[0, 1, 1, 1, 1, 0, 1]

数えると $\frac{2}{8}$ ですね。さっきの考え方だと $\frac{6}{8}$ なのでWAになります。ん...?
ここで、一旦最初の方法で1の割合 $p$ を計算して、もし $\frac{1}{2}$ を超えていたら $1 - p$ が答えになるようにして提出してみます。
するとなぜかACが出ます。意味がわかりませんでしたが、解説を読んで感動しました。

【Easy/OSINT】Dokoda? (255.09点 01時15分)

解けそうなのがなくなったので競プロをやめ、CTFへ遊びに行きます。

Wifi選択画面のスクショです。fukushinというSSIDが怪しいですが、検索して出てきた店の住所を入れてみてもうまくいきません。
過去のCTFでこういうのないかな、とググるとこんなものが

そこに、こんなすごいサイトが載っています。

これは、ネットワークのSSIDなどの位置を検索できるという恐ろしいサイトです。これにfukushinといれると、福岡のあたりと東京にポツポツとありそうです。
福岡のアドレスを入れますがうまくいきません。複数あったらややこしいよね、とBSSID(MACアドレス)での検索に切り替えると、東京のただ1地点がヒットします。あとはズームして勝利です。

【Newbie/OSINT】omu-napo (10.00点 03時20分)

ひとつだけ解けていなかったNewbieがあるので戻ります。オムナポで検索してもほぼ何も出ないんですね...
ところが、ダウンロードしてexiftoolをするとGPS情報が入っています。(なんで一回目にやらなかったんだ?)
後はその近くでオムナポを売っていそうな店を探し、アイコンから英語名を読み取れば勝ちです。

流石にかなり深夜なので、一旦寝ます。

【Easy/Crypto】RSA Trial (191.89点 09時27分)

寝る直前に解法が浮かんだので、起きた直後に実践します。
この問題ではRSAを解きます。つまり、とてもでかい2素数の積を素因数分解します。

ただし、 $n = pq$ だけでなく、 $hin t = p^{3} + q^{3}$ も与えられています。
ここで、最初はnの桁数とhintの桁数が約2:3であることに注目し、pとqの値が近いと考えました。そのため、フェルマー法(?)とか、p,qの間にある数 $n$ から初める試し割り法とかをしてみます。
しかし、よく考えると、実際に計算した値は以下のようになります。

n^(1/2)        : 1519631... (309桁)
(hint/2)^(1/3) : 1548021... (309桁)

全然違いますね。そりゃあ計算が終わらないわけです。
その後に、 $pq = n$ と $p^{3} + q^{3} = hin t$ を、n, hintを定数とみてpq平面にプロットするとどうなるか見てみます。

これは...! この2つのグラフが交点を持つので、その交点が求めたい $(p, q)$ です。また、 $p < q$ とすれば、 $0 \leq p \leq n$ なのが見えます。しかも、この範囲では、正解の右か左かでグラフの上下が決まっています。つまり、二分探索で求められるというわけです。このようにして、正解のp, qが求まりました。

p = 135846035314254976465337709017892610972260952330473093190956787889003771348431653567864619921224683455565956235143491871628818050702825171995962027067211965328186579438000900782103909716822354229408148609438412069519249653673498370233311798811450530535438970823264957903264652220707394768488735600003751703147
q = 169992447630966858915888698252097138024929549454077071745755967876059342486814377573603835797671456147429214286974157576880880918312006854165708985792421413050688157226707305761122638977024328184158435239249537443610937944802531984738249044179408265418091660715862731719651393886894610221136158422905027929059

ここまでできたら後のやり方はネットにいくらでも落ちています。
$ϕ = (p - 1) (q - 1)$ として、 $m o d ϕ$ での $e$ の逆元dを求めます。すなわち、 $m o d ϕ$ での $e^{- 1}$ を求めればよいです。フェルマーの小定理(素数pに対し $a^{p - 1} \equiv 1 mod p$ が成立)を使えば、つまり $d \equiv e^{p - 2} mod p$ ですね。これは繰り返し二乗法で高速に求められます。
そこまでできたら、暗号文をcとして、 $m \equiv c^{d} mod n$ が元の文です。

ちなみに、グラフの交点を二分探索しなくても、ふつうに数式変形で求まるらしいです。悲しい...

【Easy/Shell】veeeeeeery long text (83.92点 09時33分)

なんかめちゃくちゃ長い文字(64文字が100000行)が与えられるのでフラグを探します。
最初、100000個の暗号なのかと思っていろいろ調べましたが、ただのgrepで良かったっぽいです。えええ〜〜 (最初にgrepしましょう)

【Easy/Pwn】veeeeeeery long text (26.82点 13時21分)

文字列に\0を紛れ込ませて文字数をごまかし、リターンアドレスを書き換えるように24文字くらい先にメモリアドレス\x89\x12\x40\x00を入れるんだろうな、までは分かったのですが、細かいところがわからず... 解説全部開けました

【Medium/Forensics】which is true flag (204.07点 14時20分)

証明書関係かと思いながら見たけどよくわからなかったので、ヒント2まで開けました。最初から適当なファイル2つのdiffを取っておけばよかった...
trap.jpのIPアドレス(Aレコード)はメールのIPとは違うんだろうな〜、と一応調べてgrepで存在しないことを確認。そのあと、なんかメールのIPを表示してくれる謎サイトに叩き込んで、grepで答えが出ます。

【Medium/OSINT】Forbidden Code 1 (262.69点 14時30分)

メールアドレスからいろんなアカウントを探してくれるツールを探してきて、これを使います。

これでGoogle Calenderのアカウントが見つかるので、ここのイベントの概要欄からフラグの部分①とTwitterのアカウントがわかります。そこで何やら怪しそうな会話をしていますね...
Twitterのbioからフラグの部分②も
Twitterアカウントのidをググるとredditが出てくるので、redditのプロフィールからフラグ③が見つかるはずです...が、これを見落としてForbidden Code 2用のRSA暗号を解いていました。
ヒント2まで開けた後Forbidden Code 2の問題を見て違和感を感じ、見直したらありました... もったいない...

ちなみにForbidden Code 2は解けなかったのですが、途中までできたので供養しときます。

なんとこの問題、よく探すと素数の一方pが得られます。もちろんn、e、cはあるので、ぱっぱと復号するとI hid something in the prime numbers. :Dという文字列が得られます。
よくわからないのでヒントを開けると、おそらく違法素数の話です。となると、pまたはqを2進数に変換してファイルに書き込むと圧縮ファイルか実行可能ファイルか文字列か何かになると思われるのですが、残念ながらわからず...

さいごに

全体ランキングを見てみると、CTFも競プロも最強の人々がいっぱいいて感激しています。まずは競プロつよつよになりたいので頑張ります!
運営の方々、大量の面白い問題、ありがとうございました!!