この記事は、CTF Advent Calendar 2024の19日目の記事です。

はじめに

この記事はCryptoのプロプレイヤーに「祈り」の部分とどう向き合っているか教えてもらおうという記事で、ポエム記事として読んで下さい。半分は本当にお祈りなのではないかなと思っているのですが、もう半分は多分よく理解していないからお祈りに見えているだろうなぁと思っています。

また、問題と解説を紹介していきますが、それらにケチをつけているのではなく、自分の正直な気持ちを伝えて優しく導いてもらおうという趣旨であり、問題、作問者、また、解説に対しては感謝と尊敬しかないことを付け加えておきます。

また、Cryptoをある程度分かっている人向けに書くのでご注意ください。

『祈り』

Cryptoでは、良い感じの条件を持つ入力を素敵なアルゴリズムに通してやるといい感じの結果が返ってくるものたちがいくつかあります。例えば、以下のようなものです。

グレブナー基底
LLL
Coppersmith
z3

Cryptoプロプレイヤーは、この「いい感じの結果が返ってくること」をどう捉えているのでしょうか？いい結果が返ってくることを確信して使っているのか、はたまた、経験から良い結果がある程度の確度を持って使えているのか、はたまた、色々ガチャガチャしながら答えが出るまで、最終的には『祈り』の力でフラグを捻り出しているのでしょうか？

これから『祈り』を感じる部分について紹介していきながら、その『祈り』を感じる部分を率直に列挙していきながら、プロたちはどう向き合っているのかを問題提起していこうと思います。

SECCON CTF 13 Tidal wave

記憶に新しいkurenaif先生の最新作ですね。Tidal wave。解けませんでしたが、非常に勉強になりました。解説の詳細は公式Writeupや公式動画解説、また、bokuikkunさんの解説もあるので詳細はそちらを参照するのが良いです。以下では、ざっくりとしかやらないので、これらの解説を理解した後の方が以降読みやすいかもです。

Tidal waveは、グレブナー基底 → CVP → Coppersmith → GRS符号の誤り訂正という順で各小問題を攻略していきます。順番に見ていきましょう。

グレブナー基底

最初の小問題では、ランダムな数値から成る配列alphasを用意して、それをVandermonde matrixっぽく配置してちょっとずつずらしながら行列式を取ったdetsと、alphasの各要素を2乗したdouble_alphasが与えられるので、alphasを復元せよという小問題から始まります。ここで持ち出されるのがグレブナー基底です。

グレブナー基底
多変数多項式の簡約化が一意に行える多項式の集合
簡約化とは、直感的には多変数多項式の除算により、より次数の低い "余り" の多項式を求めていくことである。
Wikipedia

ざっくりと言うと（というより自分の理解がこのざっくりとしたものなのですが）高次元の連立方程式を突っ込むと、より簡単な方程式が得られるというものです。

さて、alphasを変数として定義してdetsとdouble_alphasについて多項式を作成して、グレブナー基底を取ってみましょう。alphasだと長いのでaとして表記しましょう。

detsとdouble_alphasの計算は以下のように実装されています。

dets = [G.submatrix(0,i*k-i,8,8).det() for i in range(5)]
double_alphas = list(map(lambda x: x^2, alphas))

上はずらしながら行列式を取ったもので、下はalphasの2乗を取った結果です。これを数式にすると以下のようになります。

$\displaystyle dets_0 = a_0^7a_1^6a_2^5a_3^4a_4^3a_5^2a_6 + ... \\ + a_0^3a_1^2a_2^5a_3^6a_5a_6^4a_7^7 + a_0^2a_1^3a_2^5a_3^6a_5a_6^4a_7^7 \\ - a_0^6a_1^5a_2^3a_4^2a_5a_6^4a_7^7 + a_0^5a_1^6a_2^3a_4^2a_5a_6^4a_7^7 \\ + a_0^6a_1^3a_2^5a_4^2a_5a_6^4a_7^7 - a_0^3a_1^6a_2^5a_4^2a_5a_6^4a_7^7 \\ - a_0^5a_1^3a_2^6a_4^2a_5a_6^4a_7^7 + a_0^3a_1^5a_2^6a_4^2a_5a_6^4a_7^7 \\ + ... + a_1a_2^2a_3^3a_4^4a_5^5a_6^6a_7^7 \\ dets_1 = ... \\ ... \\ dets_4 = ... \\ \\ \verb|double_alphas|_0 = a_0^2 + 1281782565...122826897 \\ \verb|double_alphas|_1 = a_1^2 + 1222251497...924743634 \\ ... \\ \verb|double_alphas|_{35} = a_{35}^2 + 1065024427...142500816$

