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.

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 satisfied¹:

1. $u(x)$ is monic,
2. $f(x) \equiv [v(x)]^2\ \left(\text{mod}\ u\left(x\right)\right)$, and
3. $\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$?