CPCTF 2023 writeup

参加しました。22B ですが編入生なので新入生です。（編入生でなくても traP 新入生なら新入生かな）
チーム cunitac で出ました。メンバーは cunitac で、計 1 名です。cunitac が新入生なので新入生チーム扱いになります。

新入生チーム内での順位は 2位でした。やったぁ！

とりあえずメモしておこうと思って書いたら問題が多くて疲れちゃったのでそのままでいいか、という感じになっています。ので、わりと乱雑です。

感想

最後に書くと最後になっちゃうので最初に書きます。

たぶん CTF と名のつくコンテストに出るのは初めてなのですが、思ったより PPC の割合が高く、びっくり。でも、CTF パートもけっこう楽しかったです。うれしい！

最初に書くほどの感想ではなかったかもしれません。

全体を通して

正答を提出していない問題：

Misuse (Crypto, Medium)
Simple (Crypto, Medium)
dictionary (Web, Medium)
Mex Max Matrix (PPC, Hard)
campaign registration (Web, Hard)

PPC は Rust でやりました

Newbie

ヒントが無料だったのでPPCとnetcat以外は全部開けてから考えました

2DCode 1 (Misc)

Dot Code といいますと書いてあるので、検索します

Count Coins (PPC)

書いてある通りに操作します。saturating_sub が好き。

Entrance to the Crypto World (Crypto)

適当な Web 上のツールで適当に試して解いた

Transfer (PPC)

$min {A + B, C + D}$

Tube (OSINT)

Xinxiu Chiwan で検索！

easylogin (Web)

ヒントには ' OR 0=0 -- と書いてあるが、なんかダメらしいので、勘で ' OR '' = ' と書いたら、当たり

investigation (Forensics)

必要な画像は2枚なので、探す。

netcat (Shell)

書いてある通りにやる。

welcome to CPCTF (Misc)

トップページを読む
Visualizer を探す
Discord がよくわからなかったので残りを勘で当てる

Easy

Shan shui (OSINT)

電話番号が書いてあるので、市外局番から郵便番号が特定……できないが、少ないので全部試すか～、をしたら、一発で当たった。運がいい。

1dayattack (Misc)

なんかそんなニュース見たな、と思って検索したら引っかかった、こわいねぇ。

2DCode 2 (Misc)

QRコードっぽくないところを適当に消すと、いける

Big or Small (PWN)

int なので、負の賭けをして負けることで負の損を出すことができる

Dokoda? 1 (OSINT)

Google Lens をするとだいたい特定できて、ちょっとずらすと当たる

Dokoda? 2 (OSINT)

調べても当たらなかったのでヒント1を開いたが、調べろと書いてあったので、根気強く調べたら当たった

Find cpctf (PPC)

windows(5) して、それぞれほしい $A_{i}$ たちを数えて、どれかいけたらいける

Floor Sqrt (PPC)

$⌊ n ⌋$ ごとに処理すると、いい

Geometric Progression Sum (PPC)

$D_{i} = A_{i} - X A_{i - 1}$ を管理することを考えると、各操作で $D_{L_{i}}, D_{R_{i} + 1}$ しか変化しないし、 $A_{i} = D_{i} + X A i - 1$ によって順に復元できる

Whisper Sucu (PPC)

頂点番号と時刻の偶奇の組を頂点としてBFS

overrun (PWN)

逆アセンブルして ChatGPT に見せると、SIGSEGV でなんかやるらしいので、いっぱい書いてみる

passcode (Binary)

逆アセンブルして ChatGPT に見せると、微妙に間違えた答えを返してくれるので、どこに答え書いてあった？ときいて、自分で読む。

Medium

Digital Clock (PPC)

紙に書かないとダメだな～と思って一旦スルーしたが、紙に書いたらわかった。時間ボタンを押す回数を $H$ で割ったあまりをどう固定しても $W / g cd (H, W)$ 個の時刻をぐるぐるまわるので、 $min {K + 1, H W / g cd (H, W)}$ になる。

Dokoda? 3 (OSINT)

数字を読み取るのが不可能でヒントを全部開いた。読めてもそこそこしんどくない？

God Field (PPC)

dp[耐えた攻撃の数][壊れた防具の集合]

Max Min GCD (PPC)

なにもわからなくてヒント1を開いた、ヒントの後半の言いたいことはいまいちわからなかったが、前半のおかげで解けた。 $C_{k}^{'} = max_{j} g cd (A_{k}, B_{j})$ が求められればよいが、 $A_{k}$ の約数のうち、 $⋃_{j \geq k} (B_{j} の約数)$ に含まれる最大のものが $C_{k}^{'}$ になる。BTreeSet だと TLE で、HashSet だと通ったが、Vec<bool> でよかったな、と、思った

Misuse (Crypto)

ヒント全部開けたが、なんか難しそうなのでパス！

Move Road (PPC)

適当に辺を張って DFS すればよい

Simple (Crypto)

ヒント2つ開けて、紙に書かないとダメだな～、と思って、紙に書くのを忘れていた

admin watches you (Web)

ド終盤に開いたのですぐにヒントを全部開けたが、時間があれば普通に解けたと思うし、時間がなくてもヒント2つで解けたのではないかという説がある

dictionary (Web)

ドド終盤に開いたのですぐにヒントを全部開けたが、開け終えたら終わった

Hard

Hop Step Jump (PPC)

なんか形式的べき級数っぽいな～、形式的べき級数のことな～んも知らないけど。と思いながらわからないのでヒントを2つ開けたら、当たっていたので真面目に考えたら、解けた。うれし～。以前に OEIS で母関数を見つけて解くテクを実装したことがあって、よかった。

Lost Array (PPC)

ノーヒントで、解けた。 $(A_{1}, A_{2}, \dots, A_{K}) \mapsto A_{M}$ は線形写像で、行列の冪を使って高速に計算できる。結局あるベクトルと $(A_{1}, A_{2}, \dots, A_{K})$ の内積が $0$ になればよいということになるので、その「あるベクトル」の一番うしろにある非零要素だけを使うと辞書順最小が達成できる。

Mex Max Matrix (PPC)

ヒント全部開いて、へ～、となったが、時間がなかったのでパス

campaign registration (Web)

読んでいません

handwaving (OSINT)

ヒント1つ開いて考えたが、わからなかったのでヒント全部開いて、そこにあった答えを書いた。