### Part 1

You have access to proving subtraction and multiplication over $\mathbb{F}_p$, and using that, you can prove elliptic curve addition over secp256k1. From this, by using the provable elliptic curve addition, your goal is to provide $(x, y)$ inside secp256k1 such that you can provide a provable addition chain to the elliptic curve point with $H(x, y)$ as the x-coordinate. In other words, you need to find the discrete logarithm between $(x, y)$ and the point with $H(x, y)$ as the x-coordinate. Of course, raw discrete logarithm is hard in secp256k1.

The idea is in the faulty emulated finite field in the subtraction/multiplication proof.

Note that we are checking $a - b + p - q \cdot p - r = 0$ with the equation (here $l$ is the bn254 prime) $$a - b + p - q \cdot p - r \equiv 0 \pmod{l \cdot 2^{256}}$$ This isn't actually sound, as $q \cdot p$ can go as high as $2^{512}$, larger than the modulo of the equation above. Indeed, we can try $$a - b + p - q \cdot p + l \cdot 2^{256} = r$$ so in a way, we can get $r$ to be $l \cdot 2^{256} \pmod{p}$ more than what it's supposed to be. Similar ideas work for multiplication.

This allows us to do weird things with the elliptic curve addition - so we can try an invalid curve attack. As secp256k1 is of the form $y^2 = x^3 + b$, we can try to move to the curve $y^2 = x^3$, where discrete logarithm is easy as a finite field operation as the curve is singular. Now the goal would be to find the starting point on secp256k1 such that after a single attack on subtraction/multiplication, the point lies on $y^2 = x^3$. This can be written as a system of polynomial equations with $x, y$, so the usual tricks with resultants or Groebner basis, or even manual reduction to a single variable equation works. I used manual reduction, and rbtree used Groebner basis.

One of the solvers told me that a bruteforce for a smooth curve order ($p_{max} \approx 10^{15}$) worked, albeit painful.

The idea was taken by this vulnerability report in ZKP systems. See #2.

### Part 2

You have to provide 165 points on Curve25519 in compressed form, and the hash of those points is the target point for subset sum. You then have to provide which of the 165 points will be the subset which sums to the target, while also providing the decompression proof that the compressed points decompress to the claimed result. Intuitively, $2^{165} \ll p$, so standard method doesn't work.

The main idea here is that $y$ can be larger than $p$. Therefore, if the $b$ is the bit and $y$ is the square root of $sum2$ that is less than $p$ with $b$ as its LSB, one can actually use $y' = 2p - y$ which also has $b$ as its LSB. However, as $y' \pmod{p} = p - y$, we see that $(x, y')$ and $(x, y)$ are different points. Using this, we can actually make three decisions for each point - not use it, use $y$, or use $y'$. Now $3^{165} \approx 2^{262} \gg p$.

Now this challenge is a puzzle: you have to find a set $S$ such that you can easily solve the modified subset sum $$\sum_S c_i s_i = T, \quad c_i \in \{-1,0,1\}$$ as the $3^n$ thing suggests, this can be solved via ternary systems, setting $s_i = 3^i$. See balanced ternary systems.

There is a catch - you need to prove that $(2p - y)^2 \equiv sum2 \pmod{p}$. To do so, you need to provide $0 \le q < 2^{256}$ such that $$(2p-y)^2 = q \cdot p + sum2$$ which means that $$2p-y < \sqrt{2^{256} \cdot p} \approx \sqrt{2} p$$ forcing $y > (2 - \sqrt{2})p \approx 0.6p$. Therefore, this technique doesn't work for all $y$.

This can be resolved as follows. Select the $i$th point as $3^i \cdot v_i \cdot G$ where $v_i$ is small positive integer, and not a multiple of $3$.

In this case, solving subset sum to $N$ with values $v_0, 3v_1, 9v_2, \cdots$ can be done recursively as follows

• if $N \equiv 0 \pmod{3}$, solve $N/3$ with $v_1, 3v_2, 9v_3, \cdots$
• if $N \equiv v_0 \pmod{3}$, solve $(N-v_0)/3$ with $v_1, 3v_2, 9v_3, \cdots$
• if $N \equiv -v_0 \pmod{3}$, solve $(N+v_0)/3$ with $v_1, 3v_2, 9v_3, \cdots$

as we can see, the value of $N$ decreases exponentially - so at some point, the value of $N$ will become small regardless - say, within $[-40, 40]$. The unfortunate part is that we don't know if it will become exactly zero. In practice, it turns out that $N$ does become zero.

Here, we show a much more intuitively sound way for a finish. Since $3^{163}$ is sufficiently large, what we can do is to do the $3^i \cdot v_i \cdot G$ for $0 \le i < 164$, but set the final 164th point to be a random elliptic curve point. This point will not be used for subset sum, but it will be used to try out various target points, as the target point is the hash of the entire set of 165 points. This way, we can try various target points, and clearly with a sufficient probability we will be able to find a target point in which $N$ does become exactly zero.

An alternate way by Mystiz is to have use $v_0, 3v_0, \cdots 3^{14} v_0, v_1, 3v_1, \cdots, 3^{14} v_1, \cdots v_{10}, \cdots, 3^{14} v_{10}$ and so on - then, one can try to solve for $\sum_{i=0}^{10} c_i v_i = T$ with small coefficients $c_i$ via LLL. Here, the catch is that $3^0 v_i, 3^1 v_i, \cdots, 3^{14} v_i$ must have working set of $y$-coordinates, but since there's only 15 points this actually works with high probability. Note that while we mentioned $y > 0.6p$, we can also handle $y < 0.4p$ using $p+y$ and $p-y$. Therefore, only 20% of the points fail to use this trick, and $0.8^{15}$ is definitely brute-forcable.

The idea was taken by this vulnerability report in ZKP systems. See #9.

#### 'CTF' 카테고리의 다른 글

Paradigm CTF 2023 2nd Place  (0) 2023.10.31 2023.08.25 2023.02.26 2023.02.22 2022.11.21

#### 'Blockchain Security' 카테고리의 다른 글

zkSummit11 @ Athens  (0) 2024.02.24 2023.10.30 2023.10.25 2023.10.17 2023.07.27

#### 'Blockchain Security' 카테고리의 다른 글

Curta / Plonky2x Audit Report  (0) 2024.02.27 2023.10.30 2023.10.25 2023.10.17 2023.07.27

#### 'Cryptography' 카테고리의 다른 글

1/12-1/14: MPC Fundamentals  (0) 2024.01.15 2024.01.07 2024.01.03 2024.01.03 2023.12.01

#### 'Cryptography' 카테고리의 다른 글

1/8-1/10: Fixing the Proof of [DP23]  (0) 2024.01.15 2024.01.07 2024.01.03 2024.01.03 2023.12.01

#### 'Cryptography' 카테고리의 다른 글

1/8-1/10: Fixing the Proof of [DP23]  (0) 2024.01.15 2024.01.15 2024.01.03 2024.01.03 2023.12.01

#### 'Cryptography' 카테고리의 다른 글

1/12-1/14: MPC Fundamentals  (0) 2024.01.15 2024.01.07 2024.01.03 2023.12.01 2023.12.01

#### 'Cryptography' 카테고리의 다른 글

1/4 - 1/6: FRI Soundness Proof & Proximity Testing with Logarithmic Randomness  (0) 2024.01.07 2024.01.03 2023.12.01 2023.12.01 2023.10.13