CPCTF2024 に参加したよ！楽しかった～ writeup

こんにちは、しょぼんです。CPCTF 2024 に参加して、全体 3 位でした。楽しかったです。来年も参加するか、それとも作問をするか、迷いどころです。

昨年は PPC（競プロ）の問題を何問か出しましたが、今年は作問に参加せず、競技に参加しました。今回は CPCTF が 30 時間ありましたが、午後3時から翌日の午前11時までの20時間ほぼぶっ続けでやりました（途中にあったABCは出ました）。生活リズムが崩壊しました。この記事も午前5時半に書いています。

この記事では自分がどうやって問題を解いたかを書きます。

自分について

CTF

CTF はあまり参加したことがありません。

CPCTF2021(2021年4月) と setodaNoteCTF(2021年8月) には参加して、かなり思い出に残っています。CTFってなぜか独特の雰囲気があって、それがいいんですよね。解いていると不思議な気分になります。

競プロ

競プロ勢です。2020 年 2 月に始めて、今 AtCoder 黄色（2340）です。

CRYPTO

[Newbie] Substitution

暗号文が与えられています。最後に ETEIB{...} があり、これは CPCTF{...} に対応するように見えます。同じ E が同じ C に対応していることから、「単一換字式暗号」と呼ばれる暗号だと察しました。

その後は、まず Cpvv muzp! を Well done! とエスパーし、26文字すべての対応をメモしていきながら復号しました。

[Easy] RSA Trial

hint は $p^{3} + q^{3}$ です。いま $n = pq$ であることから、

p^{3} + q^{3} = (p + q)^{3} - 3 n (p + q)

と変形できます。 $p + q = x$ とおけば、

hint = x^{3} - 3 n x

となるので、符号の正負で二分探索して $x$ の値を特定し、 $p, q$ を復元しました。

この $p, q$ が分かってしまえば RSA 暗号は解けてしまうので、あとは復号して解くことができます。

FORENSICS

[Easy] Register

pcapng 拡張子を知りませんでしたが、昔インストールした wireshark が紐づけていました。データが少ないことに気づきます。

Info に書いてあった「URB_INTERRUPT ctf」と調べたらたくさんヒットして、キーボードの入力を記録したものだと判明しました。その後、「HIDのキーコード表」でヒットしたサイトのキーコード表を見ながら flag を復元しました。

[Easy] white has much information

何も書かれていないと思いきや、反転させるとなにかの情報が含まれていることが確認できます。

Python で文字コードを確認したところ、奇数行目には文字コード 32 (半角スペース) と 9 (Tab) の $2$ 種類で構成されています。

これを $2$ 進数表記された数字であるとエスパーし、文字コードに治すと flag が出ました。

[Medium] which is true flag

メールが $10000$ 件あり、どれも送信元の IP アドレス、flag だけが違いそうでした。

まず zip に入っていた「__MACOSX」は関係なさそうでした。また、IP アドレス確認サイトで確認した trap.jp のIP（本物）だけをフィルターしても引っかかりませんでした。emlファイルの容量が最も大きいものを取り出しても全部同じ。

本物は他の偽物と何かが違うのではないか？と思って「メールに◯◯が含まれてない」という条件でいろいろ試したところ、本物だけ時刻が「15:29:06」ではなく「15:07:51」であったのでここで引っかかり、特定できました。

実際は trap.jp のメールの IP アドレスがあるので、それをフィルターするのが想定解らしく、もし時刻が全部同じなら詰んでいるところでした。

MISC

[Easy] turning over

ファイルを blender で開いたら強制終了したので、 blender をまずアップデート。そしたら開けたのですが、真っ白い板があるだけです。

このボタンを押したら flag が出ました。

1 か I か分かりませんでしたが、ありえる8通りをすべて試して正解しました。

[Hard] Forbidden code 2

Forbidden code 1 (OSINT) の続きで、そこの登場人物がなにやらRSA暗号で遊んでいる様子。

問題を解くキーは myaomyaohit の投稿にある $(b, n) = (41643, 11)$ というもの。RSA 暗号とは関係なさそうで意味不明！

ヒント 2 まで開けて、これが違法素数を作るときのパラメータ $b, n$ であることが分かりました（登場人物が legal とか illegal とか言っていたのは伏線だったんですね）。残りのパラメータ $k$ を $p, q$ から求めました。そして、違法素数のように、 $k$ をファイルとして復元すると、 $2$ つの zip ファイルと判明しました。

