hxp CTF 2020: Hyper
I was teamed up to play hxp CTF as @blackb6a last week. The hxp team had come up with a collection of hard challenges. In particular, there are two series of crypto challenges with a total of five parts. I will be writing on the hyper challenge and some follow-up and unanswered questions regarding to hyperelliptic curves.
ⓘ 𝗢𝗳𝗳𝗶𝗰𝗶𝗮𝗹 𝘀𝗼𝘂𝗿𝗰𝗲𝘀 𝘀𝘁𝗮𝘁𝗲𝗱 𝘁𝗵𝗮𝘁 𝘁𝗵𝗶𝘀 𝗶𝘀 𝗺𝗶𝘀𝗹𝗲𝗮𝗱𝗶𝗻𝗴
Seriously. I knew nothing on hyperelliptic curves prior to the CTF. The writeup is solely based on what I learnt during the game, and may not be accurate. If you found a mistake, please do not hesitate to contact me. Many thanks! 😄
Challenge Summary⌗
In this series of challenge, the message Hello! The flag is: hxp{...}
is xorred with an bytestream generated by an PRNG. In particular, the only difference between hyper (crypto, 294 points) and hyperhyper (crypto, 714 points) is the message lengths, respectively 45 and 93.
Without doubt, the most crucial element for this challenge is the PRNG, which is based on Jacobian of hyperelliptic curves. In this challenge, the Jacobian $\mathcal{J}$ of a hyperelliptic curve $\mathcal{H}$ of genus 3 over $\mathbb{Z}_p$ is used. $\mathcal{H}$ is defined by:
\[\mathcal{H}: y^2 \equiv x^7 + x\ (\text{mod}\ p).\]
Three constant points $G_1, G_2, G_3$ from $\mathcal{J}$ are picked and three integers $k_1, k_2, k_3$ are picked randomly as the seed. Finally, define $H_n \in \mathcal{J}$ by $H_n := k_1^nG_1 + k_2^nG_2 + k_3^nG_3$ for $n\in\mathbb{N}$. If we write $H_n = \left(u_n\left(x\right), v_n\left(x\right)\right)$, where
\[\begin{cases} u_n(x) := u_{n0} + u_{n1} x + u_{n2} x^2 + u_{n3} x^3 \\ v_n(x) := v_{n0} + v_{n1} x + v_{n2} x^2 \end{cases},\]
then the random stream would be $(u_{10}, u_{11}, u_{12}, v_{10}, v_{11}, v_{12}, u_{20}, u_{21}, ...)$, where each of $u_{ij}$ and $v_{ij}$'s is of 8 bytes.
Solution⌗
Part I: Comparing hyper and hyperhyper⌗
One thing that made me very curious at first glance: We are given 24 bytes of the random bytestream from the known message in both hyper and hyperhyper, why is hyperhyper an independent question? If we are able to recover internal state for the PRNG, wouldn't it be evident to solve the both parts?
Of course, I would have not questions if I have understood the PRNG. Since the first 24 bytes are known, we have $u_1(x)$. For hyper, we gotta recover the following 21 bytes, which is enough by recovering $v_1(x)$. After all, the points are given in Mumford representation. With that said, if a point $P\left(u\left(x\right), v\left(x\right)\right)\in\mathcal{J}$, the below properties are satisfied1:
- $u(x)$ is monic,
- $f(x) \equiv [v(x)]^2\ \left(\text{mod}\ u\left(x\right)\right)$, and
- $\deg\left(v\left(x\right)\right) < \deg\left(u\left(x\right)\right) \leq 3$.
It is hinted from the second property that the objective is to find a modular square root for $f(x)$ under modulo $u(x)$.
Part II: Midnight thoughts⌗
It was midnight when I realize this and I could not immediately think of an appropriate approach. I was even once expanding everything:
Suppose that we have $u(x) := x^3 + rx^2 + sx + t$ and $v(x) := ax^2 + bx + c$. Then the following modular congruences hold:
\[\begin{cases} -r^5 + 4r^3s - 3r^2t - 3rs^2 + 2st - a^2r^2 + 2abr + a^2s - 2ac - b^2 \equiv 0 \\ -r^4s + 3r^2s^2 - 4rst - s^3 + r^3t + t^2 + 1 - a^2rs + 2abs + a^2t - 2bc \equiv 0 \\ -r^4t + 3r^2st - 2rt^2 - s^2t - a^2rt + 2abt - c^2 \equiv 0 \end{cases}(\text{mod}\ p).\]
I must be very sleepy back then.
Part III: Wake up, wake up!⌗
After [enter an arbitrary number] hours of sleep, I woke up and immediately recalled Tonelli-Shanks algorithm. Basically we are able to apply the algorithm to compute modular square root, even with modulo $u(x)$. Since $u(x)$ is a degree 3 polynomial over $\mathbb{Z}_p$, the order for $\mathcal{G} := \text{GF}(p)[x]/u(x)$ would be a factor of $p^3 - 1$. Knowing the order, we can apply Tonelli-Shanks to compute a modular square root for $f(x)$. After all, $v(x)$ would be one of them.
The rest is trivial after we have $v_1(x)$ computed. Xorring the output with the keystream, we have the message: Hello! The flag is: hxp{ez_P4rT_i5_ez__tL0Cm}
.
Part IV: Mysteries of hyperelliptic curves⌗
Let $\mathcal{J}$ be the Jacobian of a hyperelliptic curve of genus 3. Suppose that $\sigma$ is the order of $G_1, G_2, G_3\in\mathcal{J}$.
- Question 1. Is $a_1G_1 + a_2G_2 + a_3G_3$ also has an order $\sigma$ given that $gcd(a_i, \sigma)=1$?
- Question 2. Define $S := \{k_1G_1 + k_2G_2 + k_3G_3 \in \mathcal{J}: k_1, k_2, k_3\in\mathbb{Z}\}$. Is $\left|S\right| = \sigma^3$?
- Question 3. Let $(\mathbb{Z}_p^3, +)$ be a group and define $x = (x_1, x_2, x_3), y = (y_1, y_2, y_3) \in\mathbb{Z}_p^3$. Suppose $x+y = (x_1+y_1, x_2+y_2, x_3+y_3)$. Is $(\mathbb{Z}_p^3, +)$ isomorphic to $S$?
- Jasper Scholten, Frederik Vercauteren (2003). "An Introduction to Elliptic and Hyperelliptic Curve Cryptography and the NTRU Cryptosystem"
https://homes.esat.kuleuven.be/~fvercaut/papers/cc03.pdf ↩