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:
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
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
Notice that the server uses a non-conventional algorithm to sum two points, using only the
# 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[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
$ 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
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
Twist
In this situation, the server uses another method for addition and multiplication, and it do relies on both
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
with coordinate to the server - The output point
is not in but in - Solve ECDLP
in using Pohlig-Hellman because the order of 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
.