The objective of this fun challenge was solving the elliptic curve discrete logarithm problem using a twist attack on a Montgomery ladder.

To enable us to do so, the server essentially provides an oracle for the function $\mathbb E\to\mathbb E,\;P\mapsto [f]P$, where $f$ is the private key and $\mathbb E$ is an elliptic curve. According to the task description, the flag is $f$’s hexadecimal representation.

Let $p = 2^{160} + 7$, which is prime, and $A=40638$. The (Montgomery) curve in use is \[ \mathbb E\colon\quad y^2 = x^3 + Ax^2 + x \] over the finite field $\mathbb F_p=\mathbb Z/\langle p\rangle$. The organizers were kind enough to also supply the curve’s group order

which is unfortunately safe as it factors into $2^3$ and some large prime, effectively avoiding small-subgroup attacks. Since we can only supply an $x$ coordinate (as opposed to both $x$ and $y$ coordinates), invalid point attacks as described in the linked paper are also unapplicable.

But a given first coordinate $x\in\mathbb F_p$ corresponds to a valid point on $\mathbb E$ if and only if the equation $y^2=x^3+Ax^2+x$ has a solution $y$, that is, iff $x^3+Ax^2+x$ is a square in $\mathbb F_p$. What happens if this is not a square? According to the SafeCurves website, there is then another curve $\mathbb T$, called $\mathbb E$’s quadratic twist, that has a point represented by $x$. It can be described by the equation \[ \mathbb T\colon\; -y^2 = x^3 + Ax^2 + x \text, \] which shows why $x$ represents a point on $\mathbb T$: If the right-hand side was not a square, then multiplying it by $-1\in\mathbb F_p$ yields a square, hence the equation is solvable for $y$.

Now it gets exciting: The Montgomery ladder algorithm works for the quadratic twist $\mathbb T$ just as well as for $\mathbb E$!

Thus, if the order of $\mathbb T$ is smooth (i.e. has no large prime divisors), we can query the server for points of small order $q$ that are not on $\mathbb E$ but on $\mathbb T$ and thus obtain the value of the private key $f$ modulo $q$! Performing this attack for all prime divisors of $\lvert\mathbb T\rvert$, we can use the chinese remainder theorem to recover the full key (modulo $\lvert\mathbb T\rvert$, that is). This is exactly the idea of so-called twist attacks.

Hence, we are now particularly interested in the order of the twist $\mathbb T$. According to the paper linked above (Section 2.2; note that the formula in Section 4 seems to be wrong!), the equation \[ \lvert\mathbb E\rvert + \lvert\mathbb T\rvert = 2p + 2 \] holds, hence \[ n := 2p + 2 - \lvert\mathbb E\rvert = 1461501637330902918203685651179313124738649676760 \text. \] Quickly throwing this into GNU factor, we get

$ factor 1461501637330902918203685651179313124738649676760
1461501637330902918203685651179313124738649676760: 2 2 2 5 7 31 5857 3280967 68590573243 308648791439 413879086189

This looks really good! The largest factor of the twist’s order is only $413879086189<2^{39}$. This is a bit too much for all the possible exponents to be enumerable on a normal (that is, the author’s) computer, but if we use the baby-step-giant-step algorithm to find the logarithm in the small subgroups, the number of operations drops to about $\sqrt{2^{39}}\leq2^{20}$ — which is definitely feasible.

Alright, we’ll walk through the process that leads to a solution. Down the rabbit hole…

---

First of all, how do we check that (the point corresponding to) a coordinate $x\in\mathbb F_p$ is indeed on the quadratic twist $\mathbb T$? This is pretty straight-forward, as it is the case if and only if $x^3+Ax^2+x$ is a non-square in $\mathbb F_p$, which holds iff $(x^3+Ax^2+x)^{\frac{p-1}2}=-1\in\mathbb F_p$:

def on_twist(x):
    return pow(x ** 3 + A * x ** 2 + x, P >> 1, P) == -1

In the following, we shall denote by $\sim\subseteq \mathbb T^2$ the relation over $\mathbb T$ that satisfies $P\sim Q$ if and only if $P$ and $Q$ have the same $x$ coordinate. This is the case iff $P=Q$ or $P=-Q$.

---

