BkP CTF 2015: Crypto 600 "Wonderland" writeup

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

\[ \lvert\mathbb E\rvert = 1461501637330902918203684014253252914573215409208 \text, \]
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

\[ \mathbb T\cong G_8\times \mathbb Z_{q_1}\times\mathbb Z_{q_2}\times\dots\times \mathbb Z_{q_7}\times\mathbb Z_{q_8} \]

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


We tried the shortest one


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