【CPCTF23】純粋培養競プロerはCapture The Flagの夢を見るか?【writeup】

4 月 26 日に開催された CPCTF23 に参加した結果、当初の想定よりいい結果が出せたので書きます。

スペック

競技プログラミング:

6 年ほど前から、ゆるーく続けています
約 1 年休止していましたが、受験終わったので復帰しました
AtCoder 黄色、JOI 本選

CTF: CPCTF 前夜に picoCTF で数問解いたくらい

Linux を普段使いしていますが、ネットサーフィンと競プロくらいしかしないので詳しくないです。

意気込み

CTF 何もわからないし競プロも復帰したてなので、競プロの問題をそれなりに解ければいいかな。

結果

4118.41 pt (7 位、新入生 3 位)
うおおおおお!! (なんで？)

問題ごとに考えたこと

難易度 NEWBIE はチュートリアルみたいな感じでヒント読めばできるので省略です (作問者、ごめん...)。ジャンルごとに行きます。

Reversing

Linux の実行形式ファイル(Windows の EXE みたいなもの)を解析します。ちょっぴり難しめです。

~~え、トップページに説明があるのに、1 問も出ないなんて...~~

Binary

トップページに説明がないのに存在する謎ジャンル (内容的に考えると、Reversing から名前変えたのかな)

EASY - passcode

Hint2 を見て、ASCII コード表とにらめっこすると解けます。
今考えれば Hint1 だけで行けた気もします。

Pwn

Linux の実行形式ファイルの脆弱性を突いて制御を奪ったりする問題です。一番ハッキングっぽいかも？初心者の方はとっつきにくいかも。

EASY - Big or Small

絶対値の大きな負の値を賭けて負けることで、その分持ち金が減るので大金持ちになれます。

EASY - overrun

私のような "高級" な人間には逆アセンブリなど不可能なので、Hint1 の C 言語コードを開きます。入力の長さが 50 を超えると壊れそうなので適当に長い文字列を入れてみると、Flag が出てきました。

PPC

競技プログラミングです。アルゴリズムの力で殴る問題です。競プロを体験したい人はこのジャンルを倒しましょう。

EASY - Find cpctf

よく読むと操作は一回しかできないので、どこを先頭に "cpctf" を作るかをすべて試せばいいです。

EASY - Floor Sqrt

$⌊ n ⌋ = a$ を固定すると、 $a^{2} \leq n < a (a + 1)$ です。

EASY - Geometric Progression Sum

$X^{k}$ は最後に各要素にかければよいので、区間加算一点取得のセグメント木で解けます。

EASY - Whisper Sucu

ウィスパー要素がわかりませんでした。元ネタはなんでしょう。

今いる頂点番号と時刻の偶奇をもって BFS するといい感じです。

MEDIUM - Digital Clock

いい感じに図を描くと、 $max (LCM (H, W), K + 1)$ が答えだとわかります。

MEDIUM - God Field

普通に bitDP です。と思ったら久しぶりすぎて部分集合 bitDP の実装が頭から抜け落ちていました。けんちょんさんいつもありがとうございます。

O(3^N) カテゴリーの記事一覧 - けんちょんの競プロ精進記録

MEDIUM - Max Min GCD

$k$ が大きいほうから解くとよさそうです。後ろで出てきた約数たちと今見ている要素の約数を比べます。

MEDIUM - Move Road

車を右に動かす代わりに Sotatsu 君を左に動かしましょう。Sotatsu 君が歩く (or とどまる) のと左に流されるのをセットで考えて BFS で行けます。

HARD - Hop Step Jump

べき級数みを感じたが解けず。

HARD - Lost Array

この問題の存在に気づくことが出来ませんでした。💩

HARD - Mex Max Matrix

わからず。問題名好きです。

Crypto

暗号です。数学が好きな人は楽しめる……？かも。

MEDIUM - Misuse

わからず。

MEDIUM - Simple

数学ゴリゴリ感があります。わからず。

Shell

Unix シェルの知識や技術を試す問題です。Unix を触ったことがなくても、調べながらなんとかできる問題も多いです。

Chu! NEWBIE 省略してごめん

Forensics

与えられたファイルをくまなく調査する問題です。求められる知識は広いですが、Google 先生が強い味方になってくれるでしょう。

Chu! NEWBIE 省略してごめん 2

Web

Web に関する知識や、Web アプリの脆弱性を突く問題です。ブラウザだけで解ける問題もあるので、手を付けやすいかも。

MEDIUM - admin watches you

コードを斜め読みしたら、なんか admin が含まれる文字列をよしなにする感じだったので、適当に ,admin でいいねしたら行けました。

MEDIUM - dictionary

SQL 何もわからないのに時間を溶かしました。結局 Hint3 を見て通しました。

MEDIUM - campaign registration

うーん、なにもわかりません。

OSINT

いわゆるネトスト（ネットストーカー）をする問題です。個人情報の特定みたいなことをします。

EASY - Shan shui

たぶん中国です。電話番号が書いてあるので、"中国市外局番" でググると、地名と市外局番と郵便番号を検索できるサイトが出てきます。

EASY - Dokoda? 1

画像検索してみたものの、似たようなイルミネーションばかりでわかりません。よく見ると左端にあるのは Panasonic のロゴなので、パナソニックセンター東京と予想できます (余談ですが、リスーピアは 2020 年に閉館してしまいました。寂しいね)。

EASY - Dokoda? 2

Google Maps で奥の東海工産を調べると一発。

MEDIUM - Dokoda? 3

国道 17 号と都道府県道 319 号の交差点です。国道 17 号が通っている都県で最もこの画像ぽいのは東京都なので都道 319 号との交差点を調べると、あたりでした。

HARD - handwaving

エアバス 332 と MAC アドレスが大事そうなことはわかりましたが、そこからが続きませんでした。Hint3 (答え) を見て提出。

Misc

上のジャンルに含まれないその他のジャンルです。

EASY - 1dayattack

私も Pixel 4a なので親近感がわきました。ちゃんとシステムはアプデしましょう。Hint2 まで開けてようやく解けました。

EASY - 2DCode 2

これはどう考えても QR コードなので、いい感じに隅の□を修復してあげたら読み取れました。

全体を通しての感想

当初は競プロだけできればいいや、と思っていましたが、結構全ジャンル楽しめたと思います。CTF 班所属の機運。
こんなにはっきりと得手不得手が出るものなんですね (Crypto と Web 苦手...) と思いましたが、Crypto はみんな解けてないので普通にむずいだけ説があります。
経験者なのに PPC - HARD が 1 問も解けなくて悲しいです (PPC だけ難易度高くないですか？と思ったが、私が Hint 開けていないからかも)。