CakeCTF 2023 作問感想

この記事はCTF AdventCalendarの-15日目の記事です

こんにちは。公式writeupっぽいやつは早く出しすぎると参加者が「じゃあ自分はwriteup書かなくてもよいか……」と思ってしまうのでしばらく経ってから出したほうが良いと思っているので寝かせていました。まだ書いていない人でこれを読んでいる人はぜひ運営へのねぎらいだと思ってwriteup書いてください。

以下は解説というよりは感想です。出題した問題はGitHubで公開してます。solverも入っているので詳しい解き方を知りたい人はそちらを見てください（あと解いた人のwriteupを読んだりしてください）。

github.com

[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にいいことを書いてくれてるんですが、”基本的に、公開鍵と秘密鍵は何か数学的な関連性が必要であるから解けないわけで、今回は $x, u$ が公開鍵にしか使われていないため、なんでもおｋ”です。適当に値を決め打ちしてそれで辻褄が合うようにすると解ける。

一見難しそうに見えて普通に数学やると解けるので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は $\mathbb{F_p}$ 上の5x5のランダムな行列 $M$ に対し $M^r$ を計算してくれて $r \mod 3$ がyoshikingの手です。 $p$ はsmoothですが一般線形群 $GL_5(\mathbb{F_p})$ では特に嬉しくないです*1。どうにかして離散対数問題を解いて $r$ を求めたいですね。

そこで一般に $\det(A^r) = \det(A)^r$ だねということを思い出して $\det(M), \det(M^r) = \det(M)^r$ を取るとdeterminantは $\mathbb{F_p}$ 上の計算ですから、このdiscrete logはPohlig-Hellmanで楽に解けるのでじゃんけん勝ち放題という問題でした。

行列の冪乗が出てきたときに行列式を考えたりジョルダン標準形を考えるのは典型だと思っているのでもうひと工夫しても良かったなと思います。あと、janken vs yoshikingを作問したときもp-1が3を位数に持っているとか持っていないとかで非想定の解法を作ったのに今回もそういう解き方のことを失念してたのも良くないですね*2。憶えてたら $p$ はランダムに生成してたと思います。まあでも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要素によって復号時に一時変数 $u = p \mod q$ を破壊できます。

RSA-CRTにおける復号では $m_p = c ^{d_p} \mod p = m \mod p, m_q = c^{d_q} \mod q = m \mod q$ としたあとgarnerのアルゴリズムで $m = ( (m_p - m_q) u \mod p) + m_q \mod n$ として $m$ を復元します。このとき $u$ が壊れているとして

$m \le p$ であれば $m_p$ と $m_q$ は同じ値になるので $m_p - m_q = 0$ となり、garnerのアルゴリズムの $(m_p - m_q) u \mod p$ の部分は0なので $u$ が壊れていても $u$ の影響は $m$ に届かないので復号に成功します
$m > p$ であれば $u$ が壊れているので復号に失敗します

というオラクルが手に入るので、復号に成功するかをみつつ二分探索すると $p$ がわかるという解法を想定していました。しかしこんな解き方をしている人は誰もいなくて、 $u$ が壊れているときその復号結果は $\mod p$ では $m$ かつ $\mod q$ では非 $m$ となるような値 $m'$ なので、 $m - m'$ が $n$ でない $p$ の倍数になり得る*3ということを利用して解かれているようでした。

……これはsignmeの解法とほとんど一緒です。自分たちの過去問と同じ問題を出してしまった……が、ばれてないのでセーフ！！！！！*4

[crypto] Iron Door (8 solves)

今回のボス問題です。唯一lunaticタグがついていたpwnのbofwowは22 solvesあることを考えるとこの問題にlunaticがついてないのはおかしい。

この問題については簡単に説明するのが難しいのですがCakeCTF 2022に出題したRock Doorの改題で、以前はDSAの $r, k$ が小さいのでLLLで解ける……という問題でした。今回は $r$ は小さく、 $k$ は大きい、ただし $k^{-1} \mod q$ は小さいという問題設定になっています。

とりあえず $s_jr_ik_i^{-1} - s_ir_jk_j^{-1}$ を考えると、両方の項に $xr_ik_i^{-1}r_jk_j^{-1}$ が登場するので $x$ を消去でき、剰余の方に比べて小さい値になることが期待できるので、係数 $r_ik_i^{-1}, r_jk_j^{-1}$ をLLLで求めることができます。

続いて、 $s_i \equiv z_i k_i^{-1} + xr_ik_i^{-1} \mod q$ という式は $s_i, z_i, r_ik_i^{-1}$ 既知で $x$ は未知だがすべての式で共通、 $k_i^{-1}$ が式ごとに異なる比較的小さな未知数なのでこれは典型的なHidden Number Problemのインスタンスです。

したがってこれを解けば $x$ が求められる、という問題でした。2段階のLLLが登場してこれは難しいぞと思いましたが、実際にはただLLLなので難しいだけで、解かれた方は大体二段階目のLLLはやらずに $r_ik_i^{-1}$ を素因数分解するという方針で解かれていたようでした

感想

毎年「このCTFで持ちネタ全部尽きたぁ。終わりだぁ……」と思っているけど、実際にやってみると簡単な問題もそこそこ難しい問題も作れているような気がします。……が、これは罠で、よく見るとjanken vs yoshiking 2もdecryptyouもIron Doorも過去の問題の焼き直しです。もう本当にだめ

インプットを怠った結果アウトプットが枯渇している状態だと思うので、来年のCakeCTF開催のためにもいろいろなCTFに参加していきたいですね（口だけオバケ）。

あとReversingとWebは本当に作れないので協力してくれる人を募集しています

それではさようなら