yoshi-camp 2020 winter 開催記

はじめに
第一部　Z3を完全に理解しよう by ptr-yudai
第二部　BKZで勝つ by mitsu
第三部　LLLで殴る(2) by theoremoon
幻の第四部　PRNGと戯れる
おわりに

yoshikingが絶対セキュリティキャンプに落とされる*1ことを受け、「yoshikingのための、セキュリティキャンプより高品質*2なcamp」として定期的に開催しているyoshi-campの第三回目が開催されました。特に明示はしてませんが、個人的には

調べても理解不能なことをテーマに
1人2時間以上のハンズオンで
ゆるくわいわい勉強する

という趣旨でyoshi-campをやっています。暗号担当が多いのでここ二回は暗号中心ですが、私はrev, pwn系を教えています。

第一回：

ptr-yudai.hatenablog.com

第二回：

ptr-yudai.hatenablog.com

私の講義なので特に書きませんが、演習中に判明したこととして

累乗はa*aでなくa**2のように書いた方が速い（というか解けなくなるパターンがある）
成立する条件の個数に制約を付けたい場合はIntを使うと賢い
有理数の制約はRealsから解にis_rationalを適用した方が速い場合がある

などがあるのでそこだけメモ。

講義内容は

Z3の使い方（Bool, Int, Real, BitVec, Enum, 制約, qf論理式）
Z3の内部での「値」の扱い（Application, Quantifier, Bounded/Free Variable）
量子記号の使い方（公理の成立・不成立の証明）
最適化（Optimizer）
推論を利用したデバッグ（unsat core）
戦略（Goal, Tactic）
Z3利用ミス集（BitVecの闇、制約の付け方による実行速度の変化）

でした。完全に理解してもらえたと思います。

LLLで解けない問題の中にBKZというアルゴリズムで解けるものがあるらしく、それの理論をお勉強しました。講義中にはあまり勝った気がしなかったので復讐します。

LLLの復習

LLLと言えばもはやpwn担当の私でも知っているレベルで一般家庭に普及していますが、解ける条件とかは覚えてなかったので復習です。

LLLでは基底を簡約したいのですが、その前にサイズ簡約とは $n$ 次元格子 $L$ の基底のグラムシュミット係数 $\mu_{i,j}$ が

$|\mu_{i,j}|\leq \cfrac{1}{2}$

を満たすことを指します。さらにその上で、Lovaszの条件 $\forall k \in {2, \cdots, n}$ に対して $\delta || b_{k-1}^{*} ||^{2} \leq || \pi_{k-1}(b_k) ||^{2}$ を満たすとき、 $L$ の基底は $\delta$ -LLL簡約されています。（ $\delta$ は簡約パラメータで $\pi$ は直交補空間への直交射影。）

LLL簡約で見つかるベクトルの大きさは

$||b_1||^{2} \leq \left(\cfrac{4}{4\delta - 1}\right)^{\frac{n-1}{2}}\lambda_{1}(L)$

みたいな条件だそうです。（ $\lambda$ は逐次最小。）覚える気は無いけど使う前に考えるようにします。

LLLのアルゴリズムですが、格子から基底を１つずつ取ってきて、次元を増やしながら簡約していっています。部分格子をサイズ簡約してLovaszの条件を満たしていれば次元を増やし、満たしていなければ1つ前の基底と交換して次元を下げる、という方法を取っているそうです。中身とか考えたこともなかった。

HKZ(Hermite-Korkine-Zolotareff)簡約

これも聞いたことがありませんでした。気持ちとしては、最短な非自明ベクトルを取っていく簡約手法です。 HZK簡約すれば逐次最小のベクトルも高い精度で近似できますが、最短なベクトルが取れるという前提がアレなので実用性には欠けそうです。

格子の基底がサイズ簡約されており、かつすべての $1\leq i\leq n$ に対して $||b_{i}^{*}||=\lambda(\pi_{i}(L))$ であるとき、HKZ簡約されていると言います。構成法は非常に単純です。

$L$ 上の最短ベクトル $b_{1}$ を取る
$\pi_{2}(L)$ 上の最短ベクトル $b_{2}'$ を取り、 $\pi_{2}(b_{2}) = b_{2}'$ となるような $b_{2}\in L$ を取る。
以下同様

HKZ簡約したとき、逐次最小のベクトルを次のような高い精度で近似できるそうです。

$\cfrac{4}{k+3}\lambda_{k}(L)^{2} \leq ||b_{k}||^{2} \leq \cfrac{k+3}{4}\lambda_k(L)^{2}$

