zer0pts CTF 2022で出題した問題について軽く振り返ります。解き方を懇切丁寧に書いたりはしてないです。もし私が出題した問題の解法について詳しく知りたければ y011d4さんによるwriteup や BaaaaaaaarkingDogさんによるwriteup、今後リリース予定の公式writeup（英語）をご覧ください。また、zer0pts CTF 2022で出題した問題はすべて以下のリポジトリで公開しています。
ptr-yudaiは問題セットを作る上でこだわりを持ってうまく楽しめるように工夫しているということが zer0pts CTF 2022開催記 - CTFするぞ に書かれていましたが、私の場合はそんなことを考える余裕はなく、とにかくできるだけ面白くて学びのある問題を作ることで必死でした。
CurveCrypto
問題名が気に入らない問題その1です。楕円曲線上の点を
と倍にしながら、そのxy座標にフラグをXORしたものを暗号として渡しています。
座標のサイズに対してフラグを分割したブロックがごく小さいので、もともとの座標の殆どの部分がわかっており、楕円曲線のの式にあてはめて適当にmultivariate Coppersmith's methodを使えばが復元できて簡単に解けます。multivariate Coppersmith's methodを知らない人は https://github.com/defund/coppersmith を眺めて見てください。2021年のCrypto問題を解く上では必携のスクリプトだったので今後も役に立つかもしれません。Crypto CTFプレイヤーにおすすめのVim Plugin 1選 - ふるつき で紹介しているVimプラグインを導入すればいつでも呼び出せて便利です。
もともと楕円曲線上の点に適当な誤差を足すとどうなるかというのを考えていて、xy座標両方あったら解けるじゃん*1ということを気がついて問題にならないかなということを言っていたらptr-yudaiがブロック暗号にするアイデアを出してくれました。
これはなかなか面白いぞと思っていたのに、完成したものを見返したらAeroCTF 2021で出題されたhorcruxの劣化版になっていたときはビビりましたが、horcurxは極めて複雑で難しい問題であること、他に類題がないことから出題してよかろうと判断しました。問題自体は面白いしね。現在まで特に怒られは発生していません。助かった。
というわけですのでCurveCryptoが解けた人はAeroCTF 2021のhorcruxにも挑戦してみると良いかもしれません。
EDDH
問題名が気に入らない問題その2です。だいたい問題名が気に入らないときはその問題もあんまり気に入ってないです。というよりはよくできた問題には頑張っていい名前をつけようとするから、これはそうでない問題だったということですね。
何をやっているかというといわゆる楕円曲線Diffie-Hellman鍵共有、いわゆるECDHなのですが、一般的な楕円曲線ではなくtwisted Edwards Curveという曲線を使っています。twisted Edwards CurveはEdDSAという電子署名アルゴリズムなどで使われています。例えば最近はSSH鍵を作るときに鍵のタイプにed25519と指定することがあるかと思いますが、ここで使われているのがEdDSA、ひいてはtwisted Edwards Curveです。
今回の問題ではtwisted Edwards Curve上の演算を自前で実装したうえで、与えられた点が曲線上にあるかどうかを確認しないことでdegenerate attackが行える、というのが脆弱性になっています。もはや群の演算を自前実装している問題は99%この種類の攻撃が想定解法であるといっても過言ではないと思います。degenerate attackというのはいわゆるinvalid curve attackのことですが、今回のケースにおいては「別の楕円曲線上での演算にしてしまう」ものではないため呼称が区別されています。
詳細はwriteupに譲りますが適当にを渡すと
が計算され、今回の問題では
がsmoothな値であるため離散対数問題が解けます。
なんのひねりもない素直な問題になってしまったのは多少不満ですが*2、CurveCryptoとともにたくさん解かれていたので良かったです。あとフラグは多少Anti Fermatを意識して似た感じにしました。
OK
keymoon先生との合作です。Oblivious Transferはこれまでにも問題にしていますが、今回はRSA暗号を用いた実装について調べていて、これをどうにかできないかと思っていじりまわしていました。その結果となるような
が多数与えられたときに
が求まるか、という問題に帰着できそうということに気が付きました。
これが解けるかは頭をひねってもわからなかったのですが、もしかしたらと思いつつkeymoon先生にお見せしたところ「これはね、解けます」という力強いお言葉をいただき、無事問題に昇華されました。
私が形にした当初はの部分がASCII文字列だったため無理やりがちゃがちゃやって解ける感じだったのですが、これもkeymoon先生がすべていい感じにしてくれました。いやはや、頭が上がりません。
問題名や問題文、ダミーフラグやフラグはすべてアニメポケットモンスターのED曲「OK！」からとりました*3。おひさまとおつきさまがかわりばんこに顔を出してくれるところを、2つある平文のうちどちらか一方だけしか手に入らないOblivious Transferに重ねる着想はなかなか詩的で気に入っています。
Karen
eprintをなんとなく眺めていたところ、「これ解けるのまじか！」となって感動した問題を出題しています。要するに とすべての要素が0, 1からなるuniformly randomなn×m行列
があるとき、
の
だけが与えられるので
と
を求めて下さいという問題です。
この問題はHidden Subset Sumとして知られていて、Ngyuen-Sternのアルゴリズムの他にFastICAと呼ばれる独立主成分分析の手法でも解けるようです。
本当はこれらの手法を完全に理解した上でさらにひとひねりを加えたような問題を出題したいところではありましたが、理解が及ばなかったことやこれまであまり知られていない問題をさらに応用した問題をいきなり出しても苦痛の大きい問題になりそうなこと、最終的な問題のソースコードが非常にコンパクトにまとまってきれいだったことからそのまま出題しています。writeupを見ても問題の特性からうまくHidden Subset Sumという単語に辿り着いて解くというものがほとんどだったので*4、結果をみても狙い通りと言えます。
ところでかなりstraightforwardなまま出した理由は上記にあるように「これまであまり知られていない」からなのですが、maple3142さんのwriteup を拝見していたところ、AIS3 EOF Qualsという大会でこの１月に出題されていたようです。まじか……。これはハラキリ物の失態です。大変失礼しました。でもこのCTFは名前すら知らなかったので許してください……
問題名が意味しているのはきんいろモザイクの九条カレンさんです。Ngyuen-Sternのアルゴリズムの最初のステップであると直交するような格子の基底を求める部分がOrthogonal Lattice Attackという名前で、これから正規直交基底のポーズが連想されたのでKarenとしました。Surveyを見ている限りではこの問題名は好評な様子でよかったです。
