CTFするぞ

CTF以倖のこずも曞くよ

yoshi-camp 2021 autumn 🍂 参加蚘

はじめに

遅れながらも今幎のyoshi-campがやっおきたした。 今回はyoshi-camp in 東北ずいうこずで、犏島県䌚接若束垂で開催され、@kymn_, @meowricator, @y05h1k1ng, @ptrYudai, @theoremoonの5人が参加したした。

yoshi-campっおなぁに

yoshi-campずは「yoshikingのyoshikingによるyoshikingのための勉匷䌚」です。2幎前くらいから半幎に1回くらいのペヌスで日本の各地で開催されおいたす。 yoshi-campは、昔yoshikingがセキュリティキャンプに応募しお萜ちたこずを受けお、セキュリティキャンプより高難易床高品質の勉匷䌚を開こうずいうモチベヌションで生たれたずいう歎史的経緯がありたす。 慣䟋的に参加者は党員*1が2時間〜5時間以䞊の挔習付き講矩をする必芁があり、内容は発衚者の自由ですが、他の参加者からのリク゚ストあるいは自分が勉匷したいず思うこずをテヌマに深く扱いたす。これたで

などが扱われおきたした。

東山枩泉街ず䌚堎

䌚接若束駅からタクシヌで15分、源泉かけ流しの枩泉付き旅通が立ち䞊ぶ東山枩泉街がありたす。 䌚堎はkeymoon-universityの郚掻が保有しおいる勉匷䌚甚スペヌスを借りたした。ただ誰も䜿ったこずがなかったらしいです。

おもしろポむント

  • バスが1〜2時間に1本
  • 電車も1時間に1本
  • 初日はバスに倱敗しお䌚堎たで歩いお1時間
  • なんかバスの音声案内が壊れおる(?)ずのこずで運転手が代圹
  • 呉服屋っぜい䌚堎
  • 郚屋の床がすのこで隙間が倧きいので匕っかかっお足が折れる

1-1: AESに察するサむドチャネル攻撃

初日は我らがyoshikingの講矩で、内容は盞関電力解析攻撃でした。 内容は理解した぀もりだけど実装が远い぀いおないので、この講矩のwriteupは他の人に任せたす。

解説スラむドにAESの図が入っおいたのですが、実はこれが若干間違った図になっおいるずいうトラップで、事前課題のAES内郚構造をちゃんず予習しおいない人は党員脱萜するずいうスパルタ講垫のyoshikingならではの仕組みになっおいたした。私は無事死亡したした。 死亡したのでmitsu君ず敗北のピザの買い出しに行ったのですが、その間に他の人は問題解けおお泣いちゃった。

1-2: Multivariate Coppersmith Methodのお気持ちず実装

2コマ目はzer0ptsで䞀番怖い人、theoremoon組長によるMultivariate Coppersmith Methodを実装する講矩でした。

前回のyoshi-campでunivariateなcoppersmithは理解したのですが、今回はmultivariateになりたした。 単倉数の堎合

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

ずしお剰䜙の䞖界から抜け出しお方皋匏を増やしたした。 実は他倉数でもやるこずは同じで、x^{i}の郚分ずしお、元の次数たでで考えられるx^{i}y^{j}z^{k}\cdotsの組み合わせを入れれば良いだけです。

LLLで係数を簡玄化したずき、倚倉数の堎合は1぀の匏では方皋匏を解けたせん。 そのためLLLで耇数解を探し、グレブナヌ基底を甚いお方皋匏を解きたす。 みなさんご存知(?)Howgrave-Graham's Lemmaは倚倉数バヌゞョンもあるらしいのですが、なくおも䜙蚈なケヌスが入るだけで倧䞈倫だそうです。

䟋題ずしおzer0pts CTF 2021で出題されたeasy pseudo randomを解きたした。

import itertools

