# 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 satisfied^{1}:

- $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⌗

*hyperhyper*, while I have no proofs. The questions are no means useful for solving the questions, but I think they are helpful in pairing-based cryptography. They are very likely used somewhere anyway.

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 ↩