TSG CTF (babe-sidh)

本日は
脆弱エンジニアのAdvent Calendar2３日目です。

TSG CTFお疲れ様でした。
A4xn=B1kRAというチームで参戦し、総合17位/国内9位でした。
Cryptoの面倒を見ていたのですが、そこで0solveの問題が出てきました。それを頑張ってその後解いたのでそれを書き記します。

問題概要

• $F_{p^2}$上の楕円曲線$E0: y^2 = x^3 + x$ $(p = 2^a * 3^b - 1), a = 0xD8, b = 0x89$

• 奇数$q$が選ばれ、$deg = q(2^a - q)$が、2, 3と互いに素

• さらに$twist[0..2]$が選ばれる

• 次数$q(2^a - q) * 3^b$のendomorohismを用いて３つの公開曲線$E_{A_{j}}$と点$(P_{A_{j}}, Q_{A_{j}})$, $(j = 0..2)$が構成される

• 目標は$q, twist[i]$を復元すること

#!/usr/bin/env sage
# -*- coding: utf-8 -*-

import secrets
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from random import SystemRandom
import hashlib
import binascii
randgen = SystemRandom()
randint = randgen.randint

def encrypt_aes_ctr(plaintext, key):
    """
    Encrypts data using AES-CTR mode.
    Returns (nonce, ciphertext)
    """
    cipher = AES.new(key, AES.MODE_CTR)
    ciphertext = cipher.encrypt(plaintext)
    return cipher.nonce, ciphertext

def decrypt_aes_ctr(nonce, ciphertext, key):
    """
    Decrypts data using AES-CTR mode with the correct nonce.
    Returns the original plaintext.
    """
    cipher = AES.new(key, AES.MODE_CTR, nonce=nonce)
    
    plaintext = cipher.decrypt(ciphertext)
    return plaintext

def cornacchia(q, M_prime):
    QF = gp.Qfb(1,0,q)
    try:
        xy = QF.qfbsolve(M_prime)
        x,y = list(map(lambda x:ZZ(x),xy))
    except ValueError:
        return None
    assert x**2+q*y**2 == M_prime
    return (abs(x),abs(y))

def fullrepresentinteger(M,p):
    QF = gp.Qfb(1, 0, 1)
    while True:
        mp = isqrt(M/p)//4
        zp = ZZ(randgen.randint(0,mp))
        tp = ZZ(randgen.randint(0,mp))
        Mp = M-p*(zp^2+tp^2)
        if Mp <= 0:
            continue
        if not Mp.is_prime() or Mp % 4 != 1:
            continue
        try:
            xy = QF.qfbsolve(Mp)
        except ValueError:
            print("there is no sols")
            continue
        xp,yp = list(map(lambda x:ZZ(x),xy))
        assert M == xp^2+yp^2+p*(zp^2+tp^2)
        return (xp,yp,zp,tp)
def endomorphism(M,p,ec,i):
    x,y,z,t = fullrepresentinteger(M,p)
    pi = ec.frobenius_isogeny()
    ii = ec.isomorphism(i)
    return x+y*ii+z*pi+t*ii*pi