そして、これを全てグレブナー基底に突っ込みます！『祈り』ましょう！

$\displaystyle a_0 + 10116746316...13709519 a_{35} = 0\\ a_1 + 99816305691...29103048 a_{35} = 0\\ ...\\ a_{34} + 139803356...37995781 a_{35} = 0$

こんな素晴らしい式が得られます！なんと、この複雑な多項式から $a_i$ と $a_{35}$ の単純な1次式が出てきました。

もはや人智を超えた結果のように見えます。実際にやってみるとこの結果が出てきますし、複雑な多項式を見たらグレブナー基底を使ってみようというのも何となく知っています。また、double_alphasがあるのでとりあえず任意の変数について1次式以下にすることができそうというのは肌感としても分かります。しかし、ここまできれいな方程式が出てくるのはどれだけ予見できているものなのでしょうか。

--- モヤモヤ 1 ---
グレブナー基底を使って、きれいな方程式が得られるというのは
どれくらい予見できることなのでしょうか？
問題を信じてやってみるしかないのか、もしくは、
自分の良く理解していない観点や数学的な着眼点があるのでしょうか？
もしくは、ほぼ『祈り』なのでしょうか？

今回の問題で言うと、 ${a_0}^3=A$ がいい感じに $a_0=B$ になりそうなのは分かるのですが、例えば ${a_0}^3{a_1}^2{a_2}^5{a_3}^6{a_5}{a_6}^4{a_7}^7=A$ が $a_0a_2a_5a_7=B$ とはならずに $a_0 + Ca_{35} = D$ となるのは、どれくらいピンとくる結果なんでしょう。

また、更に言うとこんなに暴れん坊な結果が出てくるグレブナー基底ですが、

--- モヤモヤ 2 ---
グレブナー基底でこのようなきれいな結果が出てくるように
どうやって作問しているのでしょうか？
このようなダイヤの原石のような多項式集合を
どのように作り出すのか、とても気になっています！

もっとも、作者は魔女なので、魔術かもしれないのですが。

この問題に限らず、解説で「ここでグレブナー基底を取ると、こういう式が出てきて解けます」というのをよく見かけます。現時点の自分にとっては、『祈り』の結果である神からの贈り物のように見えてなりません。グレブナー基底の本質はガチャなのか、それともちゃんと深堀をすれば人間がコントロールできるものなのか…

CVP → Coppersmith

次はCVPからのCoppersmithを使うパートです。こちらはより『祈り』成分が高く、なぜなら、CVPの結果を『信じて』更なる「祈り」を捧げる必要があるためです（？）。本来の解法と比較して1ステップ省略していますが、alphasを得ることができ、つまり行列Gを復元することができました。次の小問題は以下のp_encodedが与えられるのでpvecを求めよという問題になります。

p_encoded = pvec*G + make_random_vector(R, n)

pvecはRSAにおけるnの素因数分解後のpを分解して作られるベクトルで、Gは導出済みです。make_random_vector(R, n)は乱数が与えられます。式を書いてみましょう。

$\displaystyle \verb|p_encoded|_0 = G_{0,0} pvec_0 + G_{0,1} pvec_1 + ... + G_{0,35} prev_{35} + rand_0 \\ \verb|p_encoded|_1 = G_{1,0} pvec_0 + G_{1,1} pvec_1 + ... + G_{1,35} prev_{35} + rand_1 \\ ... \\ \verb|p_encoded|_{35} = G_{35,0} pvec_0 + G_{35,1} pvec_1 + ... + G_{35,35} prev_{35} + rand_{35} \\$

これは連立線形近似方程式を解く問題と見ることができ、つまりこれは、LWE問題です。このLWE問題を解くために、CVPをしてからCoppersmithをしていきましょう。

CVP / LLL

LWE問題はCVP問題として解くことができます。CVP問題とは、

CVP: Closest Vector Problem
格子Lに含まれないベクトルwが与えられたとき、格子Lに含まれるベクトルwに最も近いベクトルを探す問題

p_encoded = pvec*G + make_random_vector(R, n)

