yoshi-camp 2022 winter参加記【Day 0-1】
2022-12-13 22:50:34 Author: ptr-yudai.hatenablog.com(查看原文) 阅读量:22 收藏

今年もyoshi-campを開催しました。

今回は久しぶりのオンサイト開催で、zer0pts外部からの参加者も募集しました。 結果として、連絡してくれた./VespiaryのXornetさんとﾈさんを招待しました。

もともとはyoshikingがセキュリティキャンプに落ちたことを受け、セキュリティキャンプよりも高度な講義をyoshikingに受けさせる目的で開催されました。 ちなみに今年は私がGCCのチューターに落ちました。さようならGCC。

yoshi-campの講義はMooreの法則で年々難易度がインフレしています。 インフレしすぎて今年は全然実装が追いつかなかったので、とりあえず今回は初日終了までの内容を出して、後から2日目以降を公開したいと思います。

開催地決定

今までは大学関連施設を借りて開催していましたが、宿泊場所から会場までの移動時間が無駄という理由で、今回はでかい家を借りました。 場所は最大10人程度が泊まれる箱根の別荘にしました。 候補はいろいろありましたが、富士山が見える部屋や全面ガラス張りの石風呂など施設が充実していたため全力でこの別荘を取りました。

当日までに持ち運びできるホワイトボードなどを購入しました。買っててよかったです。

Day 0

会場まで

Day 1にみんなが早くチェックインできるよう、私は前日に家を開けました。 秋葉原で5m HDMIケーブルを買うついでに将棋盤を買い、将棋盤を買ったついでにハゲタカというカードゲームを買いました。

新宿から箱根湯本まで行き、会場に行く前に温泉に入りました。 会場までは山を登り左右に揺れまくる激酔いバスで一本です。

会場着

今回借りた家は基本的にすべてが良かったのですが、周辺の店から家までの坂が大変でした。

第一犠牲者
第二犠牲者
第三〜第五犠牲者

事前にホストから、HDMIが使えるでかいテレビがある情報を得ていたので、ディスプレイのセットアップやホワイトボードの配置を考えた後、講義資料の修正をしていました。 家が広すぎて寂しかったです。

Day 1

朝

まず朝にyoshikingが到着しました。 卓球台があったので卓球を極めて、あとはジェンガとかしてました。*1

その後theoremoon、Xornet、ﾈさんの順番に到着したと思います。 mitsu大教授はDay 2から来ました。

[theoremoon] 猫と学ぶ同種写像暗号

今流行りの激アツ（炎上）プロトコルことSIDH(Supersingular Isogeny Diffie-Hellman)のお勉強です。

今回扱う同種写像は楕円曲線から別の楕円曲線への写像\phi: E\rightarrow E'で、次の性質を満たすらしいです。

有利多項式なので次数が定義でき、次数lの変換をl-isogenyと呼ぶそうです。

E(\mathbb{F}_p)とH\in E(\bar{\mathbb{F}}_p)が与えられたとき、\ker{\phi}=\langle H \rangleとなる同種写像は同型を除き一意に定まるという基本命題があると説明されていました。 そしてこの写像の計算はVéluの公式/Kohelの公式というので計算できるらしいですが、今回は本質でないのでsageの実装をお借りしています。

最初の演習ではn-isogenyをすべて求める関数を実装しました。当日の私の成果はこれだけです。 n-torsion pointを生成元として同種写像を求めれば良いとひよこ先生が言っていたので、それを実装しています。

def l_isogeny(E, l):
    for root in E.division_polynomial(l).roots():
        H = E.lift_x(root[0])
        phi = EllipticCurveIsogeny(E, H)
        E2 = phi.codomain()
        yield phi, E2

sageにはisogenyというメソッドがEllipticCurveに生えていますが、上記実装のl_isogenyはすべてのl-isogenyを求めてくれます。

このあと高次数の同種写像を求める実装がありましたが、現地ではやり方が分からず死亡しました。 復習ということで演習の続きをやります。*2

SIDHするにはle-isogenyが欲しいのですが、そんなでかい値のdivision_polynomialを求めようとすると計算が終わりません。 そこで、生成元と曲線を移しながら、l-isogenyをe回計算するとle-isogenyになるようです。原理は理解できませんでした。

def l_isogeny(K):
    phi = EllipticCurveIsogeny(K.curve(), K)
    return phi

def prime_power_isogeny(K, l, e):
    E = K.curve()
    assert K.order() == l^e
    for i in range(e):
        phi = l_isogeny(l^(e-i-1) * K)
        E = phi.codomain()
        K = phi(K)
    return E

これでle-isogenyが計算できます。 まず、prime_power_isogenyにはle-ねじれ点を渡します。 これはよく分からなかったのですが、見かねた講師が1記事書いてくれています。

