FCSC 2021 - SmeaLog

Posted on 03 May 2021, 18:00 in WriteUps

France CyberSecurity Challenge (FCSC) 2021

FCSC logo

The french national cybersecurity agency (ANSSI) has organised a CTF called the France CyberSecurity Challenge (FCSC for short) which goal is to select the team that will represent France during the European CyberSecurity Challenge on the 28th of September, 2021.

Description of SmeaLog

SmeaLog was a challenge in the crypto category. The description given to the participants was straightforward:

Elliptic curve over real numbers

This translates to "Could you solve this discrete logarithm?" and we are given two files: a Sage script SmeaLog.sage and an output generated with it output.txt.

Here is the content of SmeaLog.sage, that I will explain in summary just below:

`SmeaLog.sage` source code
import os
from hashlib import sha256
from Crypto.Cipher import AES
from secret import FLAG

def gen_curve(bits = 40, k = 4):
    assert bits*k >= 160, "Error: p**k must be at least 160 bits."
    p = random_prime(2 ** (bits + 1) - 1, lbound = 2 ** bits)
    R = Zmod(p**k)
    while True:
        a, b = R.random_element(), R.random_element()
        d = 4 * a ** 3 + 27 * b ** 2
        if d.is_unit():
            E  = EllipticCurve(R, [a, b])
            E_ = EllipticCurve(GF(p), [a, b])
            if E_.order().is_prime():
                return E

def gen_random_point(E):
    R = E.base_ring()
    a, b = E.a4(), E.a6()
    while True:
        x = R.random_element()
        t = x ** 3 + a * x + b
        if is_square(t):
            y = choice([-1, 1]) * sqrt(t)
            return E([x, y])

def gen_pair(E):
    N = E.base_ring().characteristic()
    s = ZZ.random_element(N)
    P = gen_random_point(E)
    return P, s

def encrypt(s):
    k = sha256(str(s).encode()).digest()
    iv = os.urandom(16)
    c = AES.new(k, AES.MODE_CBC, iv).encrypt(FLAG)
    return iv, c

E = gen_curve()
print(f"E = {E}")

P, s = gen_pair(E)
print(f"P   = {P}")
print(f"s*P = {s * P}")

iv, c = encrypt(s)
print(f"iv = {iv.hex()}")
print(f"c  = {c.hex()}")

First the script generates an EllipticCurve Sage object with three parameters \(a\), \(b\) and \(p\) where \(p\) is 40-bits long and both \(a\) and \(b\) are 160-bits long. This elliptic curve corresponds to all the points \(P = (x, y)\) such that \(x^3 + ax - b = y^3 \mod p^4\). The elliptic curve equation and the number \(p^4\) are printed. After that, a random point \(P\) and a random number \(s\) are generated. The scalar product \(P + \ldots + P\) with \(P\) appearing \(s\) times is computed (we will denote this scalar product by \([s]P\)). This leads to a new point that we will call \(H\). The coordinates of both points are printed but the number \(s\) remains secret and is used to derive a key that will encrypt the flag (in FLAG) using AES in CBC mode. The random initialisation vector iv as well as the resulting ciphertext c are printed.

As said before, the output of this script is given to us:

Content of `output.txt`
E = Elliptic Curve defined by y^2 = x^3 + 469245061185347057653091531882370383913875080615*x + 5114351683655764329253106245428582084587536640503 over Ring of integers modulo 6801613388087663669990064996614506238369534296081
P   = (4818298608029665051393880712825109209819975611403 : 3354976854279375487312341201850051023143236550702 : 1)
s*P = (6276672712837100206846077340854087747993984369352 : 5153262096245606021857753027994479500306746041453 : 1)
iv = 0564fc638153e8b1ef1b7b5f52c539cc
c  = a808e9122d2e0f398bec32a8864d7352fe0bd1d3d6690ba52d2c5bad92fecd2cebab044f312a951aa5bdc1a23f7a925a89c38901e4b546e3a065b6cb57975efb5e2c874273f050d214e178deef8dbc3a

