Writeup by sin-infosec for SmeaLog

crypto elliptic curve

November 22, 2023

TLDR

Compute a discrete logarithm on an elliptic curve over $\mathbb{Z}/p^4 \mathbb{Z}$.

Recon

We have:

Our goal is to recover the integer $s$, which is called the discrete logarithm problem over elliptic curves. However, elliptic curves are usually defined over $\mathbb{F}_p$, so let’s see what new properties defining the curve over the ring of integers modulo $p^4$ brings.

As this challenge is really maths heavy, I won’t go into all details but these were the ressources I used through the challenge:

The first interesting property that we get out of these papers is that the order of such a curve is defined as:

$$ |E_{a,b}(\mathbb{Z}/p^4\mathbb{Z})| = p^3|E_{a,b}(\mathbb{F}_p)| $$

Let’s verify this statement:

p_4 = 6801613388087663669990064996614506238369534296081
p = 1614927334829

R = Zmod(p_4)
a = 4692450611853470576530915318823703839138750803615
b = 5114351683655764329253106245428582084587536640503
E  = EllipticCurve(R, [a, b])
E_ = EllipticCurve(GF(p), [a, b])

order_p = E_.order()
order = order_p * p^3

P = E(4818298608029665051393880712825109209819975611403, 3354976854279375487312341201850051023143236550702)
Q = E(6276672712837100206846077340854087747993984369352, 5153262096245606021857753027994479500306746041453)

print(P*order)

(0 : 1 : 0)

We get the point at infinity, so that looks good. However, the order could also be a divisor of $p^3|E_{a,b}(\mathbb{F}_p)| $

print(P*p^3)

(4007443145440943005333130212468548395141920291468 : 1028030021576040044647730940463623077982163798023 : 1)

So the order is not $p$ nor one of its power.

print(P*order_p)

raise ZeroDivisionError("Inverse of %s does not exist (characteristic = %s = %s*%s)" % (x1-x2, N, N1, N2))
ZeroDivisionError: Inverse of 760382977411273368060224531891894701675880351771 does not exist (characteristic = 6801613388087663669990064996614506238369534296081 = 1614927334829*4211714819235422071841592904178204789)

Ouch, it seems that multiplying by $|E_{a,b}(\mathbb{F}_p)| $ involves finding an inverse that does not exist. Indeed, addition on elliptic curves requires computing the inverse of elements of the field different from zero, and they always exist in the case of a field. However, when the curve is defined over $\mathbb{Z}/N\mathbb{Z}$ with N non-prime, then not every element has an inverse, and therefore the operation fails. This is actually used in the ECM factorization method as such a fail yields a non-trivial factor of $N$. You can read more about ECM here: https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization

Now to understand what follows I strongly encourage you to read the second ressource I linked about the anomalous curves and the Smart attack, as I will use the same properties of p-adics numbers and elliptic curves defined over the set of p-adic numbers noted $\mathbb{Q}_p$.

The key component here is that $\mathbb{Z}/p^n\mathbb{Z}$ can be described as a set of numbers with $n$ digits of precision in $\mathbb{Q}_p$.

Thanks to this, we can first verify the curve order:

E_Qp = E.change_ring(Qp(p))
P_Qp = E_Qp(P)
Q_Qp = E_Qp(Q)

print(P_Qp * order_p)
print(P_Qp * order)

(1202232461353*1614927334829^-2 + 12310237368*1614927334829^-1 + 629727838596 + O(1614927334829) : 1351514884646*1614927334829^-3 + 602722728334*1614927334829^-2 + 207712576140*1614927334829^-1 + O(1614927334829^0) : 1 + O(1614927334829^20))
(0 : 1 + O(1614927334829^20) : 0)

Which confirms our hypothesis on the curve order!

The curve defined in the source as E_ that will be noted $E_f$ here, is called the reduction curve of $E(\mathbb{Q}_p)$ over $\mathbb{F}_p$, and there is a group homorphism defined as:

$$\pi : E(\mathbb{Q}_p) \mapsto E_f(\mathbb{F}_p) $$ mapping a Point $P$ on $ E(\mathbb{Q}_p)$) to a point $P’$ on $E_f(\mathbb{F}_p)$. The paper explains how to build the isomorphism:

$$ \phi : ker(\pi) \mapsto p\mathbb{Z}_p $$

where $$ker(\pi) = {P \in E(\mathbb{Q}_p)|P’ = \mathcal{O} }$$ with $\mathcal{O}$ the point at infinity. $\phi$ maps coordinates $(x,y,z)$ to $\frac{-x}{y}$. The points P and Q from $E(\mathbb{Q}_p)$ are not in $ker(\pi)$, but the points $$|E_f(\mathbb{F}_p)| P \text{ and } E_f(\mathbb{F}_p)| Q$$ that we were trying to compute earlier belong to $ker(\pi)$!

And since $p\mathbb{Z}_p \approx \mathbb{F}_p $, and our p is only 40 bits, we can compute the discrete logarithm there! The other part of the discrete logarithm between $p^3P$ and $p^3Q$ can be computed with the usual technics in around 3min because the order of these points is $|E_f(\mathbb{F}_p)|$. Then using the chinese remainder theorem, we can combine both discrete logarithm value and recover the secret $s$ to decrypt the flag!

Putting it all together in Sage, here is my solving script:

from hashlib import sha256
from Crypto.Cipher import AES

p_4 = 6801613388087663669990064996614506238369534296081
p = 1614927334829

R = Zmod(p_4)
a = 4692450611853470576530915318823703839138750803615
b = 5114351683655764329253106245428582084587536640503
E  = EllipticCurve(R, [a, b])
E_ = EllipticCurve(GF(p), [a, b])

order_p = E_.order()
order = order_p * p^3

P = E(4818298608029665051393880712825109209819975611403, 3354976854279375487312341201850051023143236550702)
Q = E(6276672712837100206846077340854087747993984369352, 5153262096245606021857753027994479500306746041453)

E_Qp = E.change_ring(Qp(p))
P_Qp = E_Qp(P)
Q_Qp = E_Qp(Q)

nP_Qp = P_Qp * order_p
nQ_Qp = Q_Qp * order_p

secret_p3 =  ZZ((-nQ_Qp[0]/nQ_Qp[1]) / (-nP_Qp[0]/nP_Qp[1]))

p3P = P * p^3
p3Q = Q * p^3

secret_order_p = ZZ(discrete_log_lambda(p3Q, p3P, (0,order_p), '+'))

secret = int(crt([secret_p3,secret_order_p],[p^3,order_p]))

k = sha256(str(secret).encode()).digest()

iv = bytes.fromhex("0564fc638153e8b1ef1b7b5f52c539cc")
c  = bytes.fromhex("a808e9122d2e0f398bec32a8864d7352fe0bd1d3d6690ba52d2c5bad92fecd2cebab044f312a951aa5bdc1a23f7a925a89c38901e4b546e3a065b6cb57975efb5e2c874273f050d214e178deef8dbc3a")

flag = AES.new(k, AES.MODE_CBC, iv).decrypt(c)
print(flag)

$in