furutsuki.hatenablog.com

それはそう。

G = E.gen(0)
K = int(G.order() / l^e) * G

とかで適当に作っておきましょう。

次にfor文の中ですが、

phi = l_isogeny(l^(e-i-1) * K)

でl-isogenyを計算しています。 さっきのl_isogenyはyieldですべての同種写像を求めていましたが、今回はl-ねじれ点を1つ渡してl-isogenyを求める実装に変わっている点は注意です。 Kはもともとle-ねじれ点だったため、le-i-1倍するとl-ねじれ点になります。 これをfor文でe回繰り返せば、le-isogenyが求まるという算段です。

さて、曲線を別の曲線に移せる同種写像を一意に計算できることが分かりました。 同種写像で移る同型な楕円曲線同士をまとめると、写像を辺としたグラフになり、これを同種写像グラフと呼ぶそうです。 l-同種写像はl+1個存在するので、各頂点はl+1個の辺を持ちます。 別の曲線から同じ曲線に移ることもあるため、木構造ではなく一般的なグラフ構造です。

この性質を利用すれば、ハッシュ関数が作れることが分かります。 例えば適当な点を始点とし、2-isogenyを考えます。 入力の0ビット目が0ならx座標の小さい方に移す、といったルールを設ければハッシュ関数になります。

演習では始点について定義されていましたが、よく分からんかったので適当に一意に定まるように選びました。

def l_isogeny(E, l):
    for root in E.division_polynomial(l).roots():
        H = E.lift_x(root[0])
        yield EllipticCurveIsogeny(E, H)

def CGL_hash(message):
    p = 2^143 * 3 - 1
    E = EllipticCurve(GF(p^2), [1, 0])
    K = E.gen(0)

    prev_K = None
    for c in message:
        for i in range(8):
            bit = (c >> i) & 1

            next_point = []
            for phi in l_isogeny(E, 2):
                next_K = phi(K)
                if next_K != prev_K:
                    next_point.append((next_K, phi))
            next_point.sort(key=lambda k: k[0].xy()[0].polynomial()[0])

            prev_K = K
            if bit == 0:
                K, phi = next_point[0]
            else:
                K, phi = next_point[1]
            E = phi.codomain()

    return E.j_invariant()

print("H('A') =", CGL_hash(b"A"))
print("H('A') =", CGL_hash(b"A"))
print("H('\\xf0') =", CGL_hash(b"\xf0"))
print("H('\\xf0') =", CGL_hash(b"\xf0"))

ハッシュ値は最終のj不変量としています。

実行すると、クソ遅くて実用に耐えないハッシュ関数なんだなぁという気持ちになりました。

H('A') = 287496
H('A') = 287496
H('\xf0') = 3125053620820126733577185655687010464159146*z2 + 30208777635867085880652267524806729714750758
H('\xf0') = 3125053620820126733577185655687010464159146*z2 + 30208777635867085880652267524806729714750758

さて、ここからがSIDHの話です。 暗号というのは何かしら解くのが難しいと思われている問題をベースにしています。 SIDH暗号の場合、同種写像問題というもので安全性を証明しています。

【同種写像問題】
EとE'=\phi(E)が与えられたとき、E, E'から\phiを求めるのは困難である。

シンプルで大変よろしい。 SIDHの場合、次のような可換図式で普通のDiffie-Hellman鍵共有をします。

次の演習ではとうとうSIDHを実装します。 いろいろバグり散らかして教えてもらいましたが、最終的には次のようなコードになりました。

import sys
import json

def l_isogeny(K):
    phi = EllipticCurveIsogeny(K.curve(), K)
    return phi

def prime_power_isogeny(E, K, l, e, P=None, Q=None):
    for i in range(e):
        phi = l_isogeny(l^(e-i-1) * K)
        E = phi.codomain()
        K = phi(K)
        if P is not None:
            P = phi(P)
        if Q is not None:
            Q = phi(Q)
    return E, K, P, Q


(lA, eA), (lB, eB) = (2, 91), (3, 57)
p = lA**eA * lB**eB - 1
assert is_prime(p)

F = GF(p**2, "z")
E = EllipticCurve(F, [1, 0])
PA, QA = lB**eB * E.gen(0), lB**eB * E.gen(1)  
PB, QB = lA**eA * E.gen(0), lA**eA * E.gen(1)  

def encode_p2(v):
    v = v.polynomial()
    return [int(x) for x in list(v)]

def decode_p2(xs):
    return F(xs)

