SECCON

成り行き

ptr-yudai：「問題を作らないか？」

bless(author:ptr-yudai,kanon)[9 solves]

ptr-yudai：「pairing暗号を出さないか？」

まぁこんな感じです。アイデアとしてDBB問題を出すということになりました。また、ptr-yudaiさんがyoshicampでpairing暗号のスクリプトを軽く書いていたので、それを基に協業で作問することにしました。

        
      
import json
import os

FLAG = os.getenv("FLAG", "ctf4b{*** REDACTED ***}").encode()

# https://neuromancer.sk/std/bls/BLS12-381
p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
q = 0x73EDA753299D7D483339D80809A1D80553BDA402FFFE5BFEFFFFFFFF00000001
F1 = GF(p)
E1 = EllipticCurve(F1, (0, 4))
G1 = E1(0x17F1D3A73197D7942695638C4FA9AC0FC3688C4F9774B905A14E3A3F171BAC586C55E83FF97A1AEFFB3AF00ADB22C6BB, 0x08B3F481E3AAA0F1A09E30ED741D8AE4FCF5E095D5D00AF600DB18CB2C04B3EDD03CC744A2888AE40CAA232946C5E7E1)

F2 = GF(p^2, 'x', modulus=x^2+1)
E2 = EllipticCurve(F2, (0, 4*(1+F2.gen())))
G2 = E2.random_point()

def to_dict(P):
    if P.base_ring() == F1:
        return {'x': int(P[0]), 'y': int(P[1])}
    else:
        Px, Py = P[0].polynomial(), P[1].polynomial()
        return {'x': [int(Px[0]), int(Px[1])], 'y': [int(Py[0]), int(Py[1])]}

challenges = []
for c in FLAG:
    s, t = randrange(q), randrange(q)
    challenges.append({
        'P': to_dict(s*G1),
        'Q': to_dict(t*G2),
        'R': to_dict(c*s*t*G2)
    })

with open("output.json", "w") as f:
    json.dump(challenges, f)

analysis

てなわけで、writupです。