逐次最小の数え上げ

HKZ簡約はそもそも最短ベクトルを求める問題を含んでおり、そのアルゴリズムを考える必要があります。これにはFincke-PohstやKannanのアルゴリズムと呼ばれる手法があるそうですが、講義中には「逐次最小の数え上げと木探索を利用したアルゴリズム」を利用しました。

まずは問題を簡単に定式化します。ある数え上げ上界列 $R_{1} \leq R_{2} \leq \cdots \leq R_{n}$ について

$||\pi_k(v)||^{2} \leq R_{n+1-k}^2$

を満たす格子ベクトル $v$ の係数ベクトルを求めたいです。

証明はここには書きませんが、結論として

$\left(v_{k} + \sum_{i=k+1}^{n} \mu_{i,j}v_i \right)^{2} \leq \cfrac{R_{n-k+1}^{2} - \sum_{j=k+1}^{n}\left(v_{j} + \sum_{i=j+1}^{n} \mu_{i,j}v_i \right)^{2} ||b_{j}^{*}||^{2}}{||b_k^{*}||^{2}}$

が成り立つように $k=n$ から順に決定していきます。（不等式を満たす $v_{n-1}$ が取れないときは $k=n$ からやり直す。悲しいね。）

講義中に書く時間はなかったので、mitsu隊長が用意してくれたコードでベクトルを見つけ、sageのLLLと戦わせました。私以外は割とLLLと同じかそれよりも良い数え上げ上界列を見つけていました。どうして。

BKZ簡約

本題のBKZ簡約です。気持ちはHKZ簡約の近似みたいな手法だと捉えています。

いつもどおり基底がサイズ簡約されていて、かつ $\beta$ 次元の格子 $L_{k,k+\beta-1}$ の基底 ${\pi_{k}(b_k), \cdots, \pi_{k}(b_{k+\beta-1})}$ がHKZ簡約されているとき、BKZ簡約されていると言います。

$\beta=n$ のときはBKZもHKZも同じですね。ここで（ブロック）基底が直交補空間への射影であることを考えると、HKZ簡約する次元が低いので、単なるHKZ簡約に比べて計算量が減ることが分かります。

BKZ簡約では次の不等式が成り立つそうです。

$||b_1|| \leq \gamma_{\beta}^{\frac{n-1}{\beta-1}} \lambda_{1}(L)$

ここで $\gamma_{\beta}$ はHermiteの定数と呼ばれ、大きいほどよい精度で近似できます。

BKZのアルゴリズムでは、まず入力の基底をLLL簡約し*3、部分格子のサイズ $h$ を $n$ に初期化します。 $k=1$ から始めて各ループで部分射影格子 $L_{k,k+\beta-1}$ の最短な非零ベクトル $v$ を求め、 $||\pi_k(v)|| \geq ||b_{k}^{*}||^{2}$ が成り立っていれば次元を下げてLLLします*4。成り立っていなければカウンタをリセットして次数 $h$ の部分格子に対してLLL簡約する、という流れです。

よく分からんけど部分格子に対して最短ベクトルを求めていく感じですね。

最後にBKZが必要なknapsack問題が渡されるので解きました。解きましたと言ってもBKZはかなり時間がかかるので講義中には解けてません :sob: 注意点としては、格子の並びによって解が変わるので基底をシャッフルしてゴリ押しました。

theoremoonからは第二回に引き続きLLLの勉強です。前回は「LLLとは」から教えてくれましたが、流石に今回は全員LLL使える前提でした。普段使ってないので半分くらい忘れてたけど、まぁ第二部で若干思い出したのでOKOK。 *5

Coppersmithの定理

もはやCTFerなら誰もが一度は使った経験のあるCoppersmithの定理ですが、この講義では実装させられました。事前課題で選択して解いたCoppersmithの定理を使う過去問(私はLayer7 CTF 2020のChild Coppersmithを選びました)を、自作small_rootで解けるようになればクリアです。

Coppersmithの定理のお気持ちとしては、modular多項式を整数係数多項式に変換して解こうという手法です。つまり、 $f(x)\equiv 0\mod N$ の解 $x_{0}$ を用いた等式 $f(x_{0}) - kN = 0$ で、 $k=0$ になればOKです。これを満たすためには多項式の係数が小さい必要があります。理由は２つ。