if __name__ == '__main__':
    
    if sys.argv[1] == "alice":
        sa = randrange(0, lA^eA)
        H = PA + sa * QA
        EA, _, phiA_PB, phiA_QB = prime_power_isogeny(E, H, lA, eA, PB, QB)

        
        phiA_PBx, phiA_PBy = encode_p2(phiA_PB[0]), encode_p2(phiA_PB[1])
        phiA_QBx, phiA_QBy = encode_p2(phiA_QB[0]), encode_p2(phiA_QB[1])
        a, b = encode_p2(EA.a4()), encode_p2(EA.a6())
        print(json.dumps({
            "U": {"x": phiA_PBx, "y": phiA_PBy},
            "V": {"x": phiA_QBx, "y": phiA_QBy},
            "E": {"a": a, "b": b},
        }))
        params = json.loads(input())

        a, b = decode_p2(params['E']['a']), decode_p2(params['E']['b'])
        EB = EllipticCurve(F, [a, b])

        phiB_PA = EB(decode_p2(params['U']['x']), decode_p2(params['U']['y']))
        phiB_QA = EB(decode_p2(params['V']['x']), decode_p2(params['V']['y']))
        H = phiB_PA + sa * phiB_QA
        EBA, _, _, _ = prime_power_isogeny(EB, H, lA, eA)

        shared = EBA.j_invariant()
        print("shared key is:", shared, file=sys.stderr)

    elif sys.argv[1] == "bob":
        sb = randrange(0, lB^eB)
        H = PB + sb * QB
        EB, _, phiB_PA, phiB_QA = prime_power_isogeny(E, H, lB, eB, PA, QA)

        
        phiB_PAx, phiB_PAy = encode_p2(phiB_PA[0]), encode_p2(phiB_PA[1])
        phiB_QAx, phiB_QAy = encode_p2(phiB_QA[0]), encode_p2(phiB_QA[1])
        a, b = encode_p2(EB.a4()), encode_p2(EB.a6())
        print(json.dumps({
            "U": {"x": phiB_PAx, "y": phiB_PAy},
            "V": {"x": phiB_QAx, "y": phiB_QAy},
            "E": {"a": a, "b": b},
        }))

        params = json.loads(input())

        a, b = decode_p2(params['E']['a']), decode_p2(params['E']['b'])
        EA = EllipticCurve(F, [a, b])

        phiA_PB = EA(decode_p2(params['U']['x']), decode_p2(params['U']['y']))
        phiA_QB = EA(decode_p2(params['V']['x']), decode_p2(params['V']['y']))
        H = phiA_PB + sb * phiA_QB
        EAB, _, _, _ = prime_power_isogeny(EA, H, lB, eB)

        shared = EAB.j_invariant()
        print("shared key is:", shared, file=sys.stderr)

Alice視点でコードを見てみます。

まず、楕円曲線の作り方からE.genはl_A^{e_A}l_B^{e_B}を位数とします。 したがって、 P_A, Q_Aはそれぞれl_A^{e_A}-ねじれ点になります。 P_A, Q_Aは線形独立なので H = P_A + s_A Q_Aもまたl_A^{e_A}-ねじれ点になります。

Bobからもらった点を使い\phi'_A = E_B / \langle \phi_B(P_A) + s_A\phi_B(Q_A) \rangleが求まるので、E_{AB}=\phi'_B(E_A)が計算できます。 Bobも同様の計算で、最終的に同じ楕円曲線が求まるため、例えばj不変量を鍵として共有できます。

これで無事SIDHを実装できましたが、CTFer的にはSIDHの安全性について議論したいです。 講義資料にはSIDHでやってはいけないnのことが書かれており、今後SIDH問題に遭遇したら（pwnerなので一生遭遇しなさそうだが）役立ちそうです。

この中でGPST Attackというものが宿題になっていたため解きます。 GPST Attackとは、同じsecretを使いまして何度も鍵交換できて、鍵交換の成功・失敗をオラクルとして得られるときにsecretが求まる攻撃手法です。

BobがAliceに渡す\phi_B(Q_A)をl_A^{e_A-1}\phi_B(P_A) + \phi_B(Q_A)にしてみます。 すると、Aliceは

E_{BA}=E_B / \langle \phi_B(P_A) + s_A(l_A^{e_A-1}\phi_B(P_A) + \phi_B(Q_A)) \rangle

を計算することになります。ここで、s_A l_A^{e_A-1}\phi_B(P_A)の位数は2なので、この項はs_Aが偶数なら\mathcal{O}に、そうでなければ別の点に移ります。 したがって、鍵共有に成功すればs_Aが偶数であることが分かります。

でもこれでが偶数か奇数かしか分かりません。 今回 l_Aが2であることを利用すると、次のように送る点を調整できます。

\phi_B(P_A) \rightarrow \phi_B(P_A) - 2^{n-i-1}K_i \phi_B(Q_A)

