Twist and shout

5 minutes to read

I’ll shout about my curve all day, it’s totally secure. You’ll have to pull the solution from my cold dead hands!
Challenge contributed by CryptoHack
Connect at archive.cryptohack.org 11718
Challenge files:
twist_and_shout.py
Dockerfile
twist_and_shout.xinetd

We are given a server that uses an elliptic curve to encrypt the flag.

Source code analysis

We have the curve parameters:

"""
Define the elliptic curve

E: y^2 = x^3 + a*x + b

With order

n = 340282366920938463465004184633952524077  
  = 2^128 - 1629577202184312621
"""
q = 2**128 - 159
a = 1
b = 1494

We are allowed to enter an $\mathrm{x}$ coordinate for a point in the elliptic curve. The server will use that $\mathrm{x}$ coordinate to multiply the flag times the point in the curve (that is, it encrypts the flag) and we are given the resulting $\mathrm{x}$ coordinate:

def gen_secret(secret):
    d = secret.lstrip("ECSC{").rstrip("}")
    return int.from_bytes(d.encode(), "big")


def shout(x, d):
    P = (x, 1)
    Q = xMUL(P, d)
    return Q[0] * pow(Q[1], -1, q) % q


def challenge():
    """
    My curve has prime order, so I'll let you
    send as many points as you like! You'll
    never recover my secret before your flight home!!
    """
    import os
    flag = os.environ.get("FLAG", "ECSC{fake_flag_for_testing}").strip()  
    d = gen_secret(flag)

    while True:
        x = int(input("x-coordinate: "))
        print(shout(x, d))

Therefore, what we have is that, given a point $P$, the server computes $Q = d \cdot P$. Our objective is to find $d$, and thus we need to solve the elliptic curve discrete logarithm problem (ECDLP), which is hard as the order of the curve is a prime number.

Notice that the server uses a non-conventional algorithm to sum two points, using only the $\mathrm{x}$ coordinates of the points:

# Curve addition law using only x-coordinates, coded from
# https://www.hyperelliptic.org/EFD/g1p/data/shortw/xz/ladder/ladd-2002-it
def xDBLADD(P, Q, PQ):
    (X1, Z1), (X2, Z2), (X3, Z3) = PQ, P, Q
    X4 = (X2**2 - a * Z2**2) ** 2 - 8 * b * X2 * Z2**3
    Z4 = 4 * (X2 * Z2 * (X2**2 + a * Z2**2) + b * Z2**4)
    X5 = Z1 * ((X2 * X3 - a * Z2 * Z3) ** 2 - 4 * b * Z2 * Z3 * (X2 * Z3 + X3 * Z2))  
    Z5 = X1 * (X2 * Z3 - X3 * Z2) ** 2
    X4, Z4, X5, Z5 = (c % q for c in (X4, Z4, X5, Z5))
    return (X4, Z4), (X5, Z5)

The scalar multiplication algorithm is more common, using Montgomery Ladder:

# Montgomery Ladder for scalar multiplication
def xMUL(P, k):
    Q, R = (1, 0), P
    for i in reversed(range(k.bit_length() + 1)):  
        if k >> i & 1:
            R, Q = Q, R
        Q, R = xDBLADD(Q, R, P)
        if k >> i & 1:
            R, Q = Q, R
    return Q

Even if this is strange, the server is just computing $Q = d \cdot P$, and the returning value is $Q_\mathrm{x}$ (which is exactly Q[0] * pow(Q[1], -1, q) % q):

def shout(x, d):
    P = (x, 1)
    Q = xMUL(P, d)
    return Q[0] * pow(Q[1], -1, q) % q

The security flaw

The vulnerability is that the server does not check if there is a point in the curve that has the given $\mathrm{x}$ coordinate. We can try locally:

$ python3 twist_and_shout.py
x-coordinate: 1
273502621369416944597939413671202860337

And in SageMath:

$ sage -q
sage: q = 2 ** 128 - 159
....: a = 1
....: b = 1494
sage: E = EllipticCurve(GF(q), [a, b])
sage: E.lift_x(1)
...
ValueError: No point with x-coordinate 1 on Elliptic Curve defined by y^2 = x^3 + x + 1494 over Finite Field of size 340282366920938463463374607431768211297

As can be seen, there is no such point with $\mathrm{x}$ coordinate equal to $1$, but the Python script did show a result. Let’s see if such point exists in the curve:

sage: E.lift_x(273502621369416944597939413671202860337)
...
ValueError: No point with x-coordinate 273502621369416944597939413671202860337 on Elliptic Curve defined by y^2 = x^3 + x + 1494 over Finite Field of size 340282366920938463463374607431768211297

Not found either…

Invalid curve attack

With this setup, that the server does not check the existence of the point but still computes the multiplication, we can try to perform an invalid curve attack. The idea is to find a curve where it is easy to solve the ECDLP, take some point, send it to the server, bring back the result to the invalid curve and solve the ECDLP.

Usually, invalid curve attacks take advantage of the fact that addition and multiplication do not rely on the $b$ parameter of the curve in Weierstrass form ($y^2 = x^3 + a x + b$). So, just modifying that $b$ parameter it is possible to find another curve where the ECDLP is easy to solve. For instance, if the order of the curve is smooth (it has many short prime factors), the ECDLP is solvable using Pohlig-Hellman algorithm.

Twist

In this situation, the server uses another method for addition and multiplication, and it do relies on both $a$ and $b$. However, given that the challenge’s name talks about “twist”, we can think on the twist of an elliptic curve, which is a curve over a prime power finite field. So, if we have $E(\mathbb{F}_q)$, a (quadratic) twist of this curve would be $E(\mathbb{F}_{q^2})$.

And surprisingly, the previous points are found in the twisted curve:

sage: E2 = EllipticCurve(GF(q ** 2), [a, b])
sage: E2.lift_x(1)
(1 : 195291075018479657145988939598502694512*z2 + 75013447040380062933758487920479163178 : 1)
sage: E2.lift_x(273502621369416944597939413671202860337)
(273502621369416944597939413671202860337 : 137188032605880964854730507512363736488*z2 + 62763016274206965317903115936606943492 : 1)

Plus, the order of the curve is relatively smooth:

sage: factor(E2.order())
3 * 79 * 644899 * 1283505703 * 19385376821 * 89480282251 * 340282366920938463465004184633952524077

Actually, for Pohlig-Hellman we need the order of the point to be smooth, and it is:

sage: factor(E2.lift_x(1).order())
3 * 79 * 644899 * 1283505703 * 19385376821 * 89480282251

So, we have everything we need to solve the ECDLP:

Send point $P$ with coordinate $\mathrm{x} = 1$ to the server
The output point $Q = d \cdot P$ is not in $E(\mathbb{F}_q)$ but in $E(\mathbb{F}_{q^2})$
Solve ECDLP $Q = d \cdot P$ in $E(\mathbb{F}_{q^2})$ using Pohlig-Hellman because the order of $P$ is smooth

Flag

Now, we can write a Python script to solve the challenge:

$ python3 solve.py archive.cryptohack.org 11718
[+] Opening connection to archive.cryptohack.org on port 11718: Done  
[*] Closed connection to archive.cryptohack.org port 11718
[+] ECSC{7w1st_&&_sh0ut!}

The full script can be found in here: solve.py.