$f(xX)$ の係数が小さければ、 $f(x_0)\equiv 0\mod N$ は整数係数多項式上でも満たされる →Howgrave-Graham's lemmaがこれを言っていて、条件は $||f(xX)|| \lt \frac{n}{\sqrt{\omega}}$
$f(xX)$ の係数が小さければ、 $f(x)$ は $p(x)$ で割り切れない。（pはこの辺を参照） →条件は $||f(xX)|| \lt 2^{-\omega} X^{k} W$ （この辺怪しいので間違ってるかも）

とにかく $f$ を、根はそのままで小さい係数を持つように変形したいという話です。

ここで多項式は線形結合の形で表せるので、LLLを使って簡約すれば同じ格子上なので根はそのままで係数だけ小さくなります。嬉しい。

ところが今回は方程式が1つしか与えられていません。そこで、適当な変形で方程式の数をかさ増しする必要があります。ずるい。

方程式の増やし方ですが、あくまで独立にする必要があるので $\mod N^{m}$ の世界に持ち上げて考えます。 $f(x_0) = kN$ の両辺を $i$ 乗すれば $f^{i}=k^{i}N^{i}$ なので、 $N^{m-i}x^{i}$ を掛ければ根はそのままです。つまり、

$g_{i,j}(x) = N^{m-i}x^{i}f^{i}$

とすれば $g_{i,j}(x_{0})\equiv 0 \mod N^{m}$ ですね。また、 $f^{m}$ も $N^{m}$ を含むので、これに $x^{t}$ を掛けても方程式を増やせます。

したがって、次のような格子をLLL簡約すれば多項式の係数を小さくできます。

f:id:ptr-yudai:20201228151427p:plain

得られた係数ベクトルがHowgrave-Graham's lemmaを満たしているかを調べ、満たしていれば整数方程式を解けば良いです。

ここまで原理が分かれば実装できます。（実際にはLLL周りでバグらせて助けてもらった。）可能性のある解を全部求められるgeneratorにしてみました。

def my_small_roots(f, X, m, t):
    """
    My first small_roots implementation

    Args:
        f: Polynomial
        X: Maximum value of x
        m: Extended degree
        t: Magic parameter (f^m, xf^m to x^(t-1)f^(m-1))
    """
    N = f.parent().modulus()
    d = f.degree()

    f = f.change_ring(ZZ)
    x = f.parent().gen()

    """
    Step 1. 方程式をかさ増しする
    """
    g = {}
    for j in range(d):
        for i in range(m):
            g_ij = N^(m-i) * (x*X)^j * f(x*X)^i
            g[j*m + i] = list(g_ij)
    for i in range(t):
        h_i = (x*X)^i * f(x*X)^m
        g[d*m + i] = list(h_i)

    """
    Step 2. 格子を錬成する
    """
    B = Matrix(ZZ, d*m+t, d*m+t)
    for i in range(d*m+t):
        for j in range(d*m+t):
            if j < len(g[i]):
                B[i,j] = g[i][j]

    """
    Step 3. LLLで小さい多項式係数を求める
    """
    known = set()
    l = B.LLL()
    for row in l:
        if row.is_zero():
            continue

        
        if RR(row.norm()) >= RR(N^m / sqrt(len(row))):
            continue

        """
        Step 4. 方程式を戻す
        """
        poly = sum([ZZ(k / X^i)*x^i for i,k in enumerate(row)])
        roots = poly.roots()
        if roots:
            for root in roots:
                if root[0] not in known:
                    known.add(root[0])
                    yield root[0]

これを使ってChild Coppersmithを解いてみます。

with open("enc.txt", "r") as f:
    N, e, c = eval(f.readline())
    hint = eval(f.readline())

low_size = hint.bit_length()
kbits = 512 * 2 - low_size

PR.<x> = PolynomialRing(Zmod(N), implementation='NTL')
f = x*2^low_size + hint
f = f.monic()
set_verbose(2)

for root in my_small_roots(f, 2^kbits, m=13, t=39):
    pq = root*2^low_size + hint
    p = N / pq
    q = pq / p

    piN = p * (p-1) * (q-1)
    d = inverse_mod(e, piN)
    print(bytes.fromhex(hex(pow(c, d, N))[2:]))

やったぁ。

verbose 1 (7: child_coppersmith.sage.py, my_small_roots) LLL of 52x52 matrix (algorithm fpLLL:wrapper)
verbose 1 (7: child_coppersmith.sage.py, my_small_roots) LLL finished (time = 39.072761)
b'LAYER7{Now_you_can_say_you_are_child!}'

実装は思ったより単純でしたが、ちゃんと解けたので感動しちゃった。