feature image

2024年4月28日 | ブログ記事

新入生の CPCTF2024 Writeup

こんにちは、新入生の「てぃだ」です。

この度、CPCTF2024に参加してきたので、それについて少しだけ書こうと思います。

CPCTFって?

簡単に言うと、「CTF (CatchTheFlag) + 競プロ」で競う大会です。

公式の紹介記事もあるのでぜひ読んでみてください。↓

CPCTF2024を開催します!
CPCTFとは 新入生のみなさんに競技プログラミング(Competitive Programing)とCTF(Capture The Flag)を体験してもらうイベントです。 新入生の中で上位の成績を残した方向けに賞品も準備しております!!!また、初心者の方でも解けるような問題や、十分狙えるような特別賞も準備していますので気軽にご参加ください! 東工大の新入生を主な対象としたコンテストですが、参加自体はどなたでも可能です。歯ごたえのある問題も準備していますので腕に自身がある方の参加もお待ちしております! こちらのリンクから登録することが可能です!!! 競技プログラミングとは 競技プログラミングとは、一定の条件の入力が与えられて、それに対して指定された条件を満たす出力を返すプログラミングを書く競技です。コードを書く技術や、アルゴリズム、数学の能力の向上にもつながります。CPCTFでは、PPCという問題ジャンルとして出題されます。 traPには競技プログラミングを主な活動内容とする班であるアルゴリズム班が存在しています。アルゴリズム班の詳細は以下の記事をご覧ください!!

About Me

解いた問題

解いた問題とその解法的なものを、解いた時間順に載せておきます。

数日経ってすっかり記憶が吹っ飛んでしまったので、憶えている範囲でしか書けませんが、ご容赦ください...... 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最後の CPCF に変換したときの CPCTF の個数の最大値。
  • count[i][1] := 〃 最後の CPC を変換しなかったときの CPCTF の個数の最大値。

という定義をしてDPを行いました。

このような定義にしたのには理由があり、隣り合う CPC...PC の間の文字によって以下のような条件分岐をする上で都合が良かったからです。

  • 間の文字が T だった場合
  • TF% だった場合 (%CPC...PC を含まない任意の文字列)
  • 上記以外の場合

これで実装は終わり......ではありません!まだ重要な部分が残っています。

それは「 CPC...PC の中で PC が何回繰り返されているか」です。

これが3回以上の場合は、先頭の CPCF に置き換えても末尾の CPC に影響はありませんが、1回または2回の場合ではそうはいきません。

これを考慮して実装することで、ようやくACが得られたのでした。

(実は、この考慮を忘れて3回ほどWAを叩き出しました......)

実装: https://yukicoder.me/submissions/975638

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 しました。

恥ずかしながら、コマンドを1ピコメートルも知らない人間なので、普通に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班良いかも……!!」ってなってます。

ここまで読んでいただきありがとうございました。

tidus icon
この記事を書いた人
tidus

この記事をシェア

このエントリーをはてなブックマークに追加
共有
記事一覧 タグ一覧 Google アナリティクスについて 特定商取引法に基づく表記