中は brainfxxk のコードだったので、 AtCoder のコードテストにかけてみると flag が出ました。

OSINT

[Newbie] mokomoko

Google Lens で検索すると、出てきました。

[Newbie] omu-napo

ファイルに位置情報が入っていました。「ファイルに位置情報が入っており、危険。」（画像ヤバい度ランキング）というのは結構有名だと思います。

[Easy] Doctor yellow

Google Lens で同じ位置・同じ向きで取った写真を載せたブログがたくさんあったので、そのブログ＋Google Maps を見て位置を特定しました。

[Easy] Dokoda?

Wifiの名前に「fukushin」とあったので、そこに注目していろいろ調べましたがヒットしませんでした。

wifi の情報を集めているサイトがあるのでは？と思い「wifi database」と検索したら WiGLE というサイトがヒットしたので SSID を入れたら場所が出てきました。（思えばかなり奇跡的だったかもしれない）

[Easy] leaving

解像度が大きい駅のホームの画像が与えられています。表示の「10:25, 普通, 当駅始発, 熱海行き」と階段の広告の看板にある「静岡」などで、画像の場所が「浜松駅」であると断定しました。

浜松を 10:25 に出る熱海行の普通電車があるので、「駅探」というサイトで調べると、13:04 に熱海に着くそうです。

熱海に着いた電車はまた浜松に戻ってくるのでは？と思い、13:33 始発の浜松行き普通電車と個体が同一であるとエスパーしましたが、はずれ。実際は 13:14 の豊橋行き普通電車でした。（違うことあるんだ）

[Medium] Forbidden Code 1

与えられたメールアドレスが gmail でした。自分の場合、自分のメールアドレスを打つと紐づけられた本名が出てくるので、これもそのパターンなのではないかと思いましたが、情報がなさそうでした。

「gmail OSINT」で検索すると、そのためのページ Gmail OSINT - ActiveTK.jp があるのでそのメールアドレスを掛けてみると、イベントを作っていることが判明します。

内容をダウンロードしてみると、flag の一部と、twitter アカウントが発掘できました。twitter アカウントにも flag の一部分が書いてありました。しかし、flag はまだ完全ではありません。

誰かと会話して「別のところに投稿します」と書いてあったので、myaomyaohit で検索したら reddit がヒットしました。

Reddit の中に残りの flag が書いてあり、完成しました。

[Medium] Great View

Google Lens にかけるとラブライブ「蓮ノ空女学院スクールアイドルクラブ」の聖地と判明します。公式サイトのお知らせ情報を見て正式リリース日時が分かりました。

[Medium] Patlite

画像のバスをよく見てみると、「？06」渋谷駅　と読むことができます。都営バス06は確かに渋谷が終点なので、バスが特定できました。

バスのルートは決まっているので、バスが必ずここを通るということが分かります。都営バス06の新橋～渋谷までを撮影した動画が Youtube にあり、見てみると同じような場所があったので場所が特定できました。

[Hard] Passing

謎の駅を写した動画（と結局無関係の別の動画）があります。同じ動画投稿者の別の動画から、 twitter が得られます。

twitter の投稿を見てみると、鍵アカウントの友人との会話が見えます。でも「電車の時刻表が最近あまり変わってない」以上の情報は得られませんでした。

動画の個体の行き先は天竜峡行きで、飯田線と分かります。

右側には駅舎が写っています。ここから大量にある飯田線の駅を全探索して「三河槙原駅」であることが分かりました。

天竜峡行きの電車は7時7分、9時43分、14時54分、20時7分のみです。20時7分はありえないとして、残り3択。偶然にも左に電車が泊まっていました。これは現在の時刻表では 14時54分でしかありえないので、時刻が特定できました。

残りは日時ですが、右側の駅舎に柵がかかっている（2021年以前はない？）のと、人々の服装が軽い長袖で、寒い・暑い時期ではないことから「2021年以降の春か秋」であると断定しました。そこから一番ありえそうな日時から全探索で flag を投げていくと当たりました。

PPC

[Newbie] About half

問題文に書いてあるとおり、2通りの条件を判定します。

[Newbie] Compound Word

$N$ と $∣ S_{i} ∣$ が小さいので、ありえるすべての文字列を集合に入れて、その集合の要素数を出力すればよいです。

[Easy] Balanced Choice

$d p [i] [j] [k]$ を、 $i$ 番目まで見たとき、タイプ $0$ の総重量が $j$ 、タイプ $1$ の総重量が $k$ のときの価値の総和の最大値、と考えましたがこれでは状態数が $500 0^{3}$ となり大きすぎます。

