Processing math: 51%

Tags: elliptic dlp crypto 

Rating:

Delta Force Writeup

TSG CTF 2023 - crypto 341 - 6 solves

Commence Operation Delta!! Hint: Last part of this problem, discrete_log() function in sagemath is useful. Run ?discrete_log in sage CLI and read the document.

delta_force.tar.gz

Given Curve is Singular

We are given a curve in the form of Weierstrass form: E:y2+a1xy+a3y=x3+a2x2+a4x+a6 over integer modulo ring N=pq, where p and q are hidden.

By checking the discriminant is zero, we find that the given curve is singular.

def is_singular():
    b2 = a1**2 + 4 * a2
    b4 = 2 * a4 + a1 * a3
    b6 = a3**2 + 4 * a6
    b8 = a1**2 * a6 + 4 * a2 * a6 - a1 * a3 * a4 + a2 * a3**2 - a4**2
    Di = -(b2**2) * b8 - 8 * b4**3 - 27 * b6**2 + 9 * b2 * b4 * b6
    return Di % N == 0

assert is_singular(), "Curve is not singular"

Goal: Solve DLP over Integer Modulo N over Singular Curve

We are given points P=(Px,Py) and Q=(Qx,Qy). Q=dP where d is secret. Our goal is to recover d which contains the flag.

Denote EC(k) be the curve defined over modulo ring k, and ord(EC(k)) be the order of EC(k). If we factor N, we can solve each DLP over EC(p) and EC(q) and combine them using chinese remainder theorem.

Factorization of N = pq

We do not know the values of p and q yet. However, we know that elliptic curve operation is not well defined in composite ring(N is composite). Also, if singular curve is the form of cusp(y2=x3) over prime r, its order is r. ord(EC(N))=ord(EC(p))×ord(EC(q)).

Assuming that EC(p) is a cusp(ord(EC(p))=p), N will be the multiple of p=ord(EC(p)). If we calculate scalar multiplication NP over EC(N), operation will be not well defined. Let t be the intermediate value which breaks down the operation, because t's inverse does not exist over composite N. This means gcd(t,N) will give a nontrivial factor, which results in factorization, obtaining p.

def factor():
    try:
        ec.scalar(N, P)
    except Exception as e:
        t, _ = list(
            map(
                int,
                str(e).lstrip("inverse of Mod(").rstrip(") does not exist").split(", "),
            )
        )
    p = gcd(t, N)
    q = N // p
    return p, q

Solving DLP over EC(p)

Lets classify whether EC(p) is a cusp(form y2=x3) or node(form y2=x3+αx2). To do this, we need to find a singular point. Compute partial derivatives of EC(p) and find values where they vanish and also on a curve.

def calc_singular_point(f):
    FF = f.base_ring()
    p = FF.order()

    dfdx = lambda x, y: FF(a1 * y - 3 * x**2 - 2 * a2 * x - a4)
    dfdy = lambda x, y: FF(2 * y + a1 * x + a3)

    A = FF(6)
    B = FF(4 * a2 + a1**2)
    C = FF(2 * a4 + a1 * a3)
    roots = solve_quadratic(A, B, C)

    for xp in roots:
        yp = FF((-a1 * xp - a3) * pow(2, -1, p))
        assert dfdx(xp, yp) == 0 and dfdy(xp, yp) == 0
        if f.subs(x=xp, y=yp) == 0:
            return xp, yp

After that, we shift the curve to set the singular point as origin (0,0).

    f = f.subs(x=x + xp, y=y + yp)
    assert f.subs(x=0, y=0) == 0
    xy_coeff = f.coefficient(x * y)
    f = f.subs(y=y + xy_coeff * twoinv * x)
    assert f == x ** 3 - y ** 2, "Given curve is not a cusp"

We confirmed EC(p) is a cusp. We can solve DLP easily when a singular curve is a cusp form. EC(p) has group isomorphism with GF(p), and can be regarded as an additive group (Theorem 2.30 [^book]).

φ:EC(p)GF(p),(x,y)xy,inf

