はじめに

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

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

はじめに
yoshi-campって何？
yoshi-camp
- 開催地決定
- Day 0
  - 会場まで
  - 会場着
- Day 1
  - 朝
  - [theoremoon] 猫と学ぶ同種写像暗号
  - [ptr-yudai] 猫たちと学ぶ量子コンピュータ
  - 夜
次回予告

yoshi-campって何？

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

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

yoshi-camp

開催地決定

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

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

Day 0

会場まで

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

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

会場着

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

yoshi-camp 2022 winter参加記【Day 0-1】 — 第一犠牲者

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

Day 1

朝

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

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

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

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

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

有利多項式で表せる
全射
ϕ(OE)=OE′ϕ(OE)=OE′

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

E(Fp)E(Fp)とH∈E(¯Fp)H∈E(F¯p)が与えられたとき、kerϕ=⟨H⟩ker⁡ϕ=⟨H⟩となる同種写像は同型を除き一意に定まるという基本命題があると説明されていました。そしてこの写像の計算は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するにはl^e-isogenyが欲しいのですが、そんなでかい値のdivision_polynomialを求めようとすると計算が終わりません。そこで、生成元と曲線を移しながら、l-isogenyをe回計算するとl^e-isogenyになるようです。原理は理解できませんでした。

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

これでl^e-isogenyが計算できます。まず、prime_power_isogenyにはl^e-ねじれ点を渡します。これはよく分からなかったのですが、見かねた講師が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はもともとl^e-ねじれ点だったため、l^e-i-1倍するとl-ねじれ点になります。これをfor文でe回繰り返せば、l^e-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 - 1E = EllipticCurve(GF(p^2), [1, 0])K = E.gen(0)prev_K = Nonefor c in message:for i in range(8):bit = (c >> i) & 1next_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 = Kif 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暗号の場合、同種写像問題というもので安全性を証明しています。

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

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

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

import sysimport jsondef l_isogeny(K):phi = EllipticCurveIsogeny(K.curve(), K)return phidef 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# public parameters(lA, eA), (lB, eB) = (2, 91), (3, 57)p = lA**eA * lB**eB - 1assert 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) # PA, QA \in E[lA**eA]PB, QB = lA**eA * E.gen(0), lA**eA * E.gen(1) # PB, QB \in E[lB**eB]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__':# generate pub/priv parametersif sys.argv[1] == "alice":sa = randrange(0, lA^eA)H = PA + sa * QAEA, _, phiA_PB, phiA_QB = prime_power_isogeny(E, H, lA, eA, PB, QB)# exchange parametersphiA_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_QAEBA, _, _, _ = 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 * QBEB, _, phiB_PA, phiB_QA = prime_power_isogeny(E, H, lB, eB, PA, QA)# exchange parametersphiB_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_QBEAB, _, _, _ = prime_power_isogeny(EA, H, lB, eB)shared = EAB.j_invariant()print("shared key is:", shared, file=sys.stderr)

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

まず、楕円曲線の作り方からE.genはleAAleBBlAeAlBeBを位数とします。したがって、PA,QAPA,QAはそれぞれleAAlAeA-ねじれ点になります。 PA,QAPA,QAは線形独立なのでH=PA+sAQAH=PA+sAQAもまたleAAlAeA-ねじれ点になります。

Bobからもらった点を使いϕ′A=EB/⟨ϕB(PA)+sAϕB(QA)⟩ϕA′=EB/⟨ϕB(PA)+sAϕB(QA)⟩が求まるので、EAB=ϕ′B(EA)EAB=ϕB′(EA)が計算できます。 Bobも同様の計算で、最終的に同じ楕円曲線が求まるため、例えばj不変量を鍵として共有できます。

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

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

BobがAliceに渡すϕB(QA)ϕB(QA)をleA−1AϕB(PA)+ϕB(QA)lAeA−1ϕB(PA)+ϕB(QA)にしてみます。すると、Aliceは

EBA=EB/⟨ϕB(PA)+sA(leA−1AϕB(PA)+ϕB(QA))⟩EBA=EB/⟨ϕB(PA)+sA(lAeA−1ϕB(PA)+ϕB(QA))⟩

を計算することになります。ここで、sAleA−1AϕB(PA)sAlAeA−1ϕB(PA)の位数は2なので、この項はsAsAが偶数ならOOに、そうでなければ別の点に移ります。したがって、鍵共有に成功すればsAsAが偶数であることが分かります。

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

ϕB(PA)→ϕB(PA)−2n−i−1KiϕB(QA)ϕB(PA)→ϕB(PA)−2n−i−1KiϕB(QA)

ϕB(QA)→(1+2n−i−1)ϕB(QA)ϕB(QA)→(1+2n−i−1)ϕB(QA)

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

EBA=EB/⟨(ϕB(PA)−2n−i−1KiϕB(QA))+sA(1+2n−i−1)ϕB(QA)⟩EBA=EB/⟨(ϕB(PA)−2n−i−1KiϕB(QA))+sA(1+2n−i−1)ϕB(QA)⟩

EBA=EB/⟨ϕB(PA)+sAϕB(QA)+2n−i−1(sA−Ki)ϕB(QA)⟩EBA=EB/⟨ϕB(PA)+sAϕB(QA)+2n−i−1(sA−Ki)ϕB(QA)⟩

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

実装してみましょう。

import sysimport jsonimport osfrom ptrlib import *def l_isogeny(K):phi = EllipticCurveIsogeny(K.curve(), K)return phidef 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# public parameters(lA, eA), (lB, eB) = (2, 250), (3, 159)p = lA**eA * lB**eB - 1assert 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) # PA, QA \in E[lA**eA]PB, QB = lA**eA * E.gen(0), lA**eA * E.gen(1) # PB, QB \in E[lB**eB]def encode_p2(v):return [int(x) for x in list(v.polynomial())]def decode_p2(xs):return F(xs)s = 5963EB, _, U, V = prime_power_isogeny(E, PB + s*QB, lB, eB, PA, QA)known = 0n = 250for i in range(n):sock = Process(["sage", "chall.sage"])evil_U = U - int(2^(n-i-1)*known) * Vevil_V = int(1 + 2^(n-i-1)) * Vsock.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 = 0else:bit = 1known |= bit << iprint(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}'