よく考えると、タイプ $0$ はタイプ $1$ とは相互に影響を与えないため、別々に $d p 1 [i] [j]$ : $i$ 番目まで見たときタイプ $0$ の総重量が $j$ 、 $d p 2 [i] [j]$ : $i$ 番目まで見たときタイプ $1$ の総重量が $j$ として DP を計算し、あとで $500 0^{2}$ 通りの $(i, j)$ に対して $d p 1 [N] [i], d p 2 [N] [j]$ を見ればよいです。

[Easy] CPC To F

いま見ているところからの $3$ 文字が CPC、そしていま見ているところより左の $4$ 文字が CPCT となっていたら、貪欲に今の場所の CPC を F に変えていいだろう、と思い書いたら AC しました。

[Easy] Old Maid

AtCoder に Young Maids という同じような問題があったので同じコードを出したら WA が出ました。

実際に問題文はおそらくここからコピーしていて、操作が「先頭に追加する」から「末尾へ追加する」に変更されているだけでした。結果として Yound Maids の難しい部分がなくなっており、「値の（順序付き）set」と、「位置の（順序付き）set」の $2$ つを使えば簡単に解くことが出来ます。

[Easy] Time is Money

街 $1$ で働く時間が多ければ、良い道は使えるけど働く時間で時間を食う。しかし街 $1$ で働く時間が少なければ、良い道が使えず、時間を食う場合がある。そういう葛藤があります。

そこで、「まず道を通って借金し、最後に街 $1$ で働いたことにしておく」という予定調和に思いを馳せると、全時間は「通った道のお金の合計： $c$ 、通った道の時間の合計： $t$ 」として、コストは $⌈ c / X ⌉ + t$ なります。もっと変形すると

⌈(c + Xt) / X ⌉

です。つまり、本当に問題文の名前通り「 $1$ 時間＝ $X$ 円」として解いて、あとで $X$ で ceil を取れば良いことになります。

ちなみに ABC344-F にちょっと似てます。

[Medium] Car Flow

よく分からないので、実験してみます。そうすると、最初はどれだけ $1, 0$ 同士が詰まっていても、「できるだけ $1, 0$ がばらける」感じになることが観察できます。そのまま解答をエスパーしました。

結果とタイトルを見て、「車間距離を開けると渋滞が解消される」みたいな話を思い出しました。

[Medium] Power! or +1

答えの上界として、「操作 $1$ を $N - 1$ 回行う」ときのコスト $(N - 1) A$ があります。これによって、操作 $2$ の $k$ は高々 $50$ しか選ばなくてよい、ということが分かります。これである整数からの操作が有限個になりました。

操作 $3$ の $X \to X!$ ですが、 $X \geq N$ なら $X!$ は $N$ で割り切れるので確実に $1$ 回で済みます。あとは落ち着いて整理すると $X mod N$ だけが重要であるとわかるので、持つべき状態は「 $(X \geq N ?, X mod N)$ 」の高々 $2 N$ 通りです。

これらの状態に対して操作で遷移できる状態をすべて求めると、ダイクストラ法が適用でき、ACできました。

[Medium] String Swap Battle

$K$ を特定しないには何も始まりません。そして、 $K$ が与えられたとしてもどうやるか分からない……

サンプルを見て、いろいろな人に思いを馳せると、絶対に $K = 1$ となることが思い浮かび上がってきます。

$K = 1$ で勝つ人 $a$ が必ずいて、その人が $K > 1$ を宣言してしまうと、他の人に勝利を横取りされる危険があります。しかも、 $K = 1$ で勝つ他の人 $b$ に対しては、 $K > 1$ で $a$ が勝つなら絶対に $b$ も勝つ、ということで $a$ のスコアは $K = 1$ で最大になり、なおさら $K > 1$ を宣言する意味はありません。

あとは $K = 1$ の場合を解けばよい、すなわちある文字列に対して、隣接swapを $1$ 回行ったときの辞書順最小を求めればよいです。これはかなり罠があり、たとえば

aaabbccdec → aaabbccced: 途中まで辞書順最小の状態をキープしていたとき、操作する場所は途中である

や、

aaabb → aaabb: a, a をスワップすれば辞書順最小がキープできる
abcde → abced: もとは辞書順最小だが、どうやってもキープできず、仕方がないので後ろ $2$ つを swap する

というケースもあります。頑張ってなんとかACしました。

[Medium] Twisted Lattice

お絵かきしてみると、