def find_p_gen(ec,p,e):
    elem_order = p**e
    gens = []
    while len(gens)<2:
        P = ec.random_element()
        tmp = ec.order()//(elem_order**2)
        P = tmp*P
        assert p**e*P == ec.zero()
        if (elem_order//p)*P != ec.zero():
            if len(gens) == 0:
                gens.append(P)
            elif (elem_order//p)*gens[0]!=(elem_order//p)*P:
                gens.append(P)
    return gens

a = 0xd8
b = 0x89
p = 2**a*3**b-1
k.<i> = GF((p,2),modulus=[1,0,1])
ec0 = EllipticCurve(k, [1, 0])

while True:
    q = randint(1,2**a-1)
    secret_degree = q*(2**a-q)
    if secret_degree % 2 != 0 and secret_degree % 3 != 0:
        break
P0,Q0 = find_p_gen(ec0,2,a)
R0,S0 = find_p_gen(ec0,3,b)

true_ans = []
twists = []
for _ in range(3):
    tmp = secrets.randbelow(2**a)
    while tmp % 2 == 0:
        tmp = secrets.randbelow(2**a)
    twists.append(tmp)

endm_deg = q*(2**a-q)*3**b

key = hashlib.sha3_256(long_to_bytes(q)+long_to_bytes(twists[0])+long_to_bytes(twists[1])+long_to_bytes(twists[2])).digest()
FLAG = os.environ.get("FLAG", "TSGCTF{DUMMY}")

nonce, ciphertext = encrypt_aes_ctr(FLAG.encode(), key+b'0'*(32-len(key)))

print("ciphertext =","bytes.fromhex(\""+binascii.hexlify(ciphertext).decode()+"\")")
print("nonce =","bytes.fromhex(\""+binascii.hexlify(nonce).decode()+"\")")


print(f"E0 = {ec0.a_invariants()}")
print(f"P0,Q0 = {P0.xy()}, {Q0.xy()}")
for j in range(3):
    endm = endomorphism(secret_degree*3^b,p,ec0,i)
    Pp,Qp = endm(P0),endm(Q0)
    Rp,Sp = endm(R0),endm(S0)

    assert endm.dual()(Rp) == endm.dual()(Sp) == ec0.zero()
    isogeny = ec0.isogeny((Rp,Sp))
    EA = isogeny.codomain()

    assert isogeny(Rp) == isogeny(Sp) == EA.zero()

    tmp = pow(3^b,-1,2^a)
    PA,QA = twists[j]*tmp*isogeny(Pp),twists[(j+1)%3]*tmp*isogeny(Qp)
    print(f"EA{j} = {EA.a_invariants()}")
    print(f"PA{j},QA{j} = {PA.xy()}, {QA.xy()}")

解法

#!/usr/bin/env sage
# -*- coding: utf-8 -*-

import os
import re
import sys
import hashlib
from sage.all import *
from Crypto.Cipher import AES

BASE_DIR = os.path.dirname(os.path.abspath(__file__))
sys.path.append(os.path.join(BASE_DIR, "two-isogenies", "Theta-SageMath"))

from utilities.fast_sqrt import sqrt_Fp2
from theta_structures.couple_point import CouplePoint
from theta_isogenies.product_isogeny_sqrt import EllipticProductIsogenySqrt
from utilities.strategy import optimised_strategy
from utilities.utils import speed_up_sagemath

speed_up_sagemath()

Aexp = 0xD8
Bexp = 0x89
p = 2**Aexp * 3**Bexp - 1
k.<i> = GF((p, 2), modulus=[1, 0, 1])
mord = 2**Aexp


def parse_point(s):
    return eval(s, {"i": i})


def parse_output(text):
    m = re.search(r"ciphertext = bytes.fromhex\(\"([0-9a-f]+)\"\)", text)
    if not m:
        raise ValueError("ciphertext not found")
    ct = bytes.fromhex(m.group(1))
    m = re.search(r"nonce = bytes.fromhex\(\"([0-9a-f]+)\"\)", text)
    if not m:
        raise ValueError("nonce not found")
    nonce = bytes.fromhex(m.group(1))

    m = re.search(r"E0 = \(([^\)]*)\)", text)
    if not m:
        raise ValueError("E0 not found")
    E0 = EllipticCurve(k, eval("(" + m.group(1) + ")"))

    m = re.search(r"P0,Q0 = \((.*)\), \((.*)\)", text)
    if not m:
        raise ValueError("P0,Q0 not found")
    P0 = E0(parse_point("(" + m.group(1) + ")"))
    Q0 = E0(parse_point("(" + m.group(2) + ")"))

    EA = []
    PA = []
    QA = []
    for j in range(3):
        m = re.search(r"EA%d = \(([^\)]*)\)" % j, text)
        if not m:
            raise ValueError("EA%d not found" % j)
        EAj = EllipticCurve(k, eval("(" + m.group(1) + ")"))

        m = re.search(r"PA%d,QA%d = \((.*)\), \((.*)\)" % (j, j), text)
        if not m:
            raise ValueError("PA%d,QA%d not found" % (j, j))
        PAj = EAj(parse_point("(" + m.group(1) + ")"))
        QAj = EAj(parse_point("(" + m.group(2) + ")"))

        EA.append(EAj)
        PA.append(PAj)
        QA.append(QAj)

    return ct, nonce, E0, P0, Q0, EA, PA, QA


def dlog_2power(h, g, a):
    # h = g^x in a 2^a-order subgroup (g generator)
    x = 0
    for k in range(a):
        hk = h * (g ** (-x))
        test = hk ** (2 ** (a - 1 - k))
        if test == -1:
            x += 2**k
    return x


def to_montgomery(E):
    # Convert short Weierstrass to Montgomery y^2 = x^3 + A x^2 + x.
    A4 = E.a4()
    A6 = E.a6()
    x = polygen(E.base_ring())
    f = x**3 + A4 * x + A6
    roots = f.roots()
    if not roots:
        raise ValueError("no root for Montgomery conversion")
    r = roots[0][0]
    A = 3 * r
    B = 3 * r**2 + A4

    u = sqrt_Fp2(sqrt_Fp2(B))
    found = False
    for mult in [1, -1, i, -i]:
        uu = u * mult
        if uu**4 == B:
            u = uu
            found = True
            break
    if not found:
        raise ValueError("no 4th root found")

    A_m = A / (u**2)
    Em = EllipticCurve(E.base_ring(), [0, A_m, 0, 1, 0])

    def iso(P):
        if P.is_zero():
            return Em(0)
        xP, yP = P.xy()
        return Em((xP - r) / (u**2), yP / (u**3))

    return Em, iso


def decrypt_with_key(key_bytes, nonce, ct):
    cipher = AES.new(key_bytes, AES.MODE_CTR, nonce=nonce)
    return cipher.decrypt(ct)


def recover_u_vals(t01, t12, t20):
    R = Zmod(mord)
    prod = (t01 * t12 * t20) % mord
    roots_T = [int(r) for r in R(prod).sqrt(all=True)]
    for T in roots_T:
        u0 = (T * inverse_mod(t12, mord)) % mord
        u1 = (T * inverse_mod(t20, mord)) % mord
        u2 = (T * inverse_mod(t01, mord)) % mord
        yield u0, u1, u2


def recover_q(E0m, P0m, Q0m, EA, PA, QA, u0, u1):
    strategy = optimised_strategy(Aexp - 2)
    for j in range(3):
        EmA, isoA = to_montgomery(EA[j])
        U = isoA(PA[j])
        V = isoA(QA[j])

        K1 = CouplePoint((-u0) * P0m, U)
        K2 = CouplePoint((-u1) * Q0m, V)
        try:
            Phi = EllipticProductIsogenySqrt((K1, K2), Aexp, strategy=strategy)
        except Exception:
            continue

        Uprime = Phi(CouplePoint(E0m(0), U))[0]
        Vprime = Phi(CouplePoint(E0m(0), V))[0]

        e0 = U.weil_pairing(V, mord)
        e1 = Uprime.weil_pairing(Vprime, mord)
        d = dlog_2power(e1, e0, Aexp)
        q = (-d) % mord
        if q % 2 == 1:
            return q
    return None


def int_to_bytes(x):
    n = int(x)
    ln = (n.bit_length() + 7) // 8
    return Integer(n).to_bytes(ln, "big")


def main():
    text = open(os.path.join(BASE_DIR, "output.txt")).read()
    ct, nonce, E0, P0, Q0, EA, PA, QA = parse_output(text)

    g = P0.weil_pairing(Q0, mord)
    vals = []
    for j in range(3):
        hj = PA[j].weil_pairing(QA[j], mord)
        x = dlog_2power(hj, g, Aexp)
        vals.append((-x) % mord)
    t01, t12, t20 = vals

    # E0 is already Montgomery (A=0), but keep the check
    if E0.a_invariants() == (0, 0, 0, 1, 0):
        E0m = E0
        P0m = P0
        Q0m = Q0
    else:
        E0m, iso0 = to_montgomery(E0)
        P0m = iso0(P0)
        Q0m = iso0(Q0)

    for u0, u1, u2 in recover_u_vals(t01, t12, t20):
        q = recover_q(E0m, P0m, Q0m, EA, PA, QA, u0, u1)
        if q is None:
            continue

        invq = inverse_mod(q, mord)
        tw0 = (u0 * invq) % mord
        tw1 = (u1 * invq) % mord
        tw2 = (u2 * invq) % mord

        key = hashlib.sha3_256(
            int_to_bytes(q)
            + int_to_bytes(tw0)
            + int_to_bytes(tw1)
            + int_to_bytes(tw2)
        ).digest()

        pt = decrypt_with_key(key, nonce, ct)
        if pt and pt.startswith(b"TSGCTF"):
            print(pt.decode())
            return

    raise RuntimeError("flag not found")


if __name__ == "__main__":
    main()
# TSGCTF{POKE 1s n0t fOR Pokemon Nor pocket}

手順1　Weil pairingする

公開点は次の形：

PA_j = twist[j] * (3^b)^(-1) * ψ_j(α(P0))
QA_j = twist[j+1] * (3^b)^(-1) * ψ_j(α(Q0))

• α は deg(α) = q(2^a - q)*3^b の endomorphism
• ψ_j は 3^b-isogeny
• (3^b)^(-1) が明示的に掛かっているので、m-torsion 上では ψ_j の 3^b 倍作用がキャンセルされる。

Weil pairing の基本性質：

e_m(ψ(P), ψ(Q)) = e_m(P, Q)^{deg(ψ)} (gcd(deg(ψ), m)=1)

α の m-torsion 作用は「±q 倍」になるので、結局

h_j := e_m(PA_j, QA_j)
= g^{± q^2 * twist[j] * twist[j+1]}.

ここで符号は isogeny の向きに依存するため、実装では

t_j = -dlog_g(h_j)

と置いて符号を統一。すると

t_j = q^2 * twist[j] * twist[j+1] (mod m).

手順2 ３本の$t_j$ から $u_i = q * twist[i]$を復元

3つ掛けると

t_01 t_12 t_20
= q^6 * (twist[0] * twist[1] * twist[2])^2 (mod m)

右辺は必ず平方になるので、Z/mZ で平方根が取れる：

T = q^3 * twist[0] * twist[1] * twist[2] (mod m).

これを使って

u0 = T / t12 = q * twist[0]
u1 = T / t20 = q * twist[1]
u2 = T / t01 = q * twist[2]

が求まる（t12 などは 2-adic 単数なので逆元が存在）。

※ m = 2^a なので平方根は複数候補があるが、後段の検証で正しいものだけが残る

手順3 kaniのkernelを公開情報だけで作る

$E_0[m] \times E_{A_{j}}$上にproduct pairingを定義：
$$
e_m^×((P1,P2),(Q1,Q2)) = e_m(P1,Q1) * e_m(P2,Q2)
$$
ここで、
$K1 = (-u0 * P0, PA_j)$, $K2 = (-u1 * Q0, QA_j)$
と置くと、

$$
e_m^×(K1, K2) = e_m(P0,Q0)^{u0*u1} * e_m(PA_j, QA_j)
$$

$= g^{u0*u1} * g^{t_j}$
$= 1$

$(t_j \equiv u_0 * u1 \pmod m)となり、<K1, K2>はmaximal isotropic subgroup。
よってkaniの定理により(2^a-2^a)-isogenyになる

$\phi: E_0 \times E_{A_j} \to F \times F'$が構成できる

手順4 image curveのpairingからqを取り出す

$U = P_{A_{j}}, V = Q_{A_{j}}$
とし、
$U' = \phi(0, U)[0], V' = \phi(0, V)[0]$
を計算する
ここで第一成分への写像は未知の$2^a$isogeny phi2の双対に一致するため、
$$e_m(U', V') = e_m(U, V)^{deg(phi2)}$$
が成り立つ。
構成上、$deg(phi1) = q$で補完的に
$deg(phi2) = 2^a - q \pmod m$となるので、
$$q \equiv -deg(phi2) \pmod m$$
が得られる

手順5 twistを復元

$q$がわかれば
$$
twist[i] = \frac{u_i}{q} \pmod m
$$
で全twistが求まる
鍵は、
$key = SHA3-256(q || twist[0] || twist[1] || teist[2])$
なのでAES-CTRを復元してフラグが得られる。