HackTM CTF 2023 開催記

Tue Feb 21 2023

2/18 (土) 21:00 - 2/19 (日) 21:00 に WreckTheLine の一メンバーとして HackTM CTF 2023 を開催しました。 CTF の運営にまわるのは初めての体験で、作問期間からずっと刺激的な毎日を過ごしていました。そのときの気持ちとかは次回運営するときにも役に立ちそうなのでここにメモとして残します。作問感想の部分は問題のネタバレを多分に含んでいるため、ネタバレを避けたい方はここから問題をダウンロードして解いてから読んでみてください。解説やソルバーはここにあります。

運営

2022年10月頃

このあたりの時期に HackTM CTF 2023 をチームで開催するという話が転がり込んできました。 HackTM CTF は HackTM というイベントの中で行われる CTF のようです。 SECCON CTF Finals みたいなものかな (まだよくわかっていない)。今までたくさんおもしろい問題を解かせてもらっていて、そろそろ作る側に回らないとなという気持ちがあったので、運営に参加することにしました。中上級者向けの問題を各カテゴリで5-6問作りましょう、ということだけがチームの中で決まりました。チームの中で crypto をアクティブにやってる人は自分だけみたいな状態だったので、とにかく crypto を作ることにしました ¹。

2023年1月まで

開催が決まってからは、目に入るあらゆるものに対して「問題にできないかな」と考えていました。ぼんやり思ってるだけだと結局全然問題の形にならないので、とりあえず実装し制約をつけてみたり変形してみたり試行錯誤を繰り返していくうちに、今回の問題セットができていきました (詳しくは次の章で述べます)。基本的に式をこねくり回すのが好きなので、そういう問題が多くなってしまった感じがあります… 問題を作ったあとは CTF の終了後すぐに writeup を公開できるように ² 事前に書いてました。書いてる途中で非想定解法になりそうなものを潰せたり問題の不備を直せたり ³ したので、事前に書いておいてよかったと思います。作問後は、無自覚に他の問題と被ってしまうのが怖かったため、あらゆる CTF に参加して crypto 問を回収していました ⁴。

CTF 1-2週間前

リーダーが GCP でインスタンスを立て、サイトも立ち上がり、いよいよだなあとのんきに思っていたのですが、サイトをよく見ると過去の HackTM CTF 2020 のサイトのままになっていることに気づきました。しかもその状態でユーザー登録をしている人が出始めており、これはまずいとなりました。話を聞いてみるとインフラ担当の人が忙しくて手が回っていないということだったので、慌ててインフラ準備をする役にまわることにしました。思ったよりは深刻ではなく、なんとかなりました ⁵。

この頃には問題が全部揃うことが想定されていたはずなのですが、自分の問題5問を含めて全体で8問ぐらいしか揃ってなく、非常に焦ってました。しかし自分のほうで web, pwn, rev の問題を作ろうとしても解いてきた問題量が少なさすぎて自明問っぽいのしか作れず、かなり無力感を味わってました。

CTF 開始直前

開始1時間前ぐらいに、自分の作問がどう思われるかが急に気になりだしてめちゃくちゃ緊張し始めました。気が狂いそうだったので、 SECCON CTF だか CakeCTF だかでやられていた、開始時にサーバーが落ちたとき用のファイル共有用 HackMD を用意していました ⁶。単調作業はいい精神安定剤だった。

あとは問題のデプロイが間に合わないものがいくつかあって嘘だろ…ってなってました。

CTF 開催中

開始時に早速トラブルがあり、開始時間になっても問題が表示されませんでした。DB table の exposed という属性で問題の表示/非表示が切り替えられるのですが、仕様をチーム全体で勘違いしており、開始時間になったら自動で exposed が更新されると思い込んでいました。慌てて DB の UPDATE をかけました。急いで SQL 書くのはかなり心臓に悪かった… 開始時が最もプラットフォームが落ちやすいタイミングだと思うのですが、特に落ちることがなく安定していたかと思います。