Our goal is thus to retrieve \(s\), in order to decrypt the flag. This is in fact what is called the discrete logarithm of \(H = [s]P\) in base \(P\). This "elliptic curve discrete logarithm problem" can be used to build cryptographic primitives because it known to be computationnaly hard (meaning that it can't be solved in a reasonable amount of time) for well-chosen elliptic curves (and well-chosen point \(P\)). We will see here that the chosen parameters are not suitable for cryptographic use since we are able the compute the discrete logarithm in less than a minute on a general purpose laptop.

An elliptic curve modulo a non prime integer

Usually, in cryptographic application, we use an ellpitic curve on which we can define a group (as explained in the "crypto reminders" of a previous write-up). One basic property of a group is that it is closed under its operation (here, the sum). This means that for any two points \(P = (x_p, y_p)\) and \(Q = (x_q, y_q)\) on the curve, we want \(P + Q\) to also be a point on the curve.

Elliptic curve addition of two different points is defined geometrically and the computation of it involves an intermediate value \(\lambda = \frac{y_q - y_p}{x_q - x_p}\). But remember that we are working only with integers modulo \(n\), so dividing by \((x_q - x_p)\) actually means multiplying by the integer \(r\) such that \(r(x_q - x_p) = 1 \mod n\). Such an integer \(r\) exists if and only if \(\gcd((x_q - x_p), n) = 1\). When it exists, we say that \(r = (x_q - x_p)^{-1} \mod n\). If the curve is defined modulo a prime number, \(r\) always exists. Here, since the integers are taken modulo \(p^4\), the addition of two points on the curve is not always defined.

After some research about this unusual construction, I found a question on StackExchange that is close to our problem: in this question, the author is wondering what would happen if an elliptic curve is not defined modulo a prime number \(p\) but instead modulo a number \(n = pq\) with \(p\) and \(q\) prime (and different). The answer is quite enlightning: such a curve is in fact isomorphic to the cartesian product of the curve modulo \(p\) and the curve modulo \(q\). In other words: any point on the curve modulo \(n\) can be seen as a pair of a point on the curve modulo \(p\) and a point on the curve modulo \(q\). The point addition is naturally extended, when it is defined (which is not only the case as seen before), as the point-wise addition of the pair of points. The single and massive difference between this setup and ours is that in ours \(n\) is the power of the same prime: \(n = p^4\).

A convenient isomorphism in our setup

Following the intuition of this question (and answer) found on StackExchange, I searched a convenient isomorphism. Often, to solve crypto challenges in CTF and even more so for asymmetric cryptography, you need to have a sufficient understanding of the concepts used, some intuition on where you need to focus your research and you also need... to find and understand the right paper that will give you the solution! There is no particular method to find such a paper, but having a clear idea on what you are looking for exactly and how to formulate it precisely is crucial.

For this challenge, I managed to find this article, written by Massimiliano Sala and Daniele Taufer. It was posted on a preprint server in late 2020, and to my knowledge, is not yet published in a peer-reviewed journal or conference. In this paper the authors explain, among other interesting things, that there is an isomorphism (a one-to-one mapping) that is very convenient to use: every point \(P = (x, y)\) on our curve modulo \(p^4\) can be written as a pair containing its canonical projection \(\pi(P)\) on the curve modulo \(p\) (the point \(\pi(P) = (x \mod p, y \mod p)\)) and an integer modulo \(p^3\) that we will call \(q_P\). We will denote this relation between this pair and the point \(P\): \(P \sim (\pi(P), q_P)\)1.

What is really interesting is that this isomorphism is behaving nicely with respect to point addition: given two points \(P\) and \(Q\), let \(R = P + Q\); then \(R \sim(\pi(P) + \pi(Q), q_P + q_Q)\).

Solving the discrete logarithm

Now that we have this isomorphism, we can easily retrieve at least part of the secret \(s\). Thanks to its property with respect to point addition, we can write the following: \(H (= [s]P) \sim ([s]\pi(P), sq_P)\). Thus, by computing \(q_H.q_P^{-1} \mod p^3\), we can get the value of \(s\) but only modulo \(p^3\) and we will call this value \(s_{\text{low}}\).

Let's call \(s_3\) the value such that \(s = s_{\text{low}} + p^3.s_3\). We know that \(H = [s]P\), thus thanks to our isomorphism we also have \(\pi(H) = [s]\pi(P)\). We also know that \(s - s_{\text{low}} = s_3p^3\), thus \(\pi(H) - [s_{\text{low}}]\pi(P) = [s_3p^3]\pi(P)\).

From here we will use \(q\), the order of the point \(\pi(P)\), that is to say the lowest non-zero integer such that \([q + 1]\pi(P) = \pi(P)\). If we call \(p_{\text{inv}}\) the inverse of \(p^3\) modulo \(q\), then: it exists \(k\), such that \([p_{\text{inv}}][s_3p^3]\pi(P) = [s_3(1 + kq)]\pi(P) = [s_3]\pi(P)\).

By calling \(H'\) this new point on the curve modulo \(p\), \(s_3\) is the solution of the discrete logarithm problem: \(H' = [p_{\text{inv}}](\pi(H) - [s_{\text{low}}]\pi(P)) = [s_3]\pi(P)\).

Fortunately for us, this ECDLP is on a curve much smaller (\(p\) is a \(40\)-bits integer) on which it is practically computable.

We finally obtain the secret \(s\) by computing \(s_{\text{low}} + p^3s_3\) and are able to decrypt the flag using it. Here is the whole script used:

Sage script to solve the challenge
from hashlib import sha256
from Crypto.Cipher import AES

# Intuition from: https://crypto.stackexchange.com/questions/72613/elliptic-curve-discrete-log-in-a-composite-ring
# Isomorphism from: https://arxiv.org/pdf/2010.15543.pdf

def general_sum(P, Q, a, b):
    """
    Formula for point addition with projective coordinates
    """
    X1 = P[0]
    X2 = Q[0]
    Y1 = P[1]
    Y2 = Q[1]
    Z1 = P[2]
    Z2 = Q[2]

    T1=Y1*Y2*(X1*Y2+X2*Y1)-a*X1*X2*(Y1*Z2+Y2*Z1)-a*(X1*Y2+X2*Y1)*(X1*Z2+X2*Z1)-3*b*(X1*Y2+X2*Y1)*Z1*Z2-3*b*(X1*Z2+X2*Z1)*(Y1*Z2+Y2*Z1)+a*a*(Y1*Z2+Y2*Z1)*Z1*Z2
    T2=Y1*Y1*Y2*Y2+ 3*a*X1*X1*X2*X2+ 9*b*X1*X2*(X1*Z2+X2*Z1)-a*a*X1*Z2*(X1*Z2+2*X2*Z1)-a*a*X2*Z1*(2*X1*Z2+X2*Z1)-3*a*b*Z1*Z2*(X1*Z2+X2*Z1)-(a*a*a+ 9*b*b)*Z1*Z1*Z2*Z2
    T3= 3*X1*X2*(X1*Y2+X2*Y1)+Y1*Y2*(Y1*Z2+Y2*Z1)+a*(X1*Y2+X2*Y1)*Z1*Z2+a*(X1*Z2+X2*Z1)*(Y1*Z2+Y2*Z1)+ 3*b*(Y1*Z2+Y2*Z1)*Z1*Z2
    try:
        z_inv = pow(T3, -1, p**4)
        return (T1*z_inv, T2*z_inv, T3*z_inv)
    except:
        y_inv = pow(T2, -1, p**4)
        return (T1*y_inv, T2*y_inv, T3*y_inv)


def isomorph(P, E, E_base, q, p):
    # Little trick to just use the general sum for the last addition (the one
    # who would fail)
    qPx = general_sum((q-1)*P, P, E.a4(), E.a6())[0]

    return E_base(P), (int(qPx)/p)%p**3

if __name__ == "__main__":

    a = 4692450611853470576530915318823703839138750803615
    b = 5114351683655764329253106245428582084587536640503
    p4 = 6801613388087663669990064996614506238369534296081
    p = pow(p4, 1/4)
    E = EllipticCurve(Zmod(p**4), [a,b])
    E_base = EllipticCurve(GF(p), [a, b])
    q = E_base.order()
    P   = E(4818298608029665051393880712825109209819975611403,
            3354976854279375487312341201850051023143236550702)
    H = E(6276672712837100206846077340854087747993984369352,
        5153262096245606021857753027994479500306746041453)

    c_hex = "a808e9122d2e0f398bec32a8864d7352fe0bd1d3d6690ba52d2c5bad92fecd2cebab044f312a951aa5bdc1a23f7a925a89c38901e4b546e3a065b6cb57975efb5e2c874273f050d214e178deef8dbc3a"
    iv_hex = "0564fc638153e8b1ef1b7b5f52c539cc"



    Hiso = isomorph(H, E, E_base, q, p)
    Piso = isomorph(P, E, E_base, q, p)

    qH = Hiso[1]
    qP = Piso[1]
    print("Compute low part...")
    # We known that qH = s*qP mod p**3
    s_low = qH*pow(int(qP), -1, p**3)

    print("Compute high part...")
    # To compute the last part of s, we use the discrete log on E_
    p3_inv = pow(int(p**3), -1, q)
    lastH = int(p3_inv)*(Hiso[0] - int(s_low)*Piso[0])
    s3 = discrete_log(lastH, Piso[0], Piso[0].order(),operation='+')

    s = int(s_low) + int(s3)*p**3

    # Now decrypt the flag
    k = sha256(str(s).encode()).digest()
    iv = bytes.fromhex(iv_hex)
    c = bytes.fromhex(c_hex)
    plaintext = AES.new(k,  AES.MODE_CBC, iv).decrypt(c)
    print(plaintext.decode())
  1. The concrete definition of \(q_P\) is voluntarily not specified here but can be found in the cited paper. For the advanced readers: \(q_P\) is the \(x\)-coordinate of the product of \(\pi(P)\)'s order by \(P\), normalised by its \(y\)-coordinate and canonically projected to \(Z/p^3Z\). This is correctly defined only in the projective representation of the curve.