ほとんど格子を理解している前提で書きますが、この式の中のGを格子として見ます。すると、pvecとGを掛け合わせたものは格子Lに含まれる任意のベクトルとして考えることができます。今回与えられるp_encodedはその任意のベクトルにランダムな値を足して作られているので、p_encodedとpvec*Gは比較的近いベクトルであると考えられます。つまり、この問題はp_encodedに最も近い格子Gに含まれるベクトルを探すことでpvecを求めることができ、この問題はCVPと考えることができます。

CVPは質の良いライブラリ「Inequality Solving with CVP」があるので、そちらを使うと解くことができます。kurenaifさんの使い方シートやzer0ptsのCVP記事が非常に参考になります。これを使えばあとはパラメタを適切に指定して投げれば答えが得られます。

さて、やってみましょう。このライブラリを使ってpvecを求め、それをpに再構成したものが以下の値です。

$\displaystyle p_{kamo} = 12565690...5321344$

さあ、『祈り』ながら割り切れるかどうか見てみましょう。

完全に終わりです。ここまでありがとうございました。この解法は間違いでした。ご清聴ありがとうございます。来年もみなさん、どうかよろしくお願いいたします。

いや！待ってください！まだあきらめてはいけません！信じるのです！

『祈る』のです！！！

Coppersmith's Attack

先ほどの手法を与えられているsageコードを流用しながらp,q,N,alphas,p_encodedなどをランダムに作りながら実験してみましょう。

sage@1422f2dbe36b:/mnt$ sage solver3.sage
Expected Number of Solutions :  1
p_kamo=
107813069...0465092283539285651018073072430183885388277487977433100321323430002556928
p=
107813069...0465092283539285651018073072430183885388277487977433097532414169145114001

sage@1422f2dbe36b:/mnt$ sage solver3.sage 
Expected Number of Solutions :  1
p_kamo=
676183195...5501882391961930276292981719929111783955619629915479044046229792943505408
p=
676183195...5501882391961930276292981719929111783955619629915479046704412326655254803

sage@1422f2dbe36b:/mnt$ sage solver3.sage 
Expected Number of Solutions :  1
p_kamo=
121718811...9445801378564704362685859159720855874255202871781593950895932506309132288
p=
121718811...9445801378564704362685859159720855874255202871781593947269210613003648049

なんとこのような結果になります。（省略している部分は同じ値になります。）正確なpの値は出てきませんが、どれも非常に近い値が得られているのが分かります。さて、ここで利用できるのがCoppersmithです。

Coppersmith's Attack
とある合同方程式 f(x) ≡ 0 (mod N) に対して小さい整数解xを求める手法

今回得られた $p_{kamo}$ はpにとても近い値になっています。ということは、その二つの差分dは全体に対してとても「小さい」値になっていると考えることができます。つまり、Coppersmith's Attackを使ってdを求められるということです。

$\displaystyle N = pq \\ N = (p_{kamo} + d)q \\ 0 = (p_{kamo} + d)q\,\,\verb|mod|\,\,N$

qという変数が残っているような気がしますが、あまり気にせずCoppersmithを適用しましょう！「祈り」ながら！

これがCryptoにおける『祈り』です。

ふざけるのはこの辺にしておいて…

今回CVP/LLLとCoppersmithを紹介しましたが、どちらも『祈り』要素が強い手法だと思っています。

--- モヤモヤ 3 ---
格子を作ってLLLで解く系のものが正しい答えを現実的な時間で返すか
という部分は大体「お祈り」なんでしょうか。
格子で解くぞ！となって格子を作ってガチャガチャやるときによぎる
「格子が想定解ではないのではないか」にどれくらい抗っているのでしょうか。

出てきた結果やかかっている時間を観察して、スケールを変えたり、パラメタを変えたり、格子を変えたりガチャガチャするとは思っていますが、格子で解けるだろうという仮定をどのくらい維持続けられているのか、「祈り」続けるしかないのかがどうなんだろうと思っています。明らかに不明部分が小さかったりする場合はいけるやろとなる気持ちも分かるのですが、この辺りをしっかり自分の中で落とし込まないと今回のような問題は一生解けない気がしていて、何か良い落としどころがあるのでしょうか。

また、今回は乱数部分のbit数が大きいので、より格子で解くんだという強い気持ちを持つ必要性を感じていて、格子で解けそうというのはどういう要素から感じるものなのかもプロから聞いてみたい所です。