始まってしまうと意外と暇なものでチャットで雑談しつつ、各問題の solves 数を眺めていました。自分の d-phi-enc が一番最初に解かれるかな〜と思っていたところ Blog が速攻で解かれてて騒然としてました。

特に大きな問題もなく安心していたのも束の間、突然問題サーバーが死にました。とりあえずインスタンスの再起動で直ったのですが、原因不明だったのでリソース監視をすることにしました。といっても docker container stats を眺めてやばい挙動をしている問題がないか見たぐらいですが…見てみるとある問題が異常にメモリを食っており、それが問題になっていそうでした。今思えばインスタンスを分けるとかすべきだったのですが、当日はあまりいい動きができなかったので反省です。

他の時間は基本的には質問が来たらそれに回答するだけでした。 crypto は質問が来ることが少なかったので ⁷ 空き時間にフィードバックフォームを作っていました。とはいえ問題サーバーが落ちるのが怖かったので、人力リソース監視がやめられず、かなり疲れました。裏で pbctf やろうかな〜ヘラヘラとかいってた過去の自分を殴りたい ⁸。

CTF 終了後

開始時と異なり、終了時はちゃんと問題が表示されなくなったので無事終了しました。フラグの submit ができなくなっていることも確認。何よりも discord で議論が盛り上がっているのが見られてかなり嬉しかったです ⁹。 writeup を公開したり他の方の解き方を眺めたりして終了です。

作問感想

作った問題は以下の通りです。solves 数の予想なんてあてにならないことがわかります。

title	solves 数	予想 solves 数
d-phi-enc	51/366	100
broken oracle	5/366	30
GLP420	0/366	10
kaitenzushi	15/366	5
unrandom DSA	0/366	0-1

※ solves 数の分母は正の点数を取得したチームのみカウント

想定難易度は

d-phi-enc < broken oracle <<< GLP420 <= kaitenzushi << unrandom DSA

でした。

d-phi-enc

中級者ぐらいの人だったら多くの人が解けるであろう問題として作りました。今回が初作問で作った問題の難易度がどんなものなのか本当にわからず、全問題 0 solves とかになるのが怖かったので…

RSA のシンプル (=コードが短い) な問題を考えて、 $d^e$ が既知のときは解ける？→ $e = 3$ なら解ける？→ $\phi^e$ が既知のときは解ける？→解ける！というように作りました。そのため $\phi^e$ だけで解けるのかとか $e = 65537$ で解けるのかとかは不明です。

自分の想定解は、式をガチャガチャやって $\mod n$ を消す方向性でしたが、 crypto 慣れしている人は coppersmith ですんなり解いていそうでした。特に Franklin-Reiter Related Message Attack が刺さるのは目からウロコでした。

broken oracle

xagawa-san の Nが素因数分解可能ということのゼロ知識証明についてという記事を twitter で見かけて、何か問題にできないかな〜と思ってあれこれしてできた問題がこれです。

特に Rabin 暗号の復号オラクルが返す値によっては素因数分解できてしまうというのが CTF に使えそうです。 Rabin 暗号だと簡単すぎるかなということで Rabin 暗号から派生した暗号を探したところ、今回の問題で使った暗号を見つけました。ただの復号オラクルだと暗号化されたフラグをオラクルに投げるだけで解けてしまうので、復号→暗号化をする謎のオラクルにすることでお茶を濁しました。あとはなんとなく公開鍵が未知でも解けそうだなと思いやってみたら解けたので公開鍵も非公開にしました。謎のオラクルに公開鍵も未知という謎の問題設定になってしまいましたが、 CTF なので許して。

