この記事はCTF AdventCalendarの-15日目の記事です
こんにちは。公式writeupっぽいやつは早く出しすぎると参加者が「じゃあ自分はwriteup書かなくてもよいか……」と思ってしまうのでしばらく経ってから出したほうが良いと思っているので寝かせていました。まだ書いていない人でこれを読んでいる人はぜひ運営へのねぎらいだと思ってwriteup書いてください。
以下は解説というよりは感想です。出題した問題はGitHubで公開してます。solverも入っているので詳しい解き方を知りたい人はそちらを見てください(あと解いた人のwriteupを読んだりしてください)。
- [crypto/warmup] simple signature (88 solves)
- [rev] Cake Puzzle (56 solves)
- [crypto] janken vs yoshiking 2(43 solves)
- [crypto/pwn] decryptyou (13 solves)
- [crypto] Iron Door (8 solves)
- 感想
[crypto/warmup] simple signature (88 solves)
なんか昔つくった問題なのでよく憶えていません……。昔なんかいい問題を作ろうと思ってがちゃがちゃやっていたときにできた何やっても解ける問題を拾い上げてきました。
kanonさんがwriteupにいいことを書いてくれてるんですが、”基本的に、公開鍵と秘密鍵は何か数学的な関連性が必要であるから解けないわけで、今回はが公開鍵にしか使われていないため、なんでもおk”です。適当に値を決め打ちしてそれで辻褄が合うようにすると解ける。
一見難しそうに見えて普通に数学やると解けるのでwarmupです。
[rev] Cake Puzzle (56 solves)
これは非常にシンプルな15パズルで、さくっとreversingしてさくっとソルバ拾ってきて解くだけです。
reversing何もわからないのに無理やり何か作ろうとして結局このあたりに落ち着きました。特に面白いことはないので、出したことは多少以上に後悔してます。
[crypto] janken vs yoshiking 2(43 solves)
janken vsシリーズ、または vs yoshiking シリーズです。これまでの作品はzer0pts CTF 2021に出題したjanken vs yoshiking, SECCON CTF 2022 Qualsに出題したjanken vs kurenaifです。jankenは本当に便利な題材で、手の種類が3通りしかないのでweakなパターンを作りやすいですよね。
さて、今回はyoshikingは上の5x5のランダムな行列に対しを計算してくれてがyoshikingの手です。はsmoothですが一般線形群では特に嬉しくないです*1。どうにかして離散対数問題を解いてを求めたいですね。
そこで一般にだねということを思い出してを取るとdeterminantは上の計算ですから、このdiscrete logはPohlig-Hellmanで楽に解けるのでじゃんけん勝ち放題という問題でした。
行列の冪乗が出てきたときに行列式を考えたりジョルダン標準形を考えるのは典型だと思っているのでもうひと工夫しても良かったなと思います。あと、janken vs yoshikingを作問したときもp-1が3を位数に持っているとか持っていないとかで非想定の解法を作ったのに今回もそういう解き方のことを失念してたのも良くないですね*2。憶えてたらはランダムに生成してたと思います。まあでもpがsmoothなことでmod pで考えたくなるという誘導にはなったので別に良いか。良いような気もします
[crypto/pwn] decryptyou (13 solves)
zer0pts CTF 2022に(ptr-yudaiが)出題したsignmeという問題は crypto + pwnの問題で、RSA-CRTによる署名時に一時変数を破壊できるので素因数分解できて……という問題でした。今回出題したdecryptyouはcrypto + pwnの問題でRSA-CRTによる復号をしてくれるのですが、pwn要素によって復号時に一時変数を破壊できます。
RSA-CRTにおける復号ではとしたあとgarnerのアルゴリズムでとしてを復元します。このときが壊れているとして
- であればとは同じ値になるのでとなり、garnerのアルゴリズムのの部分は0なのでが壊れていてもの影響はに届かないので復号に成功します
- であればが壊れているので復号に失敗します
というオラクルが手に入るので、復号に成功するかをみつつ二分探索するとがわかるという解法を想定していました。しかしこんな解き方をしている人は誰もいなくて、が壊れているときその復号結果はではかつでは非となるような値なので、がでないの倍数になり得る*3ということを利用して解かれているようでした。
……これはsignmeの解法とほとんど一緒です。自分たちの過去問と同じ問題を出してしまった……が、ばれてないのでセーフ!!!!!*4
[crypto] Iron Door (8 solves)
今回のボス問題です。唯一lunaticタグがついていたpwnのbofwowは22 solvesあることを考えるとこの問題にlunaticがついてないのはおかしい。
この問題については簡単に説明するのが難しいのですがCakeCTF 2022に出題したRock Doorの改題で、以前はDSAのが小さいのでLLLで解ける……という問題でした。今回はは小さく、は大きい、ただしは小さいという問題設定になっています。
とりあえずを考えると、両方の項にが登場するのでを消去でき、剰余の方に比べて小さい値になることが期待できるので、係数をLLLで求めることができます。
続いて、という式は既知では未知だがすべての式で共通、が式ごとに異なる比較的小さな未知数なのでこれは典型的なHidden Number Problemのインスタンスです。
したがってこれを解けばが求められる、という問題でした。2段階のLLLが登場してこれは難しいぞと思いましたが、実際にはただLLLなので難しいだけで、解かれた方は大体二段階目のLLLはやらずにを素因数分解するという方針で解かれていたようでした
感想
毎年「このCTFで持ちネタ全部尽きたぁ。終わりだぁ……」と思っているけど、実際にやってみると簡単な問題もそこそこ難しい問題も作れているような気がします。……が、これは罠で、よく見るとjanken vs yoshiking 2もdecryptyouもIron Doorも過去の問題の焼き直しです。もう本当にだめ
インプットを怠った結果アウトプットが枯渇している状態だと思うので、来年のCakeCTF開催のためにもいろいろなCTFに参加していきたいですね(口だけオバケ)。
あとReversingとWebは本当に作れないので協力してくれる人を募集しています
それではさようなら