rkm0959

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. 

We are given two polynomials $f, f_v$ such that $f \cdot f_v \equiv 1 \pmod{x^n - 1}$, but some $D$ of the coefficients are erased. We have to recover $f, f_v$ completely, in a relatively fast and reliable fashion. The erasure positions are also given by the server.

For the first task, $(n, D) = (2411, 83)$ and the erasure positions are completely random. 

For the second task, $(n, D) = (8501, 2125)$ and the erasure positions can be controlled by a user provided seed. 

Task 1

By setting a variable for each erased coefficient, we will have a system of $n$ quadratic equations over $2D$ variables in $\mathbb{F}_3$. However, the interesting part is that some of the quadratic equations are actually just linear. For example, if we denote $S_1$ and $S_2$ as the set of erased coefficient's degree in $f$ and $f_v$ respectively, we can see that the equation arising from computing the coefficient of $x^k$ in $f \cdot f_v \pmod{x^n - 1}$ will be simply linear if there are no $u \in S_1$ and $v \in S_2$ such that $u + v \equiv k \pmod{n}$. 

By collecting these equations and solving the linear system, we will be closer to finding the solutions for the $2D$ variables.

However, after implementing this you can see that there will be a nontrivial kernel, of size around 40 to 50. 

This can be resolved in two ways. 

• The author's intended solution is to modify the given system as a system of $n$ quadratic equations over $K$ variables, where $K$ is the size of the kernel. This can be done simply by expressing the solution set of the $2D$ variables as a single solution added with a vector in the span of the computed kernel basis. As $K$ is much smaller than $2D$, we can actually solve this quadratic equation system by linearization. In other words, we can regard all quadratic terms as a separate linear variable, and solve the linear system over $\mathcal{O}(K^2)$ variables. This fails if $K$ is large, but such probability is small enough so that you can just try repeatedly.  
• soon-haari's solution works by selecting variables so that fixing it will add as many linear equations as possible, then brute forcing them. Apparently, brute forcing around 3 to 7 variables makes it sufficient to solve everything with a linear system. This was considered by the author as well, but was considered to be of similar difficulty. Congratulations to soon-haari for the solve!

Task 2

From solving task 1, it should be clear that the goal should be to create as many linear equations as possible, and the best way to do it is by making the erased coefficients consecutive in their positions. Note that $D = n/4$. Now how do we do that?

Looking at the sample implementation, we can see that the random sampling works by 

• selecting a random number below $n - i$
• taking the value at that index
• swapping with the value at position $n - i - 1$ so it's not selected again

The first idea is that our consecutive selections should be between $3n/4$ and $n$ - this is because if we try to pick everything from the front, the whole swapping process with the elements from the back makes everything very complicated. By picking everything at the back, the swapping process doesn't matter. Our goal is that for each $0 \le i < 2D$, the $i$th randbelow call should return a value $x$ such that $$n - D \le x < n - (i \pmod{D})$$ To do this efficiently, we need to minimize the number of bits we constrain from the randbelow results.

This can be done by finding $t, e$ such that $$n - D \le t \cdot 2^e < (t + 1) \cdot 2^e \le n - (i \pmod{D})$$ and maximizing $e$. Now, it suffices to constrain that the randbelow result is equal to $t$ after being shifted right $e$ bits. 

With this constraint in mind, finding the random seed is a relatively standard & well-known part. Check 

• https://gist.github.com/maple3142/1e3e81411a791f85073c3d902b0f14ef    
• https://rbtree.blog/posts/2021-05-18-breaking-python-random-module/    

Finished 8th in ACSC Quals 2023. Solved all cryptography challenges and warmup rev. I had a alumni meetup with NEXON Youth Programming Challenge award winners, so I went home at like 9PM with a beer and sangria inside me.

(Here, sangria is not the recent folding scheme for PLONK from Geometry Research)

Kinda gave up on the whole ACSC thing until it was around midnight, then I saw that I could make it if I solve all cryptography challenges.

So I hurried to do so and finished around 5:30AM, then solved the warmup rev. Turns out that this was a good idea.

Merkle-Hellman

This is a knapsack-based cryptosystem, and we know practically everything here. Just decrypt it.

Check Number 63

We have $n$ alongside 63 pairs of $(e, k)$ where $$ed = k \phi(n) + 1$$ The goal is to factor $n$. First, the central idea is to note that $$k \phi(n) + 1 \equiv 0 \pmod{e}$$ so we recover $$\phi(n) \equiv - k^{-1} \pmod{e}$$ Combined with CRT, this gives us $$\phi(n) \pmod{ \prod e}$$ which is around $63 * 16 = 1008$ bits of information. Meanwhile, we since $$\phi(n) = n + 1 - (p + q)$$ we have a 1025 bit range for $\phi(n)$. We can easily brute-force all possible values of $\phi(n)$, then recover $p, q$ from $n, \phi(n)$. 

