A very long story. It started when Brian Gu told me about DARK back in 2021 @theoremoon wrote the challenge "Hell" for SECCON CTF Finals 2022. It involved some hyperelliptic curves and was quite interesting. Let's look at that challenge first.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
import os
flag = os.environ.get("FLAG", "neko{the_neko_must_fit_to_the_hyperelliptic}")
p = random_prime(2 ** 512)
xv = randint(0, p-1)
yv = int(flag.encode().hex(), 16)
assert yv < p
g = 2
PR.<x> = PolynomialRing(GF(p))
f = sum(randint(0, p-1)*x**i for i in range(2*g + 1 + 1))
F = f + (yv**2 - f.subs({x: xv}))
HC = HyperellipticCurve(F, 0)
J = HC.jacobian()(GF(p))
D = J(HC((xv, yv)))
print(f"p = {p}")
for i in range(2, 5):
k = i*(i+1)
print(k*D)
|
cs |
Ultimately, we are given $p$ and Jacobians of $6D, 12D, 20D$. Here, we need to find the coordinates of $D$.
To solve this, first we note that for Mumford representation $(u, v)$ we must have $v^2 \equiv f \pmod{u}$.
As this is genus 2, $\deg u$ will be $2$ and $\deg f$ will be $5$. This means that we can recover $f$ via CRT.
After recovering $f$, we can compute the Mumford representation of $2D = 20D - 12D - 6D$. Here, we note that the $u(x)$ value of the Mumford representation of $2D$ will simply be $(x - xv)^2$ due to the usual formula. This recovers $xv$ and so $yv$.
So while the challenge was fun, I thought that it didn't venture through the whole "recover $D$ from $2D$" part. Another thing was that at first, I didn't realize that $(x - xv)^2$ would be the representation of $2D$. This lead me to thinking about searching for methods to actually compute the order of the Jacobian. After some quick tries, I realized that for hyperelliptic curves of genus 2 and above, the computation of orders is quite a difficult task. You can take more looks into this in papers like https://eprint.iacr.org/2020/289.pdf.
So the whole dividing by 2 shouldn't be very trivial. Let's think about genus 2. A reduced divisor would be of the form of $[P] - [O]$ or $[P] + [Q] - 2[O]$. We would be given the divisor multiplied by 2. We see that the $[P] - [O]$ case is the easy case presented in SECCON. How about the latter? In this case, $2[P] + 2[Q] - 4[O]$ would be presented to us. This is clearly not reduced, so we need to reduce.
A good explainer is presented in "Pairings For Beginners" Section 3.2. You set up a polynomial $g$ such that $g$ meets $f$ at $P$ with multiplicity $2$ and $Q$ with multiplicity $2$. This amounts to 4 constraints, so $g$ should be degree 3. Now we see something like $$g^2 - f = C (x - p)^2 (x - q)^2 (x^2 + ax + b)$$ For sake of explaining let's just say that $x^2 + ax + b$ splits and we have $$g^2 - f = (x - p)^2 (x - q)^2 (x - r) (x - s)$$ This will mean that $$2[P] + 2[Q] + [R] + [S] - 6[O]$$ is a principal divisor, so in the Jacobian, we will have $$2[P] + 2[Q] - 4[O] = 2[O] - [R] - [S]$$ which is practically now reduced. This means that $x^2 + ax + b$ will be (up to sign) the $u(x)$ of the Mumford representation of $2[P] + 2[Q] - 4[O]$, i.e. the polynomial we are already given. So basically we would be solving for something like $$g^2 - f = C (x - p)^2 (x - q)^2 u(x)$$ which looks to be relatively doable with the whole resultants and whatnot. It was, and I'll explain the further details later.
The next question for me was in dividing-by-2 in genus 3, rather than solving for dividing-by-3 in genus 2.
You actually need to reduce two times here, so following the system we have something like $$g^2 - f = C_1(x-p)^2(x-q)^2(x-r)^2 T(x)$$ $$h^2 - f = C_2T(x) u(x)$$ so something like $$(g^2 - f) u(x) = C(h^2 - f) (x-p)^2(x-q)^2(x-r)^2$$ where $g$ is degree 5 and $h$ is degree $3$. This is quite a lot of variables, so even after optimizing as hard as I can, I couldn't get the algorithm to run in SageMath at all. In the end I gave up, and decided to ask to solve for $P$ when given $5[P] - 5[O]$.
This requires a single reduction - take a $g$ of degree 4 that meets $f$ at $P$ with multiplicity 5. Then $$g^2 - f = C(x-p)^5 u(x)$$ holds, so this is a relatively manageable system that can be solved in SageMath within time. Once again, I'll explain the details later.
Before we dive into the PBCTF challenge, let's look into the whole dividing-by-2 situation in genus 3 hyperelliptic curves.
At first I thought it would just be a cool challenge, but it turned out that it had some interesting background.
It turns out that the previously noted fact that hyperelliptic curve's order is quite hard to compute had made it a candidate for a hidden order group. Hidden order groups are used in various parts of cryptography - the most common one we all know is the RSA group $\mathbb{Z}_N^\star$. There are various assumptions, (see Alin Tomescu's blog post) and various cryptographic primitives that are based on those assumptions. Some examples are VDFs (see [BBF18]) and integer-based zero knowledge proofs (see DARK [BFS19]) and so on. One popular choice for such a group is obvious - the RSA group itself, sometimes reduced to something like $QR_N / \{\pm 1\}$. However, selecting $N$ requires either a trusted third party or ridiculously large $N$ (see Sander's paper) which adds concerns. The goal now is trustless hidden order groups - and this is where class groups of imaginary quadratic fields come in. Apparently simply choosing a prime $p$ is enough - and nobody will be able to compute the order. Many papers based on hidden order groups mention class groups.
Hyperelliptic curves of genus 3 and above are mentioned as candidates in Brent's paper. It was then considered by Dobson, Galbraith, and Smith - this paper does a lot of things, such as rethinking security parameters, lowering sizes of ideal class group elements. Another thing that this paper does is to speculate that hyperelliptic curves of genus 3 actually might be a good choice - for example, the paper suggests that it may offer shorter keylengths in practice. The paper was followed by a paper by Jonathan Lee, who discusses point counting algorithms on hyperelliptic curves. Further work was done by a paper by Thakur to discuss more details, such as types of curves to avoid.
At this point, dividing-by-2 in genus 3 curves sounded like it should be impossible. After all, the RSA equivalent of this is solving a quadratic equation modulo $N$, which is straight up just equivalent to factoring. Also, if dividing-by-2 is impossible, then by definition, Strong RSA Assumption will be broken. I believed that this would immediately hinder the usage of hyperelliptic curves as hidden order groups. I didn't know if dividing-by-2 was possible in class groups as well. It is possible, and it's even mentioned in the DARK paper, oops...
Anyways, that was why I was so focused on doing the dividing-by-2 in genus 3 curves - I thought it would have a serious implication.
Back to the PBCTF challenge. The challenge I wanted was recovering $P, Q$ from $2[P] + 2[Q] - 4[O]$ in a genus 2 curve, and $R$ from $5[R] - 5[O]$ in a genus 3 curve. Since "hell" also had a part to recover the hyperelliptic curve equation, I decided that I should add this as well. I also wanted to make recovering $p$ as a part of the challenge. To do so, I added a point thanking @theoremoon for the nice SECCON challenge. To make the hyperelliptic curve formula recovery a bit more challenging, I bounded the coefficients heavily and gave less equations - so that lattice reductions are required. In the end, the challenge I submitted for PBCTF looked like this. It had 4 solves.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
import os
flag = open("flag", "rb").read()
flag = flag.lstrip(b"pbctf{").rstrip(b"}")
assert len(flag) == 192
while True:
p = random_prime(1 << 513, lbound = 1 << 512)
coefs = [int.from_bytes(os.urandom(42), "big") for _ in range(8)]
PR.<x> = PolynomialRing(GF(p))
g1, g2 = 2, 3
f1 = sum(coefs[i] * (x ** i) for i in range(2 * g1 + 2))
f2 = sum(coefs[i] * (x ** i) for i in range(2 * g2 + 2))
flag1 = GF(p)(int.from_bytes(flag[:64], "big"))
flag2 = GF(p)(int.from_bytes(flag[64:128], "big"))
flag3 = GF(p)(int.from_bytes(flag[128:], "big"))
hint = GF(p)(int.from_bytes(b"Inspired by theoremoon's SECCON 2022 Finals Challenge - Hell. Thank you!", "big"))
pol1 = x * x - f1(flag1)
pol2 = x * x - f1(flag2)
pol3 = x * x - f2(flag3)
pol4 = x * x - f2(hint)
if len(pol1.roots()) * len(pol2.roots()) * len(pol3.roots()) * len(pol4.roots()) == 0:
continue
HC1 = HyperellipticCurve(f1, 0)
J1 = HC1.jacobian()(GF(p))
HC2 = HyperellipticCurve(f2, 0)
J2 = HC2.jacobian()(GF(p))
P1 = HC1((flag1, pol1.roots()[0][0]))
P2 = HC1((flag2, pol2.roots()[0][0]))
P3 = HC2((flag3, pol3.roots()[0][0]))
P4 = HC2((hint, pol4.roots()[0][0]))
print(2 * J1(P1) + 2 * J1(P2))
print(5 * J2(P3))
print(J2(P4))
break
|
cs |
First, the hint and the jacobian of $P_4$ immediately gives a small product of $p$ - it can be checked that the hint string converted to integers is just a little higher than $2^{512}$. By factoring that small product, you can recover $p$.
Now we move on to recovering the 8 coefficients. As in the solution of "hell", we know that $v^2 \equiv f \pmod{u}$. Since the degrees of $u$ in the three Jacobians are 2, 3, 1 respectively, this amounts to 6 linear equations on the coefficients of $f$. Therefore, the solutions will be of the form of $s + c_1 l_1 + c_2l_2$ where $c_1, c_2$ are constants and $l_1, l_2$ is in the kernel of the matrix. As the coefficients are less than $2^{336}$, a lattice reduction will find the coefficients. Notice that $336 \times 8$ is significantly less than $512 \times 6$.
Exploit up to here: https://github.com/rkm0959/Cryptography_Writeups/blob/main/2023/PBCTF/remake-solution/solve.sage.
We now move on to the real challenge - the first one, as mentioned is recovering $P, Q$ from $2[P] + 2[Q] - 4[O]$.
Also as mentioned before, this can be reduced to solving $$g^2 - f = C_1 (x - p)^2 (x - q)^2 u(x)$$ Let's solve for this. Set $g = A + Bx + Cx^2 + Dx^3$ to get $$(A + Bx + Cx^2 + Dx^3)^2 - f = C_1(x-p)^2(x-q)^2u(x)$$ and by comparing the leading coefficient, we see that $C_1 = D^2$ so $$(A + Bx + Cx^2 + Dx^3)^2 - f = D^2(x-p)^2(x-q)^2u(x)$$ Now, for the sake of lowering degrees (in terms of $A, B, C, D$), we change this to $$(AD^{-1} + BD^{-1} x + CD^{-1} x^2 + x^3)^2 - D^{-2} f = (x-p)^2(x-q)^2u(x)$$ and re-define the variables to get $$(A + Bx + Cx^2 + x^3)^2 - D f = (x-p)^2(x-q)^2 u(x)$$ Now we will perform long-division on the LHS by $u(x)$, and add the constrain that the remainder should be zero. This will be two polynomial constraints on $A, B, C, D$. We add the fact that the result will be of the form of $$(x^2 + ax + b)^2 = x^4 + 2ax^3 + (a^2 + 2b)x^2 + 2abx + b^2$$ Since the coefficients are polynomials of $A, B, C, D$, we add constraints that the coefficients are ones of the form shown in $(x^2 + ax + b)^2$. For example, if the division result if $x^4 + c_3x^3 + c_2x^2 + c_1x + c_0$, where $c_i$s are polynomials of $A, B, C, D$, then we could set $a = c_3 / 2$ and $b = (c_2 - a^2) / 2$ then constrain that $c_1 = 2ab$ and $c_0 = b^2$. This adds two more polynomial constraints to $A, B, C, D$. Since we have four constraints and four variables, resultants will be able to recover $A, B, C, D$ with some time.
Exploit: https://github.com/rkm0959/Cryptography_Writeups/blob/main/2023/PBCTF/remake-solution/solve_12.sage
The second challenge is recovering $R$ from $5[R] - 5[O]$. This is solving $$g^2 - f = C_1(x-r)^5 u(x)$$ Here, I actually generated the parameters so that $u$ would split into three linear factors. This made it easier to compute everything, or at least think about everything (maybe this trick works with extended fields too). For example, let's say that $t$ is a root of $u$. Then, $g$ here would actually have to pass through $(t, -v(t))$. This would make the reduction process send $5[R] - 5[O]$ to have $(t, v(t))$ in the reduced form. Therefore, we actually know 3 points that $g$ passes through, which means that we can interpolate them. Therefore, we know $g \pmod{u}$.
So let's write $g = b + C_2 u(x) (x + v)$. This makes us write $$(b + C_2u(x)(x+v))^2 - f = C_1(x - r)^5 u(x)$$ and from the leading coefficients, we know $C_2^2 = C_1$. Now we can write $$(C_2^{-1} b + u(x)(x + v))^2 - C_2^{-2} f = (x-r)^5 u(x)$$ and rewriting variables, we can just solve for $$(t b + u(x)(x+v))^2 - t^2 f = (x-r)^5 u(x)$$ so there are only two variables - $t$ and $v$. We proceed similarly - divide the LHS by $u(x)$. Here, the remainder should be $0$ already, as we set $b = g \pmod{u}$ as already known. The main part is to constrain so that the result of the division is of the form $(x-r)^5$. To do so, let the result be $x^5 + c_4x^4+ \cdots + c_0$, where $c_i$s are again polynomials of $t, v$. Then, we can set $r = -c_4/5$ and constrain $c_3 = 10r^2, c_2 = -10r^3, c_1 = 5r^4, c_0 = -r^5$. This makes it possible to solve for $t, v$.
Exploit: https://github.com/rkm0959/Cryptography_Writeups/blob/main/2023/PBCTF/remake-solution/solve3.sage
After the CTF, @isenbaev told via twitter that divide-by-2 in genus 3 hyperelliptic curves. It happens that Magma is very strong, and can compute this kind of stuff very fast. At first, I was very surprised at the fact that divide-by-2 is possible. So what now? What does this mean??
I went over the VDF papers and DARK paper to look at exactly what assumptions they are working with.
VDFs require low order assumption or the adaptive root assumption. The latter is clearly hard, but low order assumption seemed interesing. Can we go further and consider multiplication/division by 3? I'm not sure, but it might be interesting to try. DARK paper mentions using the Strong RSA in Theorem 5. Another interesting thing was that there are papers that try to remove the Strong RSA assumption from arguments working over the integers. I still need to read that paper - it sounds very cool.
After reading more, I saw that the [DGS20] paper already had a defense in mind.
Basically, it considers the set $S$ where low-order assumption is broken, and just considers $\text{lcm}(S) G$. This is exactly the methods used to reduce the RSA group to $\mathbb{Z}_N^\star / \{\pm 1\}$ or something like that. This seems to be enough defense against low order assumption attacks.
What about the Strong RSA assumption side of things? I still thought that the whole dividing-by-2 things being possible was very bad, but as I mentioned before, I learned that even class groups have that property as well. Apparently it's fine.
I guess that not reading the detailed proof for DARK really hurt in the end. The proof is really hard, though...
Anyways, this was a really fun adventure, and I'm more motivated to study now. Thanks to everyone for the discussion.
'Cryptography' 카테고리의 다른 글
| ZK Applications (0) | 2023.03.03 |
|---|---|
| Polynomials and Elliptic Curves in ZK (0) | 2023.02.27 |
| Optimal Ate Pairing, BLS12-381, BN254 (0) | 2022.12.21 |
| Elliptic Curve Pairings (0) | 2022.11.25 |
| New Lookup Argument (0) | 2022.11.04 |