As a short parenthesis, we should mention how the server, whose functions we will reuse in our exploit, represents points on the curve: It stores only the $x$ coordinate (hence identifying $P$ and $-P$ for all elements!), and does so embedding the $x$ coordinate into the projective line $\mathbb F_p\mathbb P^1$ for performance reasons. That is, each (equivalence class with respect to taking negatives of a) point is represented by a pair $(x,z)\in\mathbb F_p^2$ which actually denotes the two points that have $x/z\in\mathbb F_p$ as their first coordinate. The point at infinity (and thus, the curve group’s neutral element) is represented by the tuples $(x,0)$ for any $x\in\mathbb F_p\setminus\{0\}$.

For convenience, we implemented the utility function norm as follows:

def norm(a):
    x, z = a
    if z == 0:
        return (1, 0)
    return (x * mod_inv(z, P) % P, 1)

---

Now, how do we find coordinates such that the elements of $\mathbb T$ represented by them are of some given small order?

We shall denote by $q_1,\dots,q_8$ the prime factors of $n$ that are distinct from $2$, in ascending order; that is, $q_1=5$, $q_2=7$, and so on.

Note that, according to the structure theorem for finite abelian groups, the group $\mathbb T$ satisfies

where $G_8$ is some group of order $8$.

Let $q\in\{q_1,\dots,q_8\}$. We have a group homomorphism from $\mathbb T$ to the $q$-torsion subgroup $\mathbb T[q]$ of $\mathbb T$, that is, the subgroup of elements whose order divides $q$, given by \[ \varrho_q\colon\;\mathbb T\to\mathbb T[q],\;P\mapsto [n/q]P \text. \] If we choose some point on $\mathbb T$ at random — that is, choose some $x\in\mathbb F_p$ —, and apply the “reduction” $\varrho_q$ to it, the result is (by Lagrange’s theorem) either

• the identity, in which case $r$’s order was a multiple of $q$;
• or a point of order $q$!

The first case can happen if and only if the image of $r$ under the isomorphism stated above has $0$ in the component corresponding to $\mathbb q$; and since $r$ was chosen at random, the probability of this is at most $1/q$. Hence, by repeatedly chosing random group elements, raising them to the $n/q$th power ($\varrho_q$) and ensuring the result is not the neutral element (in which case we start over), we can very likely obtain a suitable element in a few tries. The code pasted below reuses the server’s power function.