We use this isomorphism \varphi to map points from EC(p) to elements of the group (GF(p), +). We first also shift the points because curve has shifted and mapped to an additive group. Therefore ord(EC(p)) = p.

    # shift points
    Pxp = Px - xp
    Pyp = Py - yp - xy_coeff * twoinv * Pxp
    assert f.subs(x=Pxp, y=Pyp) == 0

    Qxp = Qx - xp
    Qyp = Qy - yp - xy_coeff * twoinv * Qxp
    assert f.subs(x=Qxp, y=Qyp) == 0
    
    # map to additive group over FF
    Q_ = FF(FF(Qxp) // FF(Qyp)) 
    P_ = FF(FF(Pxp) // FF(Pyp))

Solving DLP over additive group is easy.

    dp = Q_ // P_

We recovered d_{p}, which is the result of DLP over EC(p) between P and Q. Every implementation for this step is done at method solve_dlp_over_p().

Solving DLP over EC(q)

Lets classify whether EC(q) is a cusp(form y^{2} = x^{3}) or node(form y^{2} = x^{3} + \alpha x^{2}). Again, we need to find a singular point. Compute partial derivatives of EC(p) and find values where they vanish, and also on a curve. We shift the curve to set the singular point as origin (0, 0).

    xq, yq = calc_singular_point(f)

    # change of variables to make (0, 0) as singular point
    f = f.subs(x=x + xq, y=y + yq)
    assert f.subs(x=0, y=0) == 0
    xy_coeff = f.coefficient(x * y)
    f = f.subs(y=y + xy_coeff * twoinv * x)
    
    assert alpha != 0
    assert f == x**3 + alpha * x**2 - y**2

We confirmed EC(q) is a node of the form y^{2} = x^{2} (x + \alpha). We have an isomorphism(Theorem 2.31 [^book]):

\phi: (x, y) \rightarrow \frac{y + \alpha x}{y - \alpha x}

\alpha is not a quadratic residue in this challenge, so \phi gives an isomorphism:

EC(q) \simeq S := { u + \alpha v | u, v \in GF(q), u^{2} - \alpha v^{2} = 1 }

where the righthand side is a group under multiplication. This is called nonsplit multiplicative reduction. S is a set of points which field norm is 1. Let K/F be an extension field when F = GF(q). Norm map Norm_{K/F} is surjective; (Proof). By the proof, ord(S)(cardinality of kernel) is equal to q + 1. Confirmation:

    # order of Elliptic curve over GF(q) = q + 1
    oq = q + 1
    ec = EC(FF, (a1, a2, a3, a4, a6))
    assert ec.iszeropoint(P) and ec.iszeropoint(Q)
    assert ec.scalar(oq, P) == ec.O and ec.scalar(oq, Q) == ec.O

We know ord(EC(q)) = q + 1. Luckily, q + 1 is B-smooth, so we can apply Pohlig Hellman algorithm for solving the DLP.

    factors = [2, 2148001447, ...]
    assert reduce(mul, factors) == oq
    # order is B-smooth where B = 2 ** 33
    B = 2**33
    assert all(fac << B for fac in factors)

Pohlig Hellman algorithm only cares about input elements form a finite abelian group whose order is a smooth integer, which is our case. Sagemath has discrete_log method implemented, which takes elements and operations to make every step of the algorithm well defined. Identity, inverse, addition must be defined over custom groups. Define class ECPoint which is a wrapper of a tuple, define operations, and plug in to discrete_log.

    # ECPoint class for discrete_log
    class ECPoint:
        def __init__(self, point):
            self.point = point

        def is_zero(self):
            return self.point == EC.O

        def __eq__(self, other):
            return self.point == other.point

        def __hash__(self):
            return hash(self.point)

    # factory method for discrete_log
    add = lambda x, y: ECPoint(ec.add(x.point, y.point))
    inv = lambda x: ECPoint(ec.negate(x.point))

    # wrapping points with ECPoint class
    identity = ECPoint(ec.O)
    P_, Q_ = ECPoint(P), ECPoint(Q)

    # discrete_log time
    dq = discrete_log(
        Q_, P_, ord=oq, operation="other", identity=identity, inverse=inv, op=add
    )

Recovering d_{q} takes about 10 minutes in my laptop, which is the result of DLP over EC(q) between P and Q. Every implementation for this step is done at method solve_dlp_over_q().

Solving DLP over EC(N)

We solved DLP over EC(p) and EC(q). Combine the results using the Chinese remainder theorem.

def solve_dlp_over_N():
    p, q = factor()
    dp = solve_dlp_over_p(p)
    dq = solve_dlp_over_q(q)
    return crt([dp, dq], [p, q + 1])

We have recovered d, which is the result of DLP over EC(N) between P and Q.

Flag

Recover flag based on d.

from Crypto.Util.number import long_to_bytes as l2b

flag = l2b(int(d))
flag = flag[: flag.index(b"}") + 1]

We get flag.

TSGCTF{@l1_y0u_n3Ed_IS_ReaDiNG_5ilvErman_ThE_@r1thmetic_of_e11iPtiC_cURVe5}

Problem src: problem.sage depending on elliptic_curve.py

Problem output: output.txt

Exploit driver code: solve.sage

References

[^book]: Elliptic Curves: Number Theory and Cryptography 2nd Edition

Original writeup (https://github.com/pcw109550/write-up/tree/master/2023/TSG/Delta-Force).