次はCoppersmithです。正直、Coppersmithはかなり雰囲気で使っているのでちゃんと勉強しないといけないのですが、現在Coppersmithを体系的に取り扱っている日本語の資料が無さそうで、英語もかなりアカデミックなものしかなさそうだったので一旦置いておいておいています。Coppersmithについてよく理解できるいい学習資料ってあるんでしょうか？（日英問わず）

--- モヤモヤ 4 ---
Coppersmith's Attack、教えてください。
単変数でも多変数でも何故かCoppersmithが
うまく働いて解けるというのを何回か見ています。
これはそういうものなんでしょうか？
それか、単に勉強・経験不足なだけでしょうか？

正直本当に雰囲気で使っていて応用が全く効いておらず、今回のqが無視されること（恐らく、正確にはmod Nではなくmod qとして解釈されていたんだろうと思っています）もどういう理由でそうなっているのか全く分かっていません。Cryptoをやっていると分からないが何故か動くということが割とあり、自分の知識がないのか、みんな感覚でやっているのか分からなくなります。

また、Tidal waveでは $p_{kamo}$ がpにかなり近い結果となりますが、pvecで分割されているので不明部分は色々なbitに分散してもおかしくなさそうです。しかし、今回は下位ビットに集まっていて、いい感じにCoppersmithが適用できるような形になっていました。

--- モヤモヤ 5 ---
Cryptoにおいて実験は割と大切なのでしょうか？
数式ガチャガチャでは得られない、実験してみないと分からない
与えられているパラメタに潜む数学的な傾向を
観察する重要性をかなり感じています。

GRS符号の誤り訂正

やっと、ここまで来ました。pが復元できたということは、Nが素因数分解できたということです。最後はGRS符号の誤り訂正をするパートになるのですが、ここに『祈り』成分は感じていません。それができる符号化方式であり、ちゃんと誤り訂正できる保証があり、そのためのアルゴリズムがあるためです。

総評

Tidal wave、非常に噛み応えのある問題でした。ちょうどずっと埋めたいと思っていた部分のオンパレードで、色々議論したいし、勉強させてください！

他には？

他にも祈りを感じる部分はあるので、紹介していきます。

z3

Z3 Theorem Prover
Microsoft Researchが開発したSMTソルバー
Wikipedia

SMTとはいくつかの数式を与えたときに、全ての数式を満たす入力があるかどうか（充足するか）を判定する問題のことを言います。z3では、充足する場合、充足するための入力の1つを返してくれます。より、具体的にはどういうことかというと

$\displaystyle 0 ≦ x \\ x ≦ 5 \\ x < y$

このような条件を与えてやるとSAT（充足）と判定され、その場合の入力の1つである $x=0, y=1$ が与えられます。とても柔軟で何でも解けそうな見た目をしていますが、コンテスト終了までに「停止」するかが問題です。

Google CTF 2023 - MINE THE GAP

Cryptoではないのですが、z3が効果的に使えることを示す問題です。kusanoさんの解説が非常に分かりやすいです（公式解説もz3です）。マインスイーパーの確定していない部分を変数として、周囲の状況からz3に与える制約を作成していきます。盤面は3600×1632マスで、確定していないマスの個数はそのうち1割くらいもないような気がしますが、それでも大量の変数と条件をz3に与えています。

変数の取りうる値がボムがある/ないの0/1なので、z3が得意そうな形っぽいのは分かるのですが、ちゃんと計算が停止してくれるかどうかをどうやっていい感じに見積もっていくのかは、モヤモヤしたままです。まあ、でもこの問題に関しては割とSAT問題みたいな雰囲気もあるので、z3を使うのは納得感があります。

SECCON CTF 2022 Qual - janken vs kurenaif

メルセンヌツイスタやLCGのような乱数をテーマにした問題をz3で解くというのを割と見かけます。janken vs kurenaifではpythonのrandom.seedとrandom.randintを独自実装してz3に流してやるというのが想定解になります。ふるつきさんの公式解説、だこつさんの解説を読んでみましょう。

z3が扱える問題広すぎるので、z3に通してみて解いてみようというのをこの問題でも適用可能というのは分かりますし、過去問を解いていくとz3と乱数は割と組み合わせがあるなとなるのも体感しています。しかし、普段意識から外れているとz3にとりあえず通してみようと思い立つのが難しく、実際過去問として解いてみたときは全く思いつきませんでした…