\phi_B(Q_A) \rightarrow (1 + 2^{n-i-1})\phi_B(Q_A)

実際にalice側で計算してみると

E_{BA} = E_B / \langle (\phi_B(P_A) - 2^{n-i-1}K_i \phi_B(Q_A)) + s_A(1 + 2^{n-i-1})\phi_B(Q_A) \rangle

E_{BA} = E_B / \langle \phi_B(P_A) + s_A\phi_B(Q_A) + 2^{n-i-1}(s_A - K_i)\phi_B(Q_A) \rangle

となり、iビット目のときお邪魔項の位数が2iになってくれています。 したがって、sA-Kiで下の方を0にしておけば、sAのi+1ビット目が0のときのみ無限遠点に飛びます。

実装してみましょう。

import sys
import json
import os
from ptrlib import *

def l_isogeny(K):
    phi = EllipticCurveIsogeny(K.curve(), K)
    return phi

def prime_power_isogeny(E, K, l, e, P=None, Q=None):
    for i in range(e):
        phi = l_isogeny(l^(e-i-1) * K)
        E = phi.codomain()
        K = phi(K)
        if P is not None:
            P = phi(P)
        if Q is not None:
            Q = phi(Q)
    return E, K, P, Q


(lA, eA), (lB, eB) = (2, 250), (3, 159)
p = lA**eA * lB**eB - 1
assert is_prime(p)

F = GF(p**2, "z")
E = EllipticCurve(F, [1, 0])
PA, QA = lB**eB * E.gen(0), lB**eB * E.gen(1)  
PB, QB = lA**eA * E.gen(0), lA**eA * E.gen(1)  

def encode_p2(v):
    return [int(x) for x in list(v.polynomial())]

def decode_p2(xs):
    return F(xs)

s = 5963
EB, _, U, V = prime_power_isogeny(E, PB + s*QB, lB, eB, PA, QA)

known = 0
n = 250
for i in range(n):
    sock = Process(["sage", "chall.sage"])

    evil_U = U - int(2^(n-i-1)*known) * V
    evil_V = int(1 + 2^(n-i-1)) * V

    sock.sendline(json.dumps({
        "U": {"x": encode_p2(evil_U[0]), "y": encode_p2(evil_U[1])},
        "V": {"x": encode_p2(evil_V[0]), "y": encode_p2(evil_V[1])},
        "E": {"a": encode_p2(EB.a4()), "b": encode_p2(EB.a6())},
    }))

    params = json.loads(sock.recvline().decode())
    EA = EllipticCurve(F, [decode_p2(params["E"]["a"]), decode_p2(params["E"]["b"])])
    UA = EA(decode_p2(params["U"]["x"]), decode_p2(params["U"]["y"]))
    VA = EA(decode_p2(params["V"]["x"]), decode_p2(params["V"]["y"]))

    EBA, _, _, _ = prime_power_isogeny(E, UA + s*VA, lB, eB)
    shared = EBA.j_invariant()

    key = sock.recvlineafter(": ").decode()
    if key == str(shared):
        bit = 0
    else:
        bit = 1
    known |= bit << i
    print(bin(known), bin(ord("}")))

    sock.close()

これでこの講義のすべてを理解しました。

>>> int.to_bytes(0b1111001011011110110001101101000011010010110001101100001011011010111000001111011011101010110111101110101011011110101111101100110011010010111001101101000010111110110110001101001011001100110010101111101, 64, "big")
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00yochicamp{uouo_fish_life}'

[ptr-yudai] 猫たちと学ぶ量子コンピュータ

昔楕円曲線は私の担当だったのですが、yoshi-campでCrypto勢に知識をstd::moveしたのが成功したため、今年は量子コンピュータの知識をstd::moveして今後CTFで私が楽できるようにする講義です。

内容は

となっています。160ページ以上作った*3のでそもそも全部やる予定はありませんでしたが、当日は3章まで終わらせました。

どうぶつさんがいるので、すいすい学べる教材

例題を解いてもらいながら、量子回路の読み方やテレポーテーション系の基礎的な量子もつれ応用は理解してもらいました。 最後にBSides Ahmedabad CTF 2021で出したqunknownというゲートテレポーテーションの問題を全員に解いてもらってお開きにしました。

今後は4章からを復習会でやります。

夜

崖を降りて晩ごはんを入手しました。 50個入りみたいなでかい餃子パッケージなどを購入して満腹。

夜は卓球とかハゲタカとか将棋とかをやりました。

次回Day 2-3の参加記は

  • もぐら君、死す
  • 深刻な水不足
  • 焼き肉がおいしい

の三本です！


文章来源: https://ptr-yudai.hatenablog.com/entry/2022/12/13/235034
如有侵权请联系:admin#unsafe.sh