def point_of_order(q):
    while True:
        x = random.randrange(P)
        if not on_twist(x):
            continue
        x, z = norm(server.power((x, 1), n // q))
        if z != 0: # non-neutral, yay!
            return x

---

At this point, we need to find the logarithms in the small subgroups of orders $q_1$ to $q_8$, therefore yielding $[f\bmod q_1]G_1$ to $[f\bmod q_8]G_8$ for attacker-chosen base points $G_i$ and relatively small $q_i$. We will use a slight variation of the baby-step-giant-step algorithm, which is well explained in other places, hence we will not present it in full. However, there’s a catch: The “usual” descriptions of the algorithm speak about group elements, but in our case, we only know the elements up to forming inverses! Hence, if the server provides us with $[f]G$’s first coordinate, this can actually denote two points which are each other’s inverses. Accordingly, if we manage to find the logarithm $\ell$, then the correct logarithm (that is, $f\bmod q$) may just as well be $q-\ell$ since $\forall i.\;[i]G\sim [-i]G$.

Similarly, the algorithm requires point addition, which is not well-defined in our setting since $P\sim Q$ does not imply $\forall R.\;P+R\sim Q+R$. But there is a solution: The addition has exactly two possible solutions (up to $\sim$) — Namely, if $P\sim [i]G$ and $Q\sim [j]G$ for some generator $G$ of the group $\mathbb T$, then $P+Q\sim [i+j]G$ or $P+Q\sim [i-j]G$. Hence, in the “search” phase of the algorithm, we can just compute both possible products and look them up in the pre-computed table. This may however yield false positives, which must be subsequently filtered out using “trial exponentiation”:

# returns two possible sums
def sums(x1, x2):
    B = P - 1
    if x1 == x2:
        r = norm(server.square((x1, 1)))
        return r[0] if r[1] else -1 # FIXME
    y1 = mod_sqrt((x1 ** 3 + A * x1 ** 2 + x1) * B % P, P)
    y2 = mod_sqrt((x2 ** 3 + A * x2 ** 2 + x2) * B % P, P)
    return [((B * (y2 - y1) ** 2 * euclid((x2 - x1) ** 2 % P, P)[1] - A - x1 - x2) % P + P) % P,
            ((B * (y2 + y1) ** 2 * euclid((x2 - x1) ** 2 % P, P)[1] - A - x1 - x2) % P + P) % P]

# yields all the multiples of G
def mults(g):
    last = None
    cur = (g, 1)
    yield (1, 0)
    while True:
        yield cur
        if last is None:
            last, cur = cur, server.square(cur)
        else:
            last, cur = cur, server.multiply((g, 1), cur, last)

# computes log_g(x) in Z/q
def find(g, x, q):
    m = 1 + isqrt(q)
    tab = {}
    pows = mults(g)
    for i in range(m):
        ig = norm(next(pows))
        if ig[1]:
            for xx in sums(ig[0], x):
                tab[xx] = i
        else:
            tab[x] = i

    pows = mults(norm(server.power((g, 1), m))[0])
    for i in range(0, q, m):
        ig = norm(next(pows))[0]
        if ig in tab:
            print('FOUND {} {}'.format(i, tab[ig]))
            for s1 in [-1, 1]:
                for s2 in [-1, 1]:
                    ret = ((s1 * tab[ig] + s2 * i) % q + q) % q
                    if norm(server.power((g, 1), ret)) != (x, 1):
                        # false positive
                        continue
                    return [ret, q - ret]

The end result is two possible logarithms of $f$ modulo $q$.

---

Since we obtain the logarithms only modulo $8$ distinct primes, there are only $2^8=256$ possible combinations of the logarithms, each of which yields a possible flag via the chinese remainder theorem. According to the task description, $f\bmod 8=0$, hence we can filter out a lot of them. The remaining possible flags after this step were

0x1d58b64a90a582ffea7e6311586ea694c71b42a0L
0x126105a5617a01f21fd8453f9b63e89f0fe39a28L
0x1638be62b0b9c522f9ab983500a4aa50L
0x18e366161d6e653bf8a7b92bbbdf59b2f99fd890L
0xdebb570ee42e42e2e019b59fed49bbd42683018L
0x1f7f1b65664b931d121dc0be2f3af7ea64fece58L
0x4ba2430c1f1829d47f86fa2246cf87980923780L
0x164d8a2539fa318c2c14950654d354a6a328d5c0L
0x34d0e5a5594eebdb3dd827972a735757e1bf5d0L
0x44d3fc4eba64d95621c5bc87ddab97b316cd70L
0x1c3074705cca9596fbcb768234daf6f377172410L
0x11d839f0c6c313c83a3deb20b84407c4d5ad6bb0L
0xb6b32c74535d6a4ad0df767a3aba2117a1f0c38L
0x6f5e292d1feb8e0bb374d82071c552faca3a228L
0xc0a9938126689edbcffc50adb0fca0178693dc8L
0x1d9dff2c8a6f38dca11bea6f0b76262e9affdc08L
0xa9d8361a609f60e28e4d7e2294a06fd75f2fc18L
0x79549039f2f6c29cb291b253e807d1faaedd3b8L
0x1928aef817381b18af4540896ee6d94ccd8471f8L
0x628332d32d2d84a370e2dfc8cbaba1ba8779208L
0x12841da1da22f063df9276c29e8176c4f5f7440L
0x12bba7ce95aaddf522154cd05a4e739971f61280L
0xe46579a2273c031303ea2eabdbf26b7a47aa870L
0x1a4f583780ee3b568ac9a03311162537ad1831c0L
0xf57a79251c2ba48c0238261540b6741f5e08948L
0x15da08030db71d9298f2f64d7486d855df9cc7b0L
0xae2575dde8b9c84ce4cd87bb77c1a6028651f38L
0x1c75bd5256944b73b268fddfe7e2768d4afbbd78L
0xf6d00d98c29e06f0bc302945fee72a2840e6838L
0x47550345cfe5f61411ce4c2a2e3b4acccd6bfc0L
0x1608b628d5070e5025390a26d34a10d9ef6d5e00L
0xaf7b0a518f2c2ab19ec58aec35f25c0b692fe28L
0x1c8b169990fb7199fe087e12f3c581edd9299c68L
0x119365f461cff08c3362604136bac3f821f1f3f0L

We tried the shortest one

0x1638be62b0b9c522f9ab983500a4aa50L

first (since it seemed unlikely that a value like this would occur by chance), and it was indeed the flag!