この問題を解くのに必要なのは、z3に通してみようと思う気持ちと、それを信じて停止するまでガチャガチャやりながら待つことだと思っており、それはどう鍛えればいいかな…とモヤモヤしています。z3の内部実装をもっとちゃんと理解すべきなのか、最終的には『祈り』なのか…

PlaidCTF 2015 RE GEX

いつも見ているこのページで紹介されている問題です。ちゃんと復習はしていないのですが、想定解であっても解が求まるまで1時間以内くらい時間がかかるz3解法が紹介されています。近年ではCTFの洗練化が進んでいる（特に国内）ので、これくらい待つ問題はもしかしたら少ないのかもしれないですが、z3が10分で停止するのか、1時間で停止するのか、地球が滅亡した後に停止するのかを肌感レベルでも推定するのが自分にとってはとても難しく、1時間計算を待つのはせめて計算オーダーが分かっていないとベットできないかなと思っています…

と、色々問題を紹介しましたが、つまりは…

--- モヤモヤ 6 ---
z3が停止するかどうかをどのように見極めていますか？
停止すれば正しい解が出てくると思うので、
論点は停止するかどうかだと思っていて、
z3を解法として仮定するときにどのように考えていますか？

乱択

乱択で何かをするような問題は確率で可能性を体感できるので、自分にとっては『祈り』ではないです。これくらいやれば望んだ結果が得られそうというのが確率を根拠にして、自分の中で断定できます。確率的な感覚が無いとこれも祈りに見えそうではあります。競プロで鍛えられすぎた可能性はありますね。

競プロに置き換えて考えると、もしかしたら、最小費用流とかがこのフローでいけそうと判断する感覚と、この格子や方針でいけると判断する感覚は似ているのかもしれないですね。気持ちになるというか、なんというか。

望みの論文が見つかる確率

「祈り」というよりという感じですが、Cryptoの解説を読んでいると頻繁に論文が引用されてきます。入門記事でも詳細は論文を見てねとなっているものも割とあるので、Crypto系の論文が読めることは割と人権ラインな雰囲気を感じています。Webでもカンファレンスで出てきた手法とかPortSwiggerのブログ記事で紹介されている手法とか、そういった最新のものを参照する場面があったりしますね。

Google CTF 2024 Quals - McEliece

kurenaifさんの動画（今年のSECCON予選中に無茶苦茶見ました）やshihoさんのGistを見ると雰囲気がつかめるかと思いますが、論文から解く手法を持って来る必要があります。そのため、この問題を解くには論文を読める必要があります。（見つけてくるのは実装から検索キーワードに使えそうな方式名などが特定できれば、多分それほど難しくない）

論文を読むためには、ちゃんと数学的な背景知識をつける必要があり…という問題があります。もはや、『祈り』全く関係なく、単なるモヤモヤなのですが、

--- モヤモヤ 7 ---
問題を解くときに使えそうな論文ってどれくらい探しているんでしょうか？
論文を見つけて実装するのが答えっぽい解法もありそうで、
上位の問題を解くときは論文が読めることは割と必須なのでしょうか？

終わりに

いかがでしたでしょうか。SECCON予選でCrypto担当になったので今年の10月ごろからひたすらCryptoをやっていましたが、祈りとしか見えない部分が多く出てきてずっとモヤモヤしていました。本当のところは、数学的な背景知識の欠如や知識の定着度が問題な気がしていますが、せっかく記事を書くので一言ヒントだけでも教えてもらえると非常に嬉しいです！という記事でした。

もし、モヤモヤに対してヒントいただける方は、自分のツイートにリプしていただいたり、DMしていただいたり、以下にフォームを作ったのでこちらで書いて送っていただけると無茶苦茶嬉しいです。モヤモヤの一部のみ、一言だけ、全体的なヒント、感想、叱咤激励、全て大歓迎です！

docs.google.com

明日はEdwow Mathさんの「Writeup＆Upsolve〜復習するは我にあり〜」です。Cryptoの強者として前よりフォローしていました。Cryptoをやり始めてからもブログをひたすら見させていただいています、楽しみです！

はまやんはまやんはまやん

hamayanhamayan's blog

CTFのCryptoにおける祈りについて