Description of SmeaLog

SmeaLog was a challenge in the crypto category. The description given to the participants was straightforward: “Could you solve this discrete logarithm?”. Additionnaly, we are given two files: a Sage script SmeaLog.sage and an output generated with it output.txt.

First the SmeaLog.sage 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. Our goal is to retrieve $s$ from the data in output.txt, 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 assumed 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.

Crypto reminders

Since they are at the core of this challenge, here are reminders on elliptic curves. You can jump directly to the challenge solution if you already are familiar with them.

Elliptic curves basics

An elliptic curve is a mathematical object used extensively in modern cryptography. It is defined by an equation of the form $y^2 = x^3 + ax + b$ (for some fixed parameters $a$ and $b$), which means that every point $(x, y)$ that satisfies this equation lies on the curve. The most common representation of an elliptic curve looks like this:

But in cryptography, the coordinates $x$ and $y$ of the points are not real numbers but instead they are defined as integers modulo some big prime number (for example modulo $p =2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1$). Thus, the curve doesn’t look like the picture above anymore and the number of points on the curve is no longer infinite: there are at most $p^2$ points in total. The same elliptic curve for integers modulo 89 looks like this:

Now that we have defined a set of “special” points amongst the $p^2$ points (namely, those that satisfy the equation of the curve), we want to have a way to combine them: the point addition. A basic property of this addition is that adding a point $P$ to a point $Q$ gives a point $P+Q$ which is also on the curve. Thus, just adding the coordinate is not the right approach in general.

Because we are working with a finite number of points, there is another interesting property. Given a point $P$, we will denote $[n]P$ the point which is equal to $P + P + P + \dots$, with $n$ times the point $P$. But what happen if you compute $[n]P$ with an increasing value of $n$? Imagine a path starting at point $P$ and jumping from $P$ to $[2]P$, then to $[3]P$, etc. Since the number of points is finite, we are sure that it will come a time where the path will return to a point already visited: we have found a cycle! In other words, there exists $n_0$ and $n_1$ such that $[n_0]P = [n_1]P$. If you choose a point in this cycle and call it $G$, you can go over every point in the cycle just by adding $G$ the right number of times. And if you make as much jump as the length of the cycle, you will land on $G$ again. This structure is called a cyclic subgroup and the length of the cycle is called the order of this group.

In cryptographic applications using an elliptic curve the curve parameters $(a, b)$, a generator $G$ of a cyclic group and its order $q$ are given.

Challenge solution

An elliptic curve modulo a non prime integer

Usually, in cryptographic application, we use an ellpitic curve on which we can define a group. 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)$. 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.

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:

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())