時間をかけたら crypto をそんなにやったことない人でもできるように sagemath を使わないで書くことを心がけました。ですが想定以上にコードが長くなってしまったのと多項式の mod 計算のあたりがわかりづらくなってしまい、 exploit できる場所を見つけるのがかなり難しくなってしまったかもしれません。コードが長くなって煩雑になるぐらいだったら sagemath で書けばよかったかも。これみなさんどう思われますか？

GLP420

PQC の問題を出したいなと思って作った問題になります。自分の中では GLP が既存の CTF 知識が活きそうな署名方式に感じたため、これをあれこれすることに。 GLP では $\Phi(x)$ が既約多項式なものを想定しているが、これが既約でなくなったらどうなるんだろうか、というところから始まり、ググってみると「既約多項式でないと安全性の理論保証ができない」という話が見つかったので、 $\Phi(x)$ をいじることにしました。

あれこれ実験してみると $\Phi(x)$ の因数 $\Phi_i(x)$ で mod をとったときにも $s(x), e(x)$ の係数が小さくなることがわかったので、 $\Phi(x)$ が小さい次数の因数の積で表せるときに LLL で解けることを利用することにしました ¹⁰。適当に探索した結果 $\Phi(x) = x^{420} - 1$ を採用することに。

この問題は初手の $\Phi(x)$ を因数分解してみるところが guessy になってしまったことが不満ポイントなのですが、それ以外は満足しています。 $\Phi(x)$ に注目してもらえるように問題名に420を入れてみたり、他の変数は GLP のものをそのまま使ったり ¹¹ 工夫をしたつもりでしたが、作問者の自己満に終わってしまいました… おそらく初手を乗り越えれば GLP を知らない人でもコードを読むことで勉強しながら解けたんじゃないかなと期待しています。

この初手の部分は途中ヒントとして公開するか悩んだのですが、時差による不公平性 ¹² を考えてやめました。0 solves になるよりはよいのではという指摘はあるかもしれない。

kaitenzushi

この本を読んでいて $x^2 + my^2 = n$ となる $x, y$ が既知のときを問題設定にしてみようと考えました。このような形で使える面白そうな話を収集してみると、これやこれが見つかり、これらをうまく使えるような方向性にしました。

$x^2 + my^2 = n$ となる $(x, y)$ が2つ既知のとき、 $m$ が未知でも $\gcd(n, x_1 y_2 - x_2 y_1)$ で $n$ の素因数分解が求まるというのは結構非自明に感じました。これをいい感じに使えるように $x_1 y_2 - x_2 y_1$ が保存するような回転を使いました。回転させると実は $m$ (問題でいうところの $e$ ) も求まることがわかり、さらに $n, m (=e)$ が既知なら $x_1, y_1, x_2, y_2$ も求まるなということで今回の問題ができました。

アルゴリズムドリブンに問題を作ってしまったので、自分で解くときにはそのアルゴリズムから離れることができず、数々の非想定解を生み出してしまいました…ですが考察しがいがあっていろいろな解法がある問題は個人的に好きなので、そこはよかったです。とはいえ想定よりはるかに簡単な解法は避けたかったですね (特に2分探索で $\theta$ が求まるところ)。これはテストプレイをしてくれる人がいたら気づけたんだろうなあという後悔があります。でもテストプレイを依頼するとその人は CTF の参加者になれないので、難しいよね。

ちなみに、問題名は近年世間を騒がせている話題とは一切関係がありません。名前がついたのはもっと昔なので…

unrandom DSA

furutsuki-san が SECCON CTF 2022 Quals で出題した janken vs kurenaif をインスパイアして作りました。 /dev/urandom を MT に置き換えて乱数を意のままに操ることで絶対何か面白いことができると思っていろいろな問題設定を考え、最終的に DSA に行き着きました。 DSA に行き着いたのは TSG CTF 2021 の This is DSA の影響を受けています。

これ本当に解けるのか？というところから始まったので本当に解けたときはかなり感動しました。今回の問題セットの中ではダントツに気に入っている問題です。他の問題が自明に見えてしまうほどに…