コストはこんな感じです。よって、「自分の列と同じ」「自分の列と $1$ 列ずれてる」「それ以外」で場合分けすることができ、それぞれに対して頑張って（順序付き）set や平面走査などを用いてコスト最小の点を見つけることでACできました。

[Hard] Bicolor Pyramid

${1, 4, 9, 16, \dots, n^{2}}$ を用いて表現できる値を実験で求めてみると、十分大きい $n$ に対しては

表現不可能な値の集合が ${2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128, n (n + 1) (2 n + 1) /6 - 128, n (n + 1) (2 n + 1) /6 - 112, \dots, n (n + 1) (2 n + 1) /6 - 2}$ であることが分かります（これを調べると OEIS A001422 が出てきます）

また「 $k$ 段ピラミッドが作れるか？」には単調性があり、サンプルから $k \leq 2 \times 1 0^{6}$ がわかるので、決め打ち二分探索を行えます。鳩の巣原理より、「 $R - i$ が表現不可能」「 $B - (k (k + 1) (2 k + 1) /6 - i)$ が表現不可能」が同時に起きるのは高々 100 通りのため、 $i = 0, 1, \dots, min (R, 100)$ 程度やれば求まります。

しかし謎の WA が出ました。 $k$ が小さいときにバグっているらしいので $k$ が小さい場合は愚直な bit 全探索を採用するとすると、 AC できました。

[Hard] Permutation Adjacent Sum

${i, j}$ が隣り合う場合の数は、隣り合う位置 $N - 1$ 通り、隣り合う順番 $(i, j), (j, i)$ の $2$ 通り、そして残り $N - 2$ 個の値たちの順列 $(N - 2)!$ 通りです。よって、答えへの寄与は、 $2 (N - 1)! ∣ i - j ∣^{K}$ です。

$∣ i - j ∣ = t$ となる ${i, j}$ の組は、 $1 \leq t \leq N - 1$ なら $N - t$ 通りです。よって答えは

2 (N - 1)! t = 1 \sum N - 1 (N - t) t^{K} = 2 (N - 1)! {N t = 1 \sum N - 1 t^{K} - t = 1 \sum N - 1 t^{K + 1}}

です。前者の $(N - 1)! mod 998244353$ は埋め込みで、後者の $\sum_{t = 1}^{N - 1} t^{K}$ を計算するのは、[多項式・形式的べき級数] 高速に計算できるものたち - maspy の「 $\sum_{n = 0}^{N - 1} n^{k}$ の $k$ に関する列挙」の欄を見れば分かります。

以上で解けました。

PWN

[Newbie] Attack! Attack! Win!

与えられた chall.c を見てみると、入力を受け取るときに「入力がマイナスのときの場合分けをしてない」バグが見つかります。

適当に $- 2$ を入れてみると flag が出てきました。

[Easy] CPCT......

$4$ 文字しか入力が受け付けられず、「CPCT」までしか出ません。

そこで、「CTF C 文字列攻撃」で検索すると、 printf とかなら攻撃できるということが判明します。chall.c を見てみるとまさに printf だったので攻撃手法を検索しました。 %s %x などを打ってみるとうまくいきそうなので色々な文字を % の後ろにくっつけたら flag が全部出ました。

[Easy] The sky's the limit

このような問題は昔解いた記憶があり、「長い文字を入力するとバグって flag が出る」という感じでした。chatGPT に脆弱性を聞いてみるとバッファオーバーフローという名前がついているらしく、多分昔解いた問題もこれでした。

関数 win を呼び出すためにアセンブラを読んでみたり（アセンブリを読んでみよう(eiyaさん)が参考になりました）、chatGPT と協力してハッキング文字列を作ったり

しかし文字列長の場合分けのせいで exit が呼ばれてしまいうまくいきません。

かなり難しいので、「文字列長をうまくすり抜けられないか」という点でchatGPTに聞いてみると

答えてくれました。これが本当なら、逆に、最初に終端文字 \0 が入っていれば文字列長制限を突破でき、さらにバッファオーバーフローも起こせると思い、攻撃してみました。そうしたら、「Too Long...」と表示されずに Segmentation Fault を起こしたことから、うまくいきそうだということが分かり、あともう一歩というところまで来ました。

あとは頑張って試行錯誤を重ねて、 \x00\x00 ... \x00 (24個) + いい感じに攻撃 の文字列でうまくいきました。（ret命令のアドレスは偶然入ったので、かなり奇跡的）

なんとかヒントなしで解けましたがかなり難しかったです。