yoshi-camp 2022 winter参加記【Day 0-1】

WriteUp 2年前 (2022) admin

653 0 0

はじめに

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

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

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 \to E^{'}$ で、次の性質を満たすらしいです。

有利多項式で表せる
全射
$ϕ (O_{E}) = O_{E^{'}}$

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

$E (F_{p})$ と $H \in E ({\bar{F}}_{p})$ が与えられたとき、 $\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 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

これで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 – 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(‘\\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^{'} = ϕ (E)$ が与えられたとき、 $E, E^{'}$ から $ϕ$ を求めるのは困難である。

シンプルで大変よろしい。 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は $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からもらった点を使い $ϕ_{A}^{'} = E_{B} / ⟨ ϕ_{B} (P_{A}) + s_{A} ϕ_{B} (Q_{A}) ⟩$ が求まるので、 $E_{A B} = ϕ_{B}^{'} (E_{A})$ が計算できます。 Bobも同様の計算で、最終的に同じ楕円曲線が求まるため、例えばj不変量を鍵として共有できます。

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

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

BobがAliceに渡す $ϕ_{B} (Q_{A})$ を $l_{A}^{e_{A} - 1} ϕ_{B} (P_{A}) + ϕ_{B} (Q_{A})$ にしてみます。すると、Aliceは

$E_{B A} = E_{B} / ⟨ ϕ_{B} (P_{A}) + s_{A} (l_{A}^{e_{A} - 1} ϕ_{B} (P_{A}) + ϕ_{B} (Q_{A})) ⟩$

を計算することになります。ここで、 $s_{A} l_{A}^{e_{A} - 1} ϕ_{B} (P_{A})$ の位数は2なので、この項は $s_{A}$ が偶数なら $O$ に、そうでなければ別の点に移ります。したがって、鍵共有に成功すれば $s_{A}$ が偶数であることが分かります。

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

$ϕ_{B} (P_{A}) \to ϕ_{B} (P_{A}) - 2^{n - i - 1} K_{i} ϕ_{B} (Q_{A})$

$ϕ_{B} (Q_{A}) \to (1 + 2^{n - i - 1}) ϕ_{B} (Q_{A})$

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

$E_{B A} = E_{B} / ⟨ (ϕ_{B} (P_{A}) - 2^{n - i - 1} K_{i} ϕ_{B} (Q_{A})) + s_{A} (1 + 2^{n - i - 1}) ϕ_{B} (Q_{A}) ⟩$

$E_{B A} = E_{B} / ⟨ ϕ_{B} (P_{A}) + s_{A} ϕ_{B} (Q_{A}) + 2^{n - i - 1} (s_{A} - K_{i}) ϕ_{B} (Q_{A}) ⟩$

となり、iビット目のときお邪魔項の位数が2ⁱになってくれています。したがって、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で私が楽できるようにする講義です。

内容は

1章. 量子ビットとブロッホ球
2章. 量子ゲートと量子回路
3章. 量子もつれと応用
4章. 量子サブルーチン
5章. 量子アルゴリズム
6章. 量子鍵交換
7章. 量子誤り訂正（未完成）

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

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

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

夜

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

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

次回予告

次回Day 2-3の参加記は

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

の三本です！

*1:演習予定のDraperの量子回路がバグり散らかして修正していたが、諦めて遊び始めた。

*2:参加記を書きつつsage 9.8を速い速いマシンでビルドすると、なんと15分弱でビルドが終わりました。

*3:私のyoshi-campの資料は、見返せばすべて書いてある辞書を目指しています。

原文始发于Hatena Blog：yoshi-camp 2022 winter参加記【Day 0-1】

版权声明：admin 发表于 2022年12月14日下午10:56。
转载请注明：yoshi-camp 2022 winter参加記【Day 0-1】 | CTF导航

CTFSHOW第三届愚人杯WP

admin

299

ångstromCTF Writeup by VP-Union

admin

230

【WP】第一届“长城杯”网络安全大赛线上赛

admin

1,294

【一等奖方案】基于TPU平台实现人群密度估计赛题「SO-FAST」团队解题思路

admin

204

速看！*CTF 2022官方【WP】来了！

admin

1,521

赛题全解|第四届 RWCTF 体验赛 WriteUp

admin

1,727

暂无评论

您必须登录才能参与评论！

立即登录

暂无评论...

yoshi-camp 2022 winter参加記【Day 0-1】

はじめに

yoshi-campって何？

yoshi-camp

開催地決定

Day 0

会場まで

会場着

Day 1

朝

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

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

夜

次回予告

看雪2022 KCTF 秋季赛 | 第十一题设计思路及解析

流量分析之常见协议解题技巧

相关文章

暂无评论

相关文章

yoshi-camp 2022 winter参加記【Day 0-1】

はじめに

yoshi-campって何？

yoshi-camp

開催地決定

Day 0

会場まで

会場着

Day 1

朝

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

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

夜

次回予告

看雪2022 KCTF 秋季赛 | 第十一题设计思路及解析

流量分析之常见协议解题技巧

相关文章

暂无评论

广告位

相关文章