hiecss was a cryptography challenge for 172 points in this year's TUM CTF.
Our intern insisted on designing an elliptic-curve signature scheme. Needless to say, it went… quite wrong.
He is now back at brewing coffee all day long.
nc 130.211.200.153 25519
The service (see below for its source code) accepts a signed message. If the
signature is valid and the message equals "Give me the flag. This is an
order!" after stripping white space, the flag is printed.
The cryptosystem uses an elliptic curve in Weierstrass form over
the finite field \(\mathbb{F}_q\), that is the set of pairs
\((x,y) \in \mathbb{F}_q \times \mathbb{F}_q\) that fulfill the equation
\(y^2 = x^3 + ax + b \pmod{q}\) and the point at infinity.
In the following all calculations are done modulo \(q\) without explicit
notation. Let \(E(\mathbb{F}_q)\) denote the elliptic curve group with the
usual addition of points.
The curve parameters \(q, a\) and \(b\) are usually public, but in this
case unknown to us. This is no problem, because we can query the server as
often as we want and it returns different error messages.
Recovering the Curve Parameter
As first step we recover the modulus \(q\). If the received signature is
larger or equal to \(q\) the server responds with "bad signature".
Otherwise a different message is returned. With this oracle we easily determine
the modulus via binary search.
def recover_modulus(t):
def is_leq(m):
t.write("{:064x}".format(m).encode() + b'\n')
res = t.read_until(b'\n')
return res == b'\x1b[31mbad signature\x1b[0m\n'
l, u = 0, 2**256
m = 2**255
while l + 1 != u:
if is_leq(m): u = m
else: l = m
m = (u + l) // 2
return m
We get \(q =
\mathrm{0x247ce416cf31bae96a1c548ef57b012a645b8bff68d3979e26aa54fc49a2c297}\).
In the next step we send a signature of value \(0\).
We receive the following answer:
bad signature: (0x0, 0x21c2cba4d3f4b4b9daf34b7c78786f5106ec66960a1d378dcedd89d71ecbdf9b)
The values are \(x\) (the signature) and \(y\) respectively.
By the curve equation \(b = y^2\) since \(x\) is zero.
def recover_b(t, modulus):
s = '0'*64
t.write(s.encode() + b'\n')
res = t.read_until(b'\n')
y = int(res.split()[-1][:-1], 16)
b = pow(y, 2, modulus)
return b
It results in \(b =
\mathrm{0x12f55f6e7419e26d728c429a2b206a2645a7a56a31dbd5bfb66864425c8a2320}\).
With the knowledge of \(q\) and \(b\) we can query \(y\) for some
\(x \neq 0\) and solve the curve equation for \(a\):
\begin{equation*}
y^2 = x^3 + ax + b \Leftrightarrow (y^2 - x^3 - b) \cdot x^{-1} = a
\end{equation*}
The last parameter is \(a =
\mathrm{0xb3b04200486514cb8fdcf3037397558a8717c85acf19bac71ce72698a23f635}\).
Forging the Signature
The signature verification works as following.
Let \(m\) and \(s\) be the message and its signature respectively.
The server calculates \(h = \mathrm{SHA256}(m)\), \(S = (s, \sqrt{s^3 +
a \cdot s^2 + b})\) and \(S' = S^e\) with \(e = 65537\).
It accepts a signature as valid if \(S'_x = h\) holds over the integers
(not modulo \(q\)).
The SHA256 hash of the demanded message is larger than \(q\) so it cannot
be equal \(S'_x \in \{0, \dotsc, q-1\}\).
Fortunately the hashed message is not yet stripped. Therefore we can add some
white space until the hash is small enough. After appending four spaces, this
is the case.
We have to find an \(s\) such that \(e \cdot S\) equals
\(H = (h, \pm\sqrt{h^3 + a \cdot h + b})\).
The group order can be efficiently computed and is
\begin{equation*}
|E(\mathbb{F}_q)| =
\mathrm{0x247ce416cf31bae96a1c548ef57b012abf9047d8896d5976c9f357de611ea5a4}
\end{equation*}
In Sage the following command can be used for this purpose.
EllipticCurve(GF(q), [a, b]).cardinality()
With \(d = e^{-1} \pmod{|E(\mathbb{F}_q)|}\) we can compute
\(d \cdot H = d \cdot (e \cdot S) = (d \cdot e) \cdot S = S\) and use the
first component as signature.
After sending the line
"10feab68fea4ecbc95e2f7c67ebcf83e75fc0e0357006ca2429559f4aa83fce8Give me the flag. This is an order! "
we receive the flag: hxp{H1dd3n_Gr0uP_0rD3rz_4r3_5uPP0s3D_t0_B3_k3p7_h1DD3n!}.
Appendix
The given source code of hiecss:
#!/usr/bin/env python3
import gmpy2
from Crypto.Hash import SHA256
e = 65537
order = 'Give me the flag. This is an order!'
def sqrt(n, p):
if p % 4 != 3: raise NotImplementedError()
return pow(n, (p + 1) // 4, p) if pow(n, (p - 1) // 2, p) == 1 else None
# just elliptic-curve addition, nothing to see here
def add(q, a, b, P, Q):
if () in (P, Q):
return (P, Q)[P == ()]
(Px, Py), (Qx, Qy) = P, Q
try:
if P != Q: lam = (Qy - Py) * gmpy2.invert(Qx - Px, q) % q
else: lam = (3 * Px ** 2 + a) * gmpy2.invert(2 * Py, q) % q
except ZeroDivisionError:
return ()
Rx = (lam ** 2 - Px - Qx) % q
Ry = (lam * Px - lam * Rx - Py) % q
return int(Rx), int(Ry)
# just elliptic-curve scalar multiplication, nothing to see here
def mul(q, a, b, n, P):
R = ()
while n:
if n & 1: R = add(q, a, b, R, P)
P, n = add(q, a, b, P, P), n // 2
return R
def decode(bs):
if len(bs) < 0x40:
return None
s, m = int(bs[:0x40], 16), bs[0x40:]
if s >= q:
print('\x1b[31mbad signature\x1b[0m')
return None
S = s, sqrt(pow(s, 3, q) + a * s + b, q)
if S[1] is None:
print('\x1b[31mbad signature:\x1b[0m {:#x}'.format(S[0]))
return None
h = int(SHA256.new(m.encode()).hexdigest(), 16)
if mul(q, a, b, e, S)[0] == h:
return m
else:
print('\x1b[31mbad signature:\x1b[0m ({:#x}, {:#x})'.format(*S))
if __name__ == '__main__':
q, a, b = map(int, open('curve.txt').read().strip().split())
for _ in range(1337):
m = decode(input())
if m is not None and m.strip() == order:
print(open('flag.txt').read().strip())
break