TetCTF 2021: unevaluated

TetCTF is the first CTF I have played in 2021. I recalled from last year that they have cool challenges. This year, there are three crypto challenges. In particular, unevaluated is the hardest among them. Although I did not solve them, I dug into rabbit holes and had a lot of struggle, uh, fun.

Challenge Summary

There is a 128-bit prime $p$. Define $\cdot: \mathbb{Z}_{p^2}^2\times\mathbb{Z}_{p^2}^2\rightarrow\mathbb{Z}_{p^2}^2$ by

\[(x_1, y_1)\cdot(x_2, y_2) := \left(\left(x_1x_2-y_1y_2\right)\ \text{mod}\ p^2, \left(x_1y_2+y_1x_2\right)\ \text{mod}\ p^2\right),\]

where $(x_1, y_1), (x_2, y_2) \in \mathbb{Z}_{p^2}^2$. Also, define for $k\in\mathbb{N}$ and $G \in \mathbb{Z}_{p^2}^2$, $G^k = G \cdot G \cdot ... \cdot G$. Given that $G, H \in \mathbb{Z}_{p^2}^2$, the objective is to find $k\in\mathbb{N}\cap\left[0, 2^{256}\right)$ such that $H = G^k$.

Solution

Part I: What is the order composed of?

Since $p$ and $k$ are respectively 128 and 256 bits long, it is expected to recover two out of $k\ \text{mod}\ p$, $k\ \text{mod}\ q$ and $k\ \text{mod}\ r$ to compute $k$. It is interesting to see the order being a product of three primes $p, q, r$, with $q | (p-1)$ and $r | (p+1)$.

I have defined $\text{norm}: \mathbb{Z}_{p^2}^2 \rightarrow \mathbb{Z}_{p^2}$ by $\text{norm}(x, y) = (x^2 + y^2)\ \text{mod}\ p^2$ and experimented a bit and discovered some of the properties:

• The imaginary part of $G^{pr}$ is zero.
• $\text{norm}(G^{pq}) = 1$, and

If we are working on $\mathbb{Z}_p$ instead of $\mathbb{Z}_{p^2}^2$, then

• The imaginary part of $G^r$ is zero.
• $\text{norm}(G^q) = 1$, and

The following code snipped is used to verify the above properties.

# Under mod n
P = complex_pow(G, p*r, n)           # P.im == 0
dQ = norm(complex_pow(G, p*q, n), n) # dQ == 1

# Under mod p
P = complex_pow(G, r, p)             # P.im == 0
dQ = norm(complex_pow(G, q, p), p)   # dQ == 1

This make me think: If we consider a polar coordinate representation where $G = \rho e^{i\theta}$, with $\rho\in R$ and $\theta\in A$, then $R \cong \mathbb{Z}_{pq}$ and $A \cong \mathbb{Z}_{pr}$. Hence, we can imagine that the subgroup that $G$ generates is isomorphic to $\mathbb{Z}_{pq}\times\mathbb{Z}_{pr}$.

Part II: Stealing the ideas from an existing cryptosystem

Solving discrete log under modulo $n^2$ does not seem difficult. For example, we can see from Paillier cryptosystem that discrete logarithms under modulo $n^2$ can be computed easily. In this way, we can compute $x\ \text{mod}\ p$ with:

\[x \equiv \frac{\mathcal{L}(h^{p-1}\ \text{mod}\ p^2)}{\mathcal{L}(g^{p-1}\ \text{mod}\ p^2)}\ (\text{mod}\ p),\]

where $\mathcal{L}(x) = \frac{x-1}{p}$, like how a ciphertext is decrypted with the Paillier cryptosystem. Hence we have $x\ \text{mod}\ p$.

Part III: Solving 128-bit discrete logarithm

Let's try to work on $\mathbb{Z}_{p}^2$ instead of $\mathbb{Z}_{p^2}^2$. This reminded me the challenge galiver in ASIS CTF Finals 2020. I searched the discussion on CryptoHack's Discord server, and found...

Okay, works for 128-bit $p$ rather fast. So this must be discrete logarithm. Let's try it? Since the imaginary part for $G^r, H^r$ are zero, I tried discrete_log(H^r, G^r, q) on Sage. After five minutes, my PC crashed. I could not solve it during the CTF. After the game, rkm0959 publishes the writeup on the CTF and he used h.log(g) and have got it working. In his writeup, he uses a norm map which is isomorphic to the subgroup that $G^r$ generates.

p = 206109322179011817882783419945552366363
q = 103054661089505908941391709972776183181
r = 17175776848250984823565284995462697197
G = (20878314020629522511110696411629430299663617500650083274468525283663940214962,
     16739915489749335460111660035712237713219278122190661324570170645550234520364)
H = (11048898386036746197306883207419421777457078734258168057000593553461884996107,
     34230477038891719323025391618998268890391645779869016241994899690290519616973)

Zp = GF(p)

g = Zp(G[0]**2 + G[1]**2) # equivalently, g = Zp(complex_pow(G, r, p).re)
h = Zp(H[0]**2 + H[1]**2) # and           h = Zp(complex_pow(H, r, p).re)

assert g^q == 1
x_mod_q = h.log(g)
print('x % q =', x_mod_q) # 26176203815975575469683683780455489251

Part IV: Combining the building blocks

With Chinese remainder theorem, we are able to recover $x_0 := x\ \text{mod}\ pq$. It may not equal to $x$, but they are differ from a small multiple of $pq$. We can simply compute $x_0 + kpq$ for some small $k\in\mathbb{N}$ until $k$ is obtained. After that we have the flag - TetCTF{h0m0m0rph1sm_1s_0ur_fr13nd-mobi:*100*231199111007#}. This challenge makes me think more about discrete logarithm, and I am amazed by the capability of Sage. I am still wondering why discrete logarithm of a 128-bit prime can be computed in just a few minutes...