rkm0959

https://www.youtube.com/watch?v=Gfa4BIMMXhk

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. 

https://hackmd.io/qS36EcIASx6Gt_2uNwlK4A

https://www.zksummit.com/

zkSummit11에 Speaker로 참가합니다! 

https://hackmd.io/qb-NrfZ7SgWMvPGNF4xPxw

https://twitter.com/rkm0959/status/1746723799012442565

https://twitter.com/benediamond/status/1746724679706956213

https://hackmd.io/gwQ-RYURT8G1MeE5g-sbPw

https://hackmd.io/b__SmbY8TESHKGOM4Hwo5Q

https://hackmd.io/1_LFw9IORhOsJsZLjNEkiA

https://hackmd.io/NmxP5CsPTAerr2E-oPFlkQ

https://hackmd.io/keVLzFSrQdmCcmUVh2l_BQ

https://hackmd.io/c2eTRG3PSLeverwHTMkNDQ

https://hackmd.io/WzCftDAjQ7u0mYTAEg49Bw

https://hackmd.io/k8_1AfQNTfy25N23QTmZ6g