今回使った曲線はpairing friendly curveの一つである、BLS12-381です。(確か、コメントでyudaiさんが入れていたような気が）内容としては、$\mathbb{G}_1,\mathbb{G}_2$上にある有理点をペアリング写像($e:\mathbb{G}_1×\mathbb{G}_2→\mathbb{G}_3$)して$\mathbb{G}_3$で拡大体上の計算で判定を頑張ろうという内容だったように思います。

また、任意の$u, u_1, u_2\in \mathbb{G}_1, v, v_1, v_2\in \mathbb{G}_2$に対して以下が成り立ち、ペアリング写像には双線形性という性質を持ちます。（非退化は省略します。）

$e(u_1+u_2,v)=e(u_1,v) + e(u_2,v)$
$e(u,v_1+v_2)=e(u,v_1) + e(u,v_2)$

上記の性質を繰り返し適応することで以下の性質を導けます。これを利用して今回の問題を解いていきます。

$e(u^a,v^b)=e(u^b,v^a)=e(u,v)^{ab}$

コード的には$s, t \leftarrow Z_q$という乱数をとり$c_i$がflagのi番目であるとき、$P = s*G_1, Q = t*G_2, R = c*s*t*G_2$が与えられます。なので、$e(P,Q)^{c_i} = e(G_1,G_2)^{stc_i} = e(G_1,R)$

よって、$e(P,Q),e(G_1,R)$のペアリングを計算してあげれば後はブルートフォースで$c_i$が求まりそうですね。

        
      
from tqdm import tqdm

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
F = GF(p)
E = EllipticCurve(F, (0, 4))
q = 0x73EDA753299D7D483339D80809A1D80553BDA402FFFE5BFEFFFFFFFF00000001
G1 = E(0x17F1D3A73197D7942695638C4FA9AC0FC3688C4F9774B905A14E3A3F171BAC586C55E83FF97A1AEFFB3AF00ADB22C6BB, 0x08B3F481E3AAA0F1A09E30ED741D8AE4FCF5E095D5D00AF600DB18CB2C04B3EDD03CC744A2888AE40CAA232946C5E7E1)
k = 12

assert (p ^ k - 1) % q == 0

F2 = GF(p ^ 2, 'l', modulus=x ^ 2 + 1)
l = F2.gen()
E2 = EllipticCurve(F2, (0, 4 * (1 + l)))

F12 = GF(p ^ 12, 'w', modulus=x ^ 12 - 2 * x ^ 6 + 2)
w = F12.gen()
E12 = EllipticCurve(F12, (0, 4))

G1_12 = E12(*G1)


# Load output
output = eval(open("output.json", "r").read())

Ps = [E(F(xy["P"]["x"]), F(xy["P"]["y"])) for xy in output]
Qs = [E2(F2(xy["Q"]["x"][0] + xy["Q"]["x"][1] * l), F2(xy["Q"]["y"][0] + xy["Q"]["y"][1] * l)) for xy in output]
Rs = [E2(F2(xy["R"]["x"][0] + xy["R"]["x"][1] * l), F2(xy["R"]["y"][0] + xy["R"]["y"][1] * l)) for xy in output]


def twist(Px, Py):
    z = w ^ -1
    a, b = list(Px.polynomial())
    Px = a + b * (w ^ 6 - 1)
    a, b = list(Py.polynomial())
    Py = a + b * (w ^ 6 - 1)
    return z ^ 2 * F12(Px), z ^ 3 * F12(Py)


flag = b""
for P, Q, R in tqdm(list(zip(Ps, Qs, Rs))):
    P12 = E12(*P)
    Q12 = E12(twist(*(Q.xy())))
    R12 = E12(twist(*(R.xy())))
    mu1 = P12.tate_pairing(Q12, n=q, k=k)

    for ci in tqdm(range(20, 0x7f)):
        mu2 = G1_12.tate_pairing(R12, n=q, k=k)
        if mu1**ci == mu2:
            print("Found!")
            flag += bytes([ci])
            print(flag)
            break
    else:
        print("Ha?")
        exit(1)
print(flag)

b'ctf4b{wH1ch_p4iR1ng_d0_U_L1ke_tH3_m0st?}'

Try hard in my style(author:kanon)[10 solves]

ptr-yudai：「暗号を出さないか？」

まぁこれもこんな感じです。アイデアとしてmedium以上なら知ってほしい知識を組み合わせて解いてほしかったという流れです。

        
      
import os
from Crypto.Util.number import *
from random import randint
FLAG = os.getenv("FLAG", "ctf4b{*** REDACTED ***}").encode()

e, nbit = 17, 512
m = bytes_to_long(FLAG)

p, q = getPrime(nbit), getPrime(nbit)
n = p * q

assert m < n

s = randint(0, 2**nbit)
t1, t2 = randint(0, 2**nbit), randint(0, 2**nbit)

c1 = pow(m + s, e, n)
c2 = pow(m + s * t1, e, n)
c3 = pow(m * t2 + s, e, n)

print(f"{e=}")
print(f"{n=}")
print(f"{t1=}")
print(f"{t2=}")
print(f"{c1=}")
print(f"{c2=}")
print(f"{c3=}")

analysis

暗号に用いられている式は以下の3つです。

$f1 = (m + s)^e \mod n$
$f2 = (m + s * t_1)^e \mod n$
$f3 = (m * t_2 + s)^e \mod n$

Franklin-Reiter’s Related Message Attackを用いたいところですが2変数ということもあり単純には用いられません。なので、1変数にします。

１変数にするには簡単で、Gröbner basisを用いるかresultantを用いるかの二択です。（これらは変数や次数が多いほど計算が遅くなります。）

今回はresultant日本語で終結式 - Wikipediaと呼ばれるものを用いていきます。（Gröbner basisでも解けるとは思います。）これはシルヴェスター行列の行列式を求めればよいです。（詳しい理論はググってください）

さて、resultantで1変数を消去し、変数$m$だけの方程式が2本あるので、これにpolynomial gcdを適応し、次数を落としていくことで$m^e = a$といったような形の式が求まります。

これは、17回サーバに接続し$m^{17} \mod n_i $を17個集めればCRT（中国剰余定理を用いて解くことができます。）なので、solver自体はすごくきれいに書けます。

        
      
from ptrlib import remote, process
from gmpy2 import iroot
from Crypto.Util.number import *
# https://github.com/jvdsn/crypto-attacks/blob/master/shared/polynomial.py
from shared.polynomial import fast_polynomial_gcd

def resultant(f1, f2, var):
    return Matrix(f1.sylvester_matrix(f2, var)).determinant()

flag17,ns =[], []

for i in range(17):
    io = process(["python3","chall.py"])
    exec(io.recvline().decode())
    exec(io.recvline().decode())
    exec(io.recvline().decode())
    exec(io.recvline().decode())
    exec(io.recvline().decode())
    exec(io.recvline().decode())
    exec(io.recvline().decode())
    io.close()

    PR.<m,s> = PolynomialRing(Zmod(n))
    f1 = (m + s)^e - c1
    f2 = (m + s*t1)^e - c2
    f3 = (m*t2 + s)^e - c3
    
    f12 = resultant(f1,f2,s)
    f13 = resultant(f1,f3,s)
    f = fast_polynomial_gcd(f12.univariate_polynomial(),f13.univariate_polynomial())
    print(f)
    flag17.append(int(-f[0]))
    ns.append(int(n))
m17 = CRT(flag17,ns)
print(long_to_bytes(int(iroot(int(m17),17)[0])))

ctf4b{1f_y0u'r3_4n_1n73rm3d1473_b3y0nd_b361nn3r,_17'5_345y!_y4y}

最後に

難しいと感じたかもしれませんが、試行錯誤することでいろんな知識や手法が身に付きますのであきらめずにtry hard in my style!!

p.s. 次はXXXXCTFでお会いしましょう！！ではまたﾉｼ

SECCON beginner crypto

SECCON

成り行き

bless(author:ptr-yudai,kanon)[9 solves]

analysis

Try hard in my style(author:kanon)[10 solves]

analysis

最後に

Further Reading

zer0pts 2023 writeup

十月初週のupsolve

十月初週のupsolve