はじめに
今年もyoshi-campを開催しました。
今回は久しぶりのオンサイト開催で、zer0pts外部からの参加者も募集しました。 結果として、連絡してくれた./VespiaryのXornetさんとネさんを招待しました。
yoshi-campって何?
もともとはyoshikingがセキュリティキャンプに落ちたことを受け、セキュリティキャンプよりも高度な講義をyoshikingに受けさせる目的で開催されました。 ちなみに今年は私がGCCのチューターに落ちました。さようならGCC。
yoshi-campの講義はMooreの法則で年々難易度がインフレしています。 インフレしすぎて今年は全然実装が追いつかなかったので、とりあえず今回は初日終了までの内容を出して、後から2日目以降を公開したいと思います。
yoshi-camp
開催地決定
今までは大学関連施設を借りて開催していましたが、宿泊場所から会場までの移動時間が無駄という理由で、今回はでかい家を借りました。 場所は最大10人程度が泊まれる箱根の別荘にしました。 候補はいろいろありましたが、富士山が見える部屋や全面ガラス張りの石風呂など施設が充実していたため全力でこの別荘を取りました。
当日までに持ち運びできるホワイトボードなどを購入しました。買っててよかったです。
Day 0
会場まで
Day 1にみんなが早くチェックインできるよう、私は前日に家を開けました。 秋葉原で5m HDMIケーブルを買うついでに将棋盤を買い、将棋盤を買ったついでにハゲタカというカードゲームを買いました。
新宿から箱根湯本まで行き、会場に行く前に温泉に入りました。 会場までは山を登り左右に揺れまくる激酔いバスで一本です。
会場着
今回借りた家は基本的にすべてが良かったのですが、周辺の店から家までの坂が大変でした。
事前にホストから、HDMIが使えるでかいテレビがある情報を得ていたので、ディスプレイのセットアップやホワイトボードの配置を考えた後、講義資料の修正をしていました。 家が広すぎて寂しかったです。
Day 1
朝
まず朝にyoshikingが到着しました。 卓球台があったので卓球を極めて、あとはジェンガとかしてました。*1
その後theoremoon、Xornet、ネさんの順番に到着したと思います。 mitsu大教授はDay 2から来ました。
[theoremoon] 猫と学ぶ同種写像暗号
今流行りの激アツ(炎上)プロトコルことSIDH(Supersingular Isogeny Diffie-Hellman)のお勉強です。
今回扱う同種写像は楕円曲線から別の楕円曲線への写像で、次の性質を満たすらしいです。
有利多項式なので次数が定義でき、次数lの変換をl-isogenyと呼ぶそうです。
とが与えられたとき、となる同種写像は同型を除き一意に定まるという基本命題があると説明されていました。 そしてこの写像の計算は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記事書いてくれています。
それはそう。
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暗号の場合、同種写像問題というもので安全性を証明しています。
【同種写像問題】
とが与えられたとき、からを求めるのは困難である。
シンプルで大変よろしい。 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 # public parameters (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) # 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 parameters 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) # exchange parameters 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) # exchange parameters 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
はを位数とします。
したがって、はそれぞれ-ねじれ点になります。
は線形独立なのでもまた-ねじれ点になります。
Bobからもらった点を使いが求まるので、が計算できます。 Bobも同様の計算で、最終的に同じ楕円曲線が求まるため、例えばj不変量を鍵として共有できます。
これで無事SIDHを実装できましたが、CTFer的にはSIDHの安全性について議論したいです。 講義資料にはSIDHでやってはいけないnのことが書かれており、今後SIDH問題に遭遇したら(pwnerなので一生遭遇しなさそうだが)役立ちそうです。
この中でGPST Attackというものが宿題になっていたため解きます。 GPST Attackとは、同じsecretを使いまして何度も鍵交換できて、鍵交換の成功・失敗をオラクルとして得られるときにsecretが求まる攻撃手法です。
BobがAliceに渡すをにしてみます。 すると、Aliceは
を計算することになります。ここで、の位数は2なので、この項はが偶数ならに、そうでなければ別の点に移ります。 したがって、鍵共有に成功すればが偶数であることが分かります。
でもこれでが偶数か奇数かしか分かりません。 今回が2であることを利用すると、次のように送る点を調整できます。
実際にalice側で計算してみると
となり、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 # public parameters (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) # 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 = 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の参加記は
- もぐら君、死す
- 深刻な水不足
- 焼き肉がおいしい
の三本です!