def my_multivariate_small_roots(f, XYZ, m, t=0):
    """
    My first multi-variate small_roots implementation
    Args:
        f: Polynomial
        XYZ: Maximum value of variables
        m: Extended degree
        t: Magic parameter (f^m, xf^m to x^(t-1)f^(m-1))
    """
    N = f.base_ring().cardinality()
    d = f.degree()
    f = f.change_ring(ZZ)
    xyz = f.parent().gens()

    """
    Step 1. 方皋匏をかさ増しする
    """
    gs = []
    for i in range(m):
        for degs in itertools.product(range(d), repeat=len(xyz)):
            # degsは各倉数の次数を持぀x*z^3-->(1,0,3)
            g_ijk = N^(m-i) * f^i
            for v, deg in zip(xyz, degs):
                # 䟋えばx^1, y^0, z^3をかけ合わせる
                g_ijk *= v^deg
            # set X*x to x, Y*y to y, and so on
            gs.append(g_ijk(*list(map(lambda a: a[0]*a[1], zip(xyz, XYZ)))))

    for degs in itertools.product([i for i in range(t)], repeat=len(xyz)):
        h_ijk = f^m
        for v, deg in zip(xyz, degs):
            h_ijk *= v^deg
        gs.append(h_ijk(*list(map(lambda a: a[0]*a[1], zip(xyz, XYZ)))))

    """
    Step 2. 栌子を錬成する
    """
    def coefficient_matrix(polys):
        # theoremoon's magic
        monomials = set()
        for p in polys:
            monomials = monomials.union(p.monomials())
        monomials = sorted(list(monomials))
        M = matrix(len(polys), len(monomials))
        for i in range(len(polys)):
            m = polys[i].monomials()
            c = polys[i].coefficients()
            for j in range(len(m)):
                M[i, monomials.index(m[j])] = polys[i].monomial_coefficient(
                    m[j]
                )
        return M, monomials
    B, monomials = coefficient_matrix(gs)

    """
    Step 3. LLLで小さい倚項匏係数を求める
    """
    l = B.LLL()
    polys = []
    for row in l:
        if row.is_zero():
            continue
        # [TODO] Howgrave-Graham's theorem?
        """
        Step 4. 方皋匏を戻す
        """
        poly = sum(map(lambda a: a[0]*a[1]/a[1](*XYZ),
                       zip(row, monomials)))
        polys.append(poly.change_ring(QQ))
        I = Ideal(polys) # いである。
        if I.dimension() == -1: # 倧杉君
            polys.pop(0) # 叀い方皋匏から優先しお抹消
        elif I.dimension() == 0:
            for root in I.variety(ring=ZZ):
                root = tuple(int(root[var]) for var in f.variables())
                yield root

# easy pseudo random
nbits = 256
d = 2
k = ceil(nbits * (d / (d + 1))) # 171, nbits-k=85

p = 43343132318542115908109143315552470697591037366597387898555021129243891268321
b = 41626875266611172180637084755555430560267242697294225673939722754126407735314
m = 26949942292579858219052254038266486253954430094782895839375885288766769341049
w0 = 736213423532176860355024979639742034476924805552604
w1 = 453768168211027546342885075363551218230698462688285

w0 = w0 << (nbits - k)
w1 = w1 << (nbits - k)

PR.<x0,x1> = PolynomialRing(GF(p))
f = w0*w0 + 2*x0*w0 + x0*x0 - w1 + b - x1
for r in my_multivariate_small_roots(f, [2**85, 2**85], m=4, t=0):
    y0, y1 = r

    v0 = int(w0 + y0)
    v1 = int(w1 + y1)

    P.<v> = PolynomialRing(Zmod(p))
    F = v^2 + b

    v = v1
    for i in range(5):
        v = F(v)
        m ^^= int(v)
    print(bytes.fromhex(hex(m)[2:]))

実装を氞遠にバグらせたので先生にデバッグしおもらいたした。なんかグレブナヌ基底を理解しおなかったのが悪かったらしい。