10時間はかからないぐらいで解けたので出題しても許されるかなと考えていましたが、今ではこの考えはだいぶ間違っていたなと思っています。主に以下の理由です。

janken vs kurenaif を解いた人じゃないと、そもそも乱数生成を意のままに操れること自体が非自明
- 初見で janken vs kurenaif を解くのにも数時間はかかるはず
24時間の CTF で1問に10時間もかけられる人はほとんどいない
- 強い crypto プレイヤーが複数いるチームって結構希少な気がする
pbctf が裏で走っていた
- crypto プレイヤーが分散していたと思う

24時間 CTF で出してしまったことは反省していますが、それを除けばコードも短く解けたときの快楽性もあり面白さに自信のある ¹³ 問題なのでぜひ解いてみてくれると嬉しいです。この記事投稿時点で CryptoHack の CTF ARCHIVE で公開できるよう申請中です ¹⁴。そのうち CryptoHack でもプレイできるようになるはずです。

フィードバックフォーム

最近参加した CTF のフォームを参考にしました。具体的には SECCON CTF と DiceCTF です。よく言われていることですが、解けた問題が高評価になりやすいのか、 solves 数の多い問題＝高評価となってしまいがちで難しいですね…

今回使った CTFx では、点数はつくが同点時の順位変動はないといった問題を設定することができなさそうだったので、フィードバック問は作れませんでした。告知の仕方が悪かったのかあまり回答されていないので、もしこれを見てる人でまだの方は回答していただけると嬉しいです。リンクはこちら。

フィードバック結果

基本的には褒められのコメントが多くて大変嬉しいです。次回も頑張りたいと思います。

以下、多く受けた要望

rev 問が少なすぎる、 rev の人を雇え
- rev 少なかったのは承知してます… WreckTheLine にはめちゃ rev に強い人がいるのですが、忙しくて作問できなかったらしいです。 final ではきっと作問してくれるので…
ソース無し web はやめて
- そのとおりだと思います…
問題が難しかった。 CTFtime とかに初心者向けではないと書いてほしい
- 確かに、そっちのほうがお互いにとってよさそうですね
crypto の Dockerfile を配れ
- 欲しがる人いるんですね。ライブラリのバージョン依存の問題以外は別に不要かなと思ってました、すみません…
web の downtime がひどかった…
- すみません…
一つの IP で複数の web 問題を出すと悲想定解生むからやめたほうがいいよ
- そうだったのか…それは悲しいのでやめたい。けど料金かかりそうだな〜やむないが
近年だと CTFx を使う理由ないよ
- そうだったのか…でも実際 CTFd のほうが cli とかも整ってるし便利だよなとは感じた

次回があれば次回に活かしたいですね。

本当は deep learning の問題も作ろうと思っていたが、 adversarial attack に毛が生えたものや guessy な問題しか思いつかなかったのでやめた ↩
書くことに満足して終了後すぐアップロードする準備を完全に失念していた… ↩
例えば kaitenzushi の assert が必要十分か、など ↩
回収するだけのはずがいつの間にか解いてしまってるんだよなあ ↩
と信じているだけで、真相は明らかになっていない ↩
プラットフォームとして使っていた CTFx の底力が不明だったため ↩
全体で140個ぐらい質問があった中、3個だけだった。英語弱者なので質問来ないでと祈っていたのが効いた ↩
当然問題は回収しましたが ↩
英語弱者なので議論に入っていけなかったのが辛かった ↩
因数の最大次数 * 2 の行列の LLL が十分速く動けばいい ↩
discord で $\omega$ の値が論文と違うという話があった (論文未確認)。そんな… ↩
ヒントが出たあとに起きている時間が地域によって違うはずなので… CTF で睡眠を諦めるのはよくないと思います ↩
個人の感想です。多くの人にとっては pain かも ↩
https://github.com/cryptohack/ctf_archive/pull/15 ↩