Dual Signature Algorithm

I overcomplicated this problem way too much - the easier solution is combining the two signature schemes via CRT then LLL.

I tried some straightforward lattices without the CRT idea, but it didn't give me the answer. Here's my solution.

Start with the equations $$ks_1 = z + r_1x + c_1q_1, \quad ks_2 = z + r_2x + c_2q_2$$ where $c_1, c_2$ each have absolute values of at most something like $2^{515}$. We'll cancel out the $k$ in the equations to get $$s_2(z + r_1x + c_1q_1) = s_1(z+ r_2x + c_2q_2)$$ or $$(s_2r_1 - s_1r_2)x = (s_1 - s_2)z + (s_1q_2) c_2 - (s_2q_1) c_1$$ This gives us a system - we want $$-2^{515} \le c_1, c_2 \le 2^{515}$$ as well as the linear equation $$(s_1q_2) c_2 \equiv (s_2q_1) c_1 + (s_2 - s_1)z \pmod{s_2r_1 - s_1r_2}$$ While there are some GCD issues like $\gcd(s_1q_2, s_2r_1 - s_1r_2) = 2 \neq 1$, in essence this is the same type of problem as $$S \le c_1 \le E, \quad L \le Ax + B \bmod{M} \le R$$ which is the exact task that the special case of my CVP repository solves. After getting $c_1, c_2$, the rest is easy linear equation. 

Corrupted

We are given a broken PEM file that looks like the following.

We need to recover the full PEM key. The solution is really hands-on, and it needs some grinding.

The PEM decoding algorithm is in pycryptodome - basically, it's just a DER decoding. So how does DER decoding work?

By following the DER implementation in pycryptodome alongside with some debugging, it's basically as follows.

• 1 byte is consumed as the octet. Not sure what this does. 
• Then, 1 byte is consumed as the length $l$. If $l \le 127$, then this is the final length.
• If $l \ge 128$, then the next $l \pmod{128}$ bytes in big endian represent the final length.
• The "final length" bytes worth of data, in big endian, is the pushed data. 

However, the very first "final length" is actually the full length, so this one should be skipped. 

Also, we quickly note that 

• By comparing lengths, it can be seen that this file is based on 2048 bit RSA. 
• In this case, the PEM file has a linebreak every 64 characters. Based on this, we can remove some "?" to linebreaks.
• The first step is to base64 decode the lines between the first and the last ones. By randomly selecting one of 64 choices for each "?" and decoding it multple times, we can figure out which bits in the decoded data are known, and which bits in the decoded data are the ones from the "?"s. This is useful when patching important "?"s so that the length informations makes sense.

The main part is to patch everything so that the length informations makes sense. Since the datasets are $n, e, d, p, q, d_p, d_q, u$ in order, just try every patch that makes sense and does not affect the bits that are actually known. Decoding an actual 2048 bit RSA PEM helps.

In the end, we'll have the full $n, e$ and some bits of $p, q, d_p, d_q, u$. However, $u$ is not needed here. 

The rest is relatively well-known - you set up an equation $$pq = n, \quad ed_p = k_p(p-1) + 1, \quad ed_q = k_q(q-1) + 1$$ and solve this equation modulo powers of 2 iteratively. To do so, you need to fix $k_p, k_q$ - it turns out that there are $\mathcal{O}(e)$ possible pairs of $(k_p, k_q)$, so you can try out all candidates. For example, see [HS09]. There is also my challenge "RSA Hex Permutation". 

SusCipher

This is a 3-round block cipher, and a hint is given - use differential cryptanalysis. 

Let's find some easy differentials. We collect the $((i \oplus j)[u], (S_i \oplus S_j)[v])$ and see how it behave - and it turns out that the bias is noticeable. We can keep track of an array $pos$, where $pos_i$ denotes the bit location where the original $i$th bit is the most correlated to it. 

In the current state, there are 3 S-box applications, so the bias will decrease over those 3 S-boxes. However, if we know a key chunk, for example, the first 6 bits, then the first key addition and the S-box application can be computed directly, so in reality we are only going through 2 S-boxes. Therefore, the correlation between the state just after the first S-box and the encrypted state will be much greater.

We can now brute force all 64 possibilities for all 8 key chunks. 20K random encryptions are enough to reliably find the key.