InterKosenCTF writeup
はじめに
InterKosenCTF に参加しました。
@betit0919とチームを組ませてもらって結果は22位(正の得点91チーム中)でした!
CTF初参加ではありましたが、いくつかの問題は自力で解くことができ、CTFの面白さを知ることができて本当に楽しいコンテストでした。
ということで、書いてみようと思います。writeupを書くまでがCTF #InterKosenCTF
— ptr-yudai (@ptrYudai) 2019年8月12日
参加まで
CTFが何なのかも全くわからない状態だったのですが、@betit0919がことあるごとに誘ってくれるので、暇だしせっかくなら出てみようかなと参加しました。 思えば競技プログラミングもこんな感じで@betit0919に誘われ、沼にはまっていった気がします……。
一日目の夕方ごろに家まで行って簡単に解いた問題の説明を受け、CTFの雰囲気をなんとなく理解し、問題を解き始めました。
解けた問題
2人で解いた問題に関してはチームメイトのwite-up betit0919.hatenablog.com にも載っているので参考にしてください。
Hugtto!
概要
- 時刻を元に作った値をseedとした乱数(0-2)がある
- 乱数をもとに画像中のrgbのいずれかが変更されflagが埋め込まれている
解法
- flagが"InterKosen{"で始まるので一致する部分を全て挙げる
- 開始位置の差分からflag長を推測 (544bit)
- 544bitずつに分けてrgbの値を全て足す(544bit*1400ほど足しました)
- flagで確定している01の分偏るのでそこからflagを逆算
書いたコードは こちら (なんどもバグらせて@betit0919に助けてもらいました笑)
感想
544bitで区切ったところまでは不安でしたが、足し合わせたときに綺麗に偏って勝ちを確信しました(なおそこからビッグエンディアンであることに気づかずしばらくハマる)。 個人的に解いた中で一番面白いと感じた問題でした。
なお、 作者の想定解 は画像の生成時刻からseedを求める解法で、なるほど~ってなりました。
E_S_P
概要
RSA暗号の問題
- e, N は与えられた出力のテキストファイルからわかる
- 平文がyukkoという名の文字列とflagを足し合わせたものになっている
- yukko = "Yukko the ESPer: My amazing ESP can help you to get the flag! -----> "と長い
解法
こちらの非常にわかりやすいスライド を参考にすると、平文の上位bitがかなりわかっているので、Coppersmith's Attackが利用できる
こちらの非常にわかりやすいCoppersmith's Attack の参考実装 を元に実装すると、そのままでは答えが出ない
SageMathのドキュメント を元にsmall_rootsのパラメータを適当にいじると答えが出る
書いたコードは こちら
感想
解法自体は"ググリ力"という感じでした笑 実際には解けるまでに数時間かかっています。
この問題を解くにあたってRSA暗号とその攻撃方法などについていろいろと勉強しましたが、めちゃくちゃ面白かったです。
pascal homomorphicity
概要
- RSA暗号に似た暗号が c = (n+1)e (mod n2) で生成される
- e = key の場合の出力c_keyが与えられる
- こちらの入力したeに対し、長さが十分なら計算したcを返してくれる
解法
- (n+1)e (mod n2) = en +1 であることを利用
- 初めのc_keyは c_key = key * n + 1 を満たすので、c_keyをそのまま投げれば、n * (key * n + 1 ) (mod n2) = n より、nが手に入る
- c_key = key * n + 1 からkeyが求まる
感想
解法自体はとてもあっけないのですが、本質である c = en + 1 に気づくまでにありえないくらい時間を溶かしてしまいました。RSA暗号だと勘違いしてRSA attack を調べることに熱中してしまったのが敗因です笑。Common Module Attackを実装して2組の(e,c)から平文を求めたらn+1が出てきて(当然)、方針の間違いに気がつきました。
この問題、平文の部分を隠されても解ける?のでその方が面白かった気がします(ただこれは難しくなりすぎるかもしれません)。
fastbin tutorial
概要
- 指定のサーバにつなぐと簡単なインターフェイスが与えられる
- 操作は、1 malloc, 2 free, 3 read, 4 write ができ、fastbinと変数ABCのアドレスが表示されている
- flagが格納されているアドレス(前半部はランダム) が与えられる
解法
fastbinについて調べるとdouble free attackというものが出てくる
- 1A 1B とA, Bをmalloc
- 2A 2B 2Aと交互にfreeするとAをdouble freeできる
- 1CとCをmallocするとAにつながるので4Cでアドレスを書き込む
- 1Cでmallocしていくと書き込んだアドレスにつなげる
- 3でreadする
感想
まともにやったように見えますが、アドレスの書き込み方が良くわかっていないので、実験を繰り返して、ASCIIで表示されることがわかり、ASCIIで入力できるアドレスが来るまでガチャをするなどしました。
まとめ
InterKosenCTF は、CTF初参加でも楽しむことのできるすばらしいコンテストでした~!pwnの2問目のshopkeeperもあと少しで解けそうだったので復習しようと思います。
暗号や脆弱性をついた攻撃、リバースエンジニアリングなどハッキングっぽいことができてわくわくしました。知識は圧倒的に足りていないので、勉強して他のCTFにも参加していきたいです。