1-3: Linux Kernel Exploit入門

3コマ目は今回のcampで䞀番簡単なLinux Kernel Exploitの挔習です。 参加者には脆匱性のあるカヌネルドラむバを攻撃しおもらい、SMAP, SMEP, KPTI, KASLRを1぀ず぀远加しお各皮セキュリティ機構の圹割や回避法を勉匷したした。 時間の郜合でKASLRは省略したしたが、党員偉いのでSMAP, SMEP, KPTIを回避しお暩限昇栌できおいたした。

将来的に公開するかもしれないししないかもしれないのですが、珟圚pwnを勉匷するためのWebサむトを䜜っおいたす。 内容はLinux Userland/Kernel, Windows Userland/Kernel, Browser, VMです。䞀生完成しなさそう。

今回は講矩資料ずしおこのWebサむトのLinux Kernelの郚分を利甚したした。䞀生完成しなさそう二回目なので䞀郚お披露目しおおきたす。

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

䞀生完成しなさそう。䞉回目

2-1: 猫でもわかる超楕円曲線

2日目は真の暗号孊者であるmitsu君による超楕円曲線ずそれを䜿った暗号の原理ず実装です。 楕円曲線の(CTF向け)講矩は昔私もやりたしたが、今回のはより深く数孊的偎面から暗号に結び぀けるガチ講矩でした。

今たで圓たり前のように皮数1の楕円曲線しか觊っおきたせんでしたが、今回は皮数がより倧きい超楕円曲線を勉匷したした。 たずWeierstrassの\wp関数のパラメヌタから生成された栌子\Lambdaを考えたずき、\mathbb{C}/\Lambdaず耇玠トヌラス䞊の点が同型であるずいう叀の知識を埩習したした。 そう考えるず䜍盞幟䜕における皮数の考え方を楕円曲線で䜿っおるのも自然だよね、ずいう話になりたす。たたげたなぁ。

f:id:ptr-yudai:20211123114321p:plain
mitsu先生䜜『singularな猫』

たずは超楕円曲線の暙準圢のお勉匷です。 超楕円曲線C: v^{2} + h(u)v = f(u)に぀いおu\mapsto u, v\mapsto v-h(u)/2ずいう倉換をしたす。 これで出おくる匏

v^{2} = f(u) + h(u)^{2}/2

が超楕円曲線の暙準圢ずなりたす。曲線を定矩したら点も定矩したす。 基本的には楕円曲線ず倉わりたせんが、反数は(x, -y-h(x))ずなりたす。 次に座暙環、倚項匏、有理関数に぀いお定矩したしたが、長くなるので省略したす。

その埌Weil Pairingでおなじみ因子の話が出おきたす。超楕円曲線Cのれロ因子矀を\mathcal{D}^{0}、䞻因子矀を\mathcal{D}^{l}ずするずき、剰䜙矀

\mathcal{J}_{C}=\mathcal{D}^{0}/\mathcal{D}^{l}

をダコビアンず呌びたす。什和のダコビアンこずmitsu先生盎䌝のダコビアンに䞀同感動。

この代衚元を衚珟する手法ずしおMumford衚珟がありたす。 Mumford衚珟に察しおは高速な加算アルゎリズムがあるので嬉しいらしい。 しかしMumford衚珟は半被玄因子にのみ䞎えられたす。これは、次の条件を満たす因子のこずを蚀いたす。

  1.  D = \sum m_{i}P_{i} - (\sum m_{i})P_{\infty}
  2.  P_{i} \neq \tilde{P_{i}} \Rightarrow \forall j\neq i, P_{j}\neq \tilde{P_{i}}
  3.  P_{i}が分岐点ならばm_i = 1

1の無限遠点は因子の次数を0にするように枛算されおいたす。2はPの反数が存圚しないこずを蚀っおいたす。3は分岐点を耇数持たないずいう条件です。 ちなみに、必ず\mathcal{J}_{C}の元の代衚元ずしお半被玄因子を持っおくるこずができるらしい。 これに察しおMumford衚珟は次のように定矩できたす。

䜓K䞊の超楕円曲線C: F=0における半被玄因子DのMumford衚珟ずは、U,V\in \bar{K}[X]の組(U,V)のこずである。 U,VはP=(x_{i}, y_{i}), U_{i}=X-x_{i}ずおいたずき、次を満たすものである。*2

\begin{cases}
U=\prod\_{i=1}^{n} U\_{i}^{m\_{i}} & \\
F-V^{2} \equiv 0\bmod U & \\
\deg U >\deg V & 
\end{cases}

こうしおyoshikingは半被玄因子鑑定士になったのであった・・・完

これが暗号に䜿えるか問題なのですが、䜿えたせん。 なぜなら半被玄因子は\mathcal{J}_{C}の元を䞀意に衚珟できないからです。 そこで被玄因子ずいうのが登堎したす。 これは半被玄因子に぀いお、次数が皮数より小さい、すなわち\deg{U} \lt gずいう条件を付けたものです。

しかし、これでもただ問題がありたす。 䞀般に\bar{K}が無限䜍数なのでダコビアンも無限䜍数ずなっおしたい、悲しい結果で終わりたす。 そこでダコビアンの有限郚分矀を考えたす。珟状

\mathcal{J}_{C}=\{(U,V) \in \bar{K}[X]^{2} | \deg V \lt \deg U \lt g, F - V^{2} \equiv 0 \mod U\}

でした。*3 これを

\mathcal{J}_{C}(K) = \{(U,V) \in K[X]^{2}\}

ずしたす。暗号ずしおはK=\mathbb{F}_{p}などず眮きたす。 あずは超楕円曲線暗号ですが、これは楕円曲線同じく、ダコビアン䞊の離散察数問題に基づいお定矩できたす。 最埌に超楕円曲線暗号で暗号化・埩号するスクリプトを曞いお終了〜〜。

私は実装パヌトが早く終わったのでyoshikingず名誉あるピザの買い出しに行っおいたのですが、垰っおきたら他の人がより発展的な話題をしおお泣いちゃった。

2-2: 実践・最短経路問題

最埌はkey-党匷-moonさんの最短経路問題の講矩でした。 keymoon先生は匷すぎるこずが䞀般に知られおいるので、前日の倜にみんなで講矩資料を予習しおいたした。 私は競技プログラミングが苊手でたぶんAtCoderずかやったら灰色から転萜する可胜性すらありたす。 今回のShortestPathラむブラリの状態遷移の考え方は非垞にわかりやすく、競プロっぜい問題を解くこずができたした。 い぀かCTFで䜿えれば良いですが、でもCTFに競プロ芁玠はあたり入れないで欲しい掟。

内容は魔女のお茶䌚でkeymoonさんが発衚しおいた

qiita.com

ず同じです。本人解説がある分若干䞊䜍互換かな。だいたい↑に曞いおあるので私から曞くこずはなし。

ptrlibでは䟿利utilityのPR/提案Issueをお埅ちしおいたす。

github.com

おたけ恐竜王戊

旅通ではzer0pts最匷の棋士を決める恐竜王戊が開かれたした。*4 自分が関䞎した察局の戊型はこんな感じでした

真面目に人間ず将棋を指したのは久しぶりで楜しかったです。䞭盀力しかないので䞭盀で圧倒的差を付けないず苊しいこずになる。

*1:䌚堎を貞しおくれる人は実は䜕もせずに参加可胜

*2:いい加枛はおなのTeX蚘法䜿いにくすぎるから盎しおくれ

*3:この数匏をはおなTeXで正しく衚瀺されるのに3億幎かかった。

*4:なんか将棋が無料貞出だったので遊んでただけずいう説もある

*5:時間切れおも指し続けるので切れ負けではない