rkm0959

I briefly participated in DUCTF 2021, solving three crypto challenges and two simple rev challenges.

The reversing challenges were fun and hard enough for me, but they are labeled easy/medium so I will not explain them here.

Also, joseph (one of the problemsetters) has a very good writeup on https://jsur.in/posts/2021-09-26-ductf-2021-writeups, so check it out. 

yadlp

Step 1 

In challenges like these, figuring out the curve we are on is usually the first step. To do this, we let $$y = \frac{x +\sqrt{(D+1)x^2 - D}}{D}$$ and work out some algebra to end up with $$(x+y)^2 - (D+1)y^2 = 1$$ which is a Pell's equation. Now we change $(x, y)$ to $(x+y, y)$ and change $D$ to $D+1$ and consider $x^2 - Dy^2 = 1$. 

The solutions of Pell's equation satisfy some good properties, which come from the identity $$(a^2-Db^2)(c^2-Dd^2) = (ac+Dbd)^2 - D(ad+bc)^2$$ which shows that if $(a, b), (c, d)$ are solutions of $x^2-Dy^2=1$, then $(ac+Dbd, ad+bc)$ is also such a solution. This turns out to be the group addition as well. The homomorphism to a multiplicative group of $\mathbb{F}_{p^2} = \mathbb{F}_p[x] / (x^2 - D)$ written as $$(a, b) \rightarrow a + bx$$ is also notable. The results here so far can be studied from Pell's equation theory, so the point up to here were straightforward for me.

Step 2 

Now we have to look at the group structure. There are various methods to end up with the correct conclusion - that the group is a cyclic group of order $p+1$. You could just guess the group order, or give a solid mathematical proof. joseph gives a proof by using that the multiplicative group of $\mathbb{F}_{p^2}$ is cyclic and $\alpha^{p+1}=1$ for each $\alpha = a + bx$ for $(a, b)$ satisfying $a^2 - Db^2 = 1$. I think technically this proves that the group order is a divisor of $p+1$, but this is quite good as well. Here's another method that I used during my solve.

It suffices to show that there are exactly $p+1$ solutions for $a^2 - Db^2 \equiv 1 \pmod{p}$. This is equivalent to computing $$\sum_{b=0}^{p-1} 1 + \left( \frac{Db^2 + 1}{p} \right) = 2 + \sum_{b=1}^{p-1} 1 + \left( \frac{Db^2+1}{p} \right)$$ $$= 2 + \sum_{b=1}^{p-1} 1+ \left( \frac{D + b^2}{p} \right)$$ which means the value is the number of solutions for $$a^2 - b^2 \equiv D \pmod{p}, \quad b \not\equiv 0 \pmod{p}$$ plus $2$. Of course, the given equation is equivalent to $$(a-b)(a+b) \equiv D \pmod{p}$$ and there are $p-1$ solutions of the form $$a-b \equiv i \pmod{p}, \quad a+b \equiv Di^{-1} \pmod{p}$$ for each $i \in \{1, \cdots , p-1\}$. The key is that none of the solutions have $b \equiv 0 \pmod{p}$ because $D$ is, in this problem, not a quadratic residue. Therefore, the number of solutions is $2 + (p-1) = p+1$, as desired. This concludes the proof.

Note that if $D$ was a quadratic residue, there would be $p-1$ solutions.

This is really the turning point of the challenge - if $D$ was a quadratic residue, the group order would be $p-1$ and the fact that $p$ is a safe prime will help greatly to make the cipher safe. However, $D$ is not a quadratic residue, which makes the fact that $p$ is "safe" mean absolutely nothing. In fact, $p+1$ is very smooth. I thought that the whole $p$ is "safe" thing in the given script was a very funny joke :)

Step 3

Now we compute the actual discrete logarithm. There are many ways to compute this - you could write a custom Pohlig-Hellman algorithm to account for different addition and multiplication formula, which is possible but a hassle. An easier way is to define $\mathbb{F}_{p^2} = \mathbb{F}_p[x] / (x^2 - D)$ and work discrete logarithm over this field. Of course, to find a discrete logarithm, we need a generator $g$ for the field. Theoretically, we can just find random points until we find a generator. In my solution, I just tried the given points.

Step 4

Now that we know all the discrete logarithms, all we need to do is compute the flag. We see that $$\sum m_i \log_g(g_i) = \log_g(res) \pmod{p+1}$$ along with $0 \le m_i < 2^{64}$. This condition can be straightforwardly feeded into my CVP repository https://github.com/rkm0959/Inequality_Solving_with_CVP and we have the flag. This was a nice challenge combining a lot of fun math ideas :)

power sign

There are a lot of approaches possible, and a lot of solutions are on joseph's writeup linked above. Here, I'll just write my solution. 

Ultimately, we need $x, u$ such that $$x^2 \equiv H(msg, u) \pmod{N}$$ holds. Obviously there must be some issue with the whole $H$, so let's take a look in that whole thing. 

In $H$, we write $msg$ as a polynomial in $GF(r^n)$ and then computes the constant part of $$(msg + zu)^{r^m}$$ My immediate idea was to utilize frobenius endomorphism to simplify $$(msg + zu)^{r^m} \equiv msg^{r^m} + z^{r^m} u^{r^m} \equiv msg^{r^m} + z^{r^m} u \pmod{r}$$ which was linear in $u$. This gave us $$H(msg, u) = H(msg, 0) + u H(0, 1) \pmod{r}$$ and both $H(msg, 0)$ and $H(0, 1)$ can be computed directly from the given data.

Therefore, we can just select $u$ appropriately to make $H(msg, u) \equiv 1 \pmod{r}$ and send $x=1$ to get the flag.

l33tcrypt v2

Hour 1-2

CCE, a local CTF, was going on, but I was done with my part and had some time on my hands. 

That whole number field thing looked very scary, but the "error part" getrandbits and the "error part" from rounding $y$ made me believe that this is not really about number fields, but more about "approximate stuff" like lattices.

Also, I saw that after we find $p, q$, the remaining part can be copied from TetCTF 2021. (https://rkm0959.tistory.com/192)

After looking at basic conjugate things like $\overline{x} = 2p-x$ and $x \overline{x} = p^2 + q^2$ and doing some calculations on paper, I ended up with $$(a+r_1)^2 + 2p(a+r_1)(b+r_2) + (b+r_2)^2 (p^2+q^2) = y + r_3$$ where $0 \le r_1, r_2, r_3 < 1$. To make everything integer, multiplying $4^l$ gives $$(2^la + r_1)^2 + 2p(2^la+r_1)(2^lb+r_2) + (2^lb+r_2)^2 (p^2+q^2) + 4^ly + r_3$$ where $0 \le r_1, r_2 < 2^l$ and $0 \le r_3 < 4^l$ are integers. We have two equations, so in total, 6 error terms. 

We know $p^2+q^2$, so we only want the $p$ part. I wanted to plug in CVP repo, but it's not possible in this form. This is because the equations have parts like $r_1r_2p$, which is a large unknown value. This situation happened to me before - it was in AeroCTF horcrux (https://rkm0959.tistory.com/211) and I had talked about my solution with joseph before on discord. So I thought this might be the way. The idea is to cancel out $p$, making everything about the 6 error terms only. In the end, I would have a 6-variable polynomial to solve for small roots. 

In AeroCTF horcrux, the bounds were good enough that I could finish with CVP repo, not using the full power of the polynomials. To be more exact, I wouldn't need to use that $r_1r_2$ is $r_1$ multiplied by $r_2$ - just the fact that $0 \le r_1r_2 < 2^{2l}$. However, that was not true for this problem, as my CVP repo failed to give a correct solution. This meant that I actually needed the full power of 6 variable polynomials. I tried defund's repo, but it killed my computer. Another idea I had in mind was to use bounding to find one of $r_1, r_2$. However, not knowing $p$ precisely made this impossible. Then I went to work on writing up CCE and had dinner. 

Hour 3

I started with the bounding idea again - the part that kept bugging me was that $r_1$ really didn't matter. For example, if I had known $p$, I could find $r_2$ without the knowledge of $r_1$ or $r_3$ as the "impact" of $r_2$ is far greater than $r_1$ or $r_3$ in the whole equation.

To be more detailed, consider the equation $$(a+r_1)^2 + 2p(a+r_1)(b+r_2) + (b+r_2)^2 (p^2+q^2) = y + r_3$$ with $0 \le r_1, r_2, r_3 < 1$. When $r_1$ changes from $0$ to $1$, the LHS increases about 1337 * 2 bits. When $r_3$ changes from $0$ to $1$, the RHS increases about 1 bit. When $r_2$ changes from $0$ to $1$, the LHS increases about 1337 * 3 bits. This made me think about ignoring all $r_1, r_3$ parts as "noises", simplifying the equations at the cost of a looser bound and loss of information. 

Consider $0 \le r_1, r_2 < 2^l$ and $0 \le r_3 < 4^l$, with $$\left( a+ \frac{r_1}{2^l} \right)^2 + 2p \left(a + \frac{r_1}{2^l} \right) \left( b + \frac{r_2}{2^l} \right) + \left(b+\frac{r_2}{2^l} \right)^2 (p^2+q^2) = y + \frac{r_3}{2^{2l}}$$ we will divide this by $p^2+q^2$, and denote anything that is around 1 or smaller as $O(1)$. This gives $$\frac{1}{p^2+q^2} \left( a+ \frac{r_1}{2^l} \right)^2 + \frac{1}{p^2+q^2} 2p \left(a + \frac{r_1}{2^l} \right) \left( b + \frac{r_2}{2^l} \right) + \left(b+\frac{r_2}{2^l} \right)^2  = \frac{1}{p^2+q^2} y + \frac{1}{p^2+q^2} \cdot \frac{r_3}{2^{2l}}$$ First, $a^2$ is 1337 * 2 bits and so is $p^2 + q^2$, implying that the first part is $O(1)$. For the second part, if we fully expand the numerator, the part excluding $2pab$ are all around 1337 * 2 bits, implying that it is $O(1)$ after division by $p^2+q^2$.

We can also see that $(r_2/2^l)^2$ is $O(1)$. Finally, clearly $r_3/4^l$ is already $O(1)$. In conclusion, we have the stunning equation $$O(1) + \frac{2ab}{p^2+q^2} p + b^2 + \frac{2r_2b}{2^l} =  \frac{y}{p^2+q^2}$$ and in practice, the inequality $$\frac{2ab}{p^2+q^2} p + b^2 + \frac{2r_2b}{2^l} \le \frac{y}{p^2+q^2} \le 3 + \frac{2ab}{p^2+q^2} p + b^2 + \frac{2r_2b}{2^l}$$ worked well, which was verified with multiple testing with generated data. After clearing denominators, this was the perfect inequality to plug into CVP repo. Everything was known except $p$ and one error term for each equation, and everything was linear in terms of unknown values. I plugged this into the CVP repository, but there were multiple solutions. It took a few minutes to figure out that my candidates for $p$ were all consecutive integers, and I just had to take the next prime number to find the actual $p$, giving the flag.

This was a really really good challenge that taught me a lot. It had an interesting tradeoff of complexity and precision.

This writeup is long overdue, sorry about that. I participated in ACSC finals, and solved nearly all crypto, as there was a cryptography challenge that was really more about SQL Injection than cryptography. To be more detailed, the exact same cryptogrpahic vulnerability is used in one of the cryptohack challenges (and it has very similar setups as well) so the cryptographic side of the challenge is next to none. I had some fun learning some basic SQL Injection and got close, but ultimately failed to solve the challenge. I did solve all others, including one that was solved only by me. This writeup will be relatively short and concise, as I do not have a lot of time on my hands.

The solutions codes are on the usual github, https://github.com/rkm0959/Cryptography_Writeups/tree/main/2021/ACSC  

RSA Stream

We see that we are encrypting the given python file, so we know the plaintext and the ciphertext.

Since this is an XOR cipher, this implies that we know all the key streams used to encrypt the plaintext.

We note that the key streams are composed of $m^e \pmod{n}$ where $e$ are several primes. 

Of course, if we know $m^{e_1} \pmod{n}$ and $m^{e_2} \pmod{n}$ with $\gcd(e_1, e_2) = 1$, we can find $r_1, r_2$ such that $e_1r_1 + e_2r_2 = 1$.

Now we can finish calculating $m$ by simply using $$m \equiv m^{e_1 \cdot r_1} m^{e_2 \cdot r_2} \pmod{n}$$

CBCBC

We have a cipher that uses AES-CBC two times. From line 118 we see that padding oracle attacks still work.

If we write out the entire decryption process, we get that $$P_n = D_k(D_k(C_n) \oplus C_{n-1}) \oplus D_k(C_{n-1}) \oplus C_{n-2}$$ where $C_0 = IV_2$ and $C_{-1} = IV_1$. Note that $P_n$ can be easily controlled by $C_{n-2}$.

Therefore, the whole padding oracle attacks work, it's just that we need to change 2 blocks before the targeted block to perform the attack. The remaining parts are straightforward if you have solid understanding of padding oracle attack.

Swap on Curve

Basically we have to solve $$y^2 = x^3 + ax + b, \quad x^2 = y^3 + ay + b$$ which can be done by doing algebra to change it into a one variable polynomial equation, or using resultants to achieve the same goal. I used the latter option, also using what I learned from joseph (https://twitter.com/josep68_) in CryptoHack discord. Sometimes the resultant function on Sagemath doesn't work for some reason I don't fully understand, but you can get around this by using sylvester matrix trickery. 

Two Rabin

We have two separate problems, each of which needs to be solved to get the flag.

For the first problem, there is a known linear relation between the two messages since the pad is not random. Therefore, the two equations given can both be written as a polynomial equation of a single variable, which means that the system can be solved by polynomial GCD or basic algebra as both equations are only quadratic. I chose the latter option for some reason :P

For the second problem, the padding is small but they are random. Therefore, we can write the first message as $x$ and the second message as $x+y$ where $y$ is some small value. Since we have two quadratic equations on $x, y$, we can use resultants again to make a polynomial equation on $y$ only. Since $y$ is small, this polynomial equation can be solved via coppersmith's attack. After getting $y$, we now have two quadratic equations where $x$ is the only variable, which can be solved similarly as the first problem. 

Wonderful Hash

We require some sort of a hash collision. Since the hash is simply XOR of the hash of each blocks, this problem is equivalent to finding $x_1, x_2, \cdots,  x_k$ given sets $X_1, X_2, \cdots, X_k$ such that the following holds. $$x_i \in X_i, \quad \oplus_{i=1}^k x_i = 0$$ Of course, if $k=2$ this is the well-known birthday problem. 

While I'm not sure if this was required for this challenge, this problem has been studied before. It's in the 2002 CRYPTO paper "A Generalized Birthday Problem", and it has been explained by barkingdog in his blog post https://www.secmem.org/blog/2020/08/19/A-Generalized-Birthday-Problem/. Using this, we can solve the problem in $\mathcal{O}(2^{n/(1+\log_2 k)})$. The basic idea is to make a binary tree and solve the problem "partially" (make LSBs zero) as we go upwards. For more details, consult the blog post above or the 2002 paper. 

Share The Flag

This will be explained further later when I upload the CVP repository updates. 

Guest Writeup : https://blog.cryptohack.org/cryptoctf2021-hard

I played GoogleCTF Quals as a member of Super Guesser. We reached 9th place, which is good enough for a place in the Finals!

I solved all five cryptography problems, one (pythia) with barkingdog. While this was good work, I'm still sad that I couldn't solve the misc "cryptography" problem due to lack of time and creativity (and probably work ethic as well). Here's how we solved the cryptos.

NOTE : All challenges from GoogleCTF are open sourced, so check them here. https://github.com/google/google-ctf/tree/master/2021

exploit codes for all five challenges can be found on https://github.com/rkm0959/Cryptography_Writeups/tree/main/2021

tiramisu (28 solves)

Step 1 : Basic Analysis

We start by reading some golang codes. We see that the code roughly does the following 

• We receive the server's ECDSA public key and the encrypted flag message.
• The flag is encrypted with AES, using the key derived by HMAC with the ECDSA secret key.
• We can send our ECDSA public key, which would normally allow us to compute the shared secret.
• Using this shared secret, we send an authenticated encrypted message to the server.
• The server checks if we sent a valid encryption, and replys with another valid encryption with different IV.

Step 2 : Reducing the Problem and Finding Attack Vector

First, note that HMAC with a strong hash like sha256 is very hard if not impossible to break. 

Therefore, we should probably look deeper into the inner workings of the ECDSA implementation.

Especially, since the flag is encrypted with a HMAC-derived key, we must recover ECDSA secret key at some point.

This immediately implies that the following message is a very scorching hot take.

After realizing that people are actually solving this problem, we look more into the ECDSA. 

We see that there are actually two curves supported in this implementation, as shown in this code.

Now we see the vulnerability! The server checks our point lies on our curve, but then takes the coordinates modulo $P$, which is the modulo from the server's curve. Since there are no restrictions on the coordinate size, by Chinese Remainder Theorem, we have a complete control over the final coordinates taken modulo $P$. The server takes this faulty point and multiply it by $D$, the ECDSA secret key.

Step 3 : The Invalid Curve Attack

Turns out that the problem now reduces to a known attack called the invalid curve attack. 

Basically, when we work on the Weierstrass curve $y^2 = x^3 + ax + b$, the standard implementations for adding and doubling points never uses the value of $b$. It only uses the value of $a$ and the one or two points of the input. 

Therefore, if the server considers a point $(X, Y)$ and considers it as a point on $y^2 = x^3 + ax + b$ while multiplying a scalar to it, it actually performs valid scalar multiplication, although the computation is on the point $y^2 = x^3 + ax + b'$, where $$b' \equiv Y^2 - X^3 - aX \pmod{p}$$

Since we have full control on $(X, Y)$, the result after the coordinates are taken modulo $P$, we can actually select any curves of the form $y^2 = x^3 - 3x + b$. To exploit this even further, we can use the small subgroup attack. Consider we take find a curve $y^2 = x^3 - 3x + b$ which has an order which is a multiple of a small prime $m$. We can then take a point $(X, Y)$ on this curve with order $m$. If we send this point, the shared secret will be the first coordinate of a scalar multiple of $(X, Y)$, which there are only at most $m$ candidates. 

Since we can easily determine if our guess for a shared secret is valid by checking whether we receive a reply or not, we can test all $m$ candidates. However, the shared secret is just the first coordinate of the elliptic curve point. This means we will actually get two possible candidates for $D \pmod{m}$, so something like $D \equiv \pm l \pmod{m}$, since the additive inverse of a point has the same first coordinate. 

If we gather a lot of such information, we will be able to find a sufficiently small candidates for $D$ by Chinese Remainder Theorem.

To do so, we choose the "signs" in each modulo relation, compute $D$ by Chinese Remainder Theorem, and repeat.

Step 4. Implementation and Finish

• Choosing the Modulo $m$ - Prime : I chose the modulo $m$ to be prime, since they give a lot of information in a sense that $m$ will have GCD 1 with all the previous modulos I used. If you get $\pmod{m_1}$ and $\pmod{m_2}$ information, then you will get $\pmod{\text{lcm}(m_1, m_2)}$ information in total by Chinese Remainder Theorem. Therefore, having $\gcd(m_1, m_2) = 1$ usually helps.
• Choosing the Modulo $m$ - Size : This is quite important. If we take larger $m$, the number of modulo relations we need to take becomes smaller. This implies that we have an easier offline bruteforce of choosing signs, computing Chinese Remainder parts, and either ECDSA public key verification or AES decryption. However, choosing larger $m$ also implies that we have to search more elliptic curves to find a appropriate one, and we also need to interact with the server more to decide what $D \pmod{m}$ can be. If we take small $m$, everything becomes the opposite. I chose $m$ to be a prime between $300$ and $1000$. In my case, 25 relations were sufficient to find $2^{25}$ candidates for $D$, which is definitely a feasible number of candidates for final offline bruteforce.
• Multiprocessing : I used it to speedup both the server computation and the offline bruteforce. 
• Trick from rbtree : Instead of bruteforcing the signs, one can just solve for $D^2$ by CRT and take sqrt. In this case, you would need twice more information on $D \pmod{m}$, but you don't need the extra bruteforce. Great idea from rbtree, shared after contest!

pythia (65 solves)

This was a tricky problem for me, as I found the solution nearly immediately but struggled to write the exploit. 

Step 1 : Basic Analysis

• There are a total of $26^3$ possible passwords, each corresponding to a 16 bytes AES-GCM key.
• There is a password (key) we have to find. We must do it using around 48 queries of the following type.
• We can send some nonce/ciphertext/tag to be AES-GCM decrypted with the key without any associated data.
• The only response we get from the queries are whether or not the decryption process was successful.

Note that there are actually 150 queries and 3 passwords, but since each three problems are independent, we can just focus on one.

Step 2 : Reducing the Problem and Finding Attack Vector

In these types of problems, it's best to halve the number of candidates by each query.

To do so, we have to figure out how to build some nonce/ciphertext/tag that accepts all of the keys from a given set.

If we can do this, we can simply perform a "binary search" to get each password. This is a good time to look at how AES-GCM works. 

Step 3 : AES-GCM and Polynomial Fun

Here, we only consider the case where there are no associated data and we have 12 byte nonce. Everything is in $GF(2^{128})$.

Let $K$ be the key, $C = C_0 || C_1 || \cdots || C_{n-1}$ the ciphertext, and $IV$ the nonce. We now calculate $$H = AES_K(0^{128}), \quad J_0 = IV || 0^{31} || 1, \quad L = 0^{64} || len(C)$$

The tag $T$ is now calculated as $T = C_0 H^{n+1} + C_1 H^n + \cdots + L \cdot H + AES_K(J_0)$. 

Let's fix $IV= 0^{96}$. If we know $K$ and $n$, then we can calculate $H, J_0, L, AES_K(J_0)$. 

Now we want the polynomial coefficients $C_0, C_1, \cdots, C_{n-1}, T$ such that $$C_0 H^{n+1} + C_1 H^n + \cdots + L \cdot H + T = AES_K(J_0)$$ for a given set of $K$. To be exact, if we have $K_1, K_2, \cdots , K_m$ as a target set of keys, we compute the corresponding $H_1, H_2, \cdots , H_m$.

Then, we will try to find $n, C_0, C_1, \cdots , C_{n-1}, T$ such that $$C_0 H_t^{n+1} + C_1 H_t^n + \cdots + C_{n-1} H_t^2 + L H_t + T = AES_{K_t}(J_0)$$ for each $1 \le t \le m$. This is starting to look like Lagrange interpolation, with the caveat that $L$ is determined by $n$.

Take $n=m$. Let $f(x) = C_0 x^{m+1} + \cdots + C_{m-1} x^2 + L x + T$, which is a polynomial we want to find.

Our desired $f$ must satisfy $f(H_t) = AES_{K_t}(J_0)$ for each $1 \le t \le m$.

This $f$ can be found directly with Lagrange interpolation, and $f$ will have degree at most $m-1$. However, we have to set $f$'s coefficient of $x$ to be equal to $L$. This can be done by adding some scalar multiple of $g = (x-H_1)(x-H_2) \cdots (x-H_m)$.

However, if this $g$ has the coefficient of $x$ equal to $0$, we cannot control this coefficient by adding $g$.

In this case, we have to control it by multiplying some random degree 1 polynomial.

Finally, note that we can put any number of zero blocks at the front of the ciphertext to meet the length requirement if $\deg f < m+1$. 

There are a lot of methods to handle these sepcial cases, (i.e. $g$ can't control the coefficient) and the solution writeen by barkingdog is a bit different from what I wrote as well. He handled these cases by simply adding a few random points for the interpolation part of $f$.

This makes $g$ and it's coefficients much more random, making it unlikely for the coefficient to be zero.

I would like to note that is error is a very unlikely case, so not error-handling these special cases won't hurt. 

Step 4 : Implementation Details

• Fast Interpolation : If we try to find $C_i, T$ with a system of linear equations, the algorithm will take $\mathcal{O}(n^3)$ time which is quite slow. A relatively naive lagrange interpolation takes $\mathcal{O}(n^2)$ time. I suggest just using SageMath's lagrange polynomial function.
• Binary Search : If we just use standard binary search, we would have to compute $f$ for a set of $26^3/2$ keys. This is quite large for us to handle, and it may not even fit the payload size. Since we have much more than $\log(26^3) < 15$ queries per password, we can try to make our interpolation computation easier at the cost of using more queries. Here is one way to do so - we divide the set of $26^3$ keys into $40$ batches of size around $440$. We find which batch the key is in, and then use standard binary search. This fits in the query limit quite tightly. Note that if we found the batch that has the key, we do not need to check the other batches. 
• Cache : Note that the payload to test whether the key is in a certain set can be precomputed beforehand. Therefore, by using a cache or hashmap or whatever, we can save ourselves from repeating the same computation over and over again. This is especially useful when we are testing the $40$ batches - we will test the same batches for all three passwords, and computing the payload for all of them takes quite a while. By saving these payloads, we can save quite a lot of time on the exploit. 
• AES-GCM : endian stuff are very confusing to figure out, so you have to really concentrate

h1 (23 solves)

Step 1 : Basic Analysis

• We have some ECDSA looking stuff (it's actually just elliptic curve operations with Jacobians)
• We have some signatures, but we do not know any public key.
• Alice has sent two messages and signatures, but one of the messages contain the unknown flag.
• Bob has sent two messages and signatures, and we know both messages and their hashes.
• We also know the AES encrypted messages (one contains flag) with the shared secret as the key.
• The ECDSA nonce is yelling loudly at us to attack it which we obviously have to do.

Step 2 : Reducing the Problem and Finding Attack Vector

Obviously there is something going on with the custom RNG, and it becomes apparent if we read the code. 

We see that $n$ is $512$ bits, and our RNG call uses $b = 2^{32}$. Therefore, in the RNG call, the nonce can be written as $$\sum_{i=0}^{15} a \cdot byte_i \cdot 2^{32i}$$ since all values from $i \ge 16$ becomes $0$ modulo $2^{512}$. Note that $255a < 2^{32}$, so no modulo operations are needed.

Since each $byte_i$ has 8 bit of "entropy", in total the RNG has only 128 bits of "entropy", which is horrible.

This also means that each complete message/signature pair gives us around 384 bits of information on the secret key.

Since we have two such pairs for Bob's secret key $db$, we should be able to extract this value.

Clearly, computing the shared secret solves the problem, so we just need the public key of Alice. 

This is not hard, as given one complete message/signature you can recover the public key. This is even in wikipedia.

NOTE : There may be more than one public key possible, so try all of them to find the flag.

Therefore, clearly getting the secret key $db$ is the hardest part of the challenge, unless you are rkm0959 who doesn't know fundamentals.

Step 3 : Yet Another Inequality Solving with CVP!

Consider the message, signature pair $(r_1, s_1, z_1)$ and $(r_2, s_2, z_2)$, where $z$'s are the hashes. We know $$\left( \sum_{i=0}^{15} a \cdot byte_{1, i} \cdot 2^{32i} \right) \cdot s_1 \equiv z_1 + r_1 d \pmod{n}$$ $$\left( \sum_{i=0}^{15} a \cdot byte_{2, i} \cdot 2^{32i} \right) \cdot s_2 \equiv z_2 + r_2 d \pmod{n}$$ Since we can, we will remove $d$ from this system by writing $$\left( \sum_{i=0}^{15} a \cdot r_2 \cdot byte_{1, i} \cdot 2^{32i} \right) \cdot s_1 - \left( \sum_{i=0}^{15} a \cdot r_1 \cdot byte_{2, i} \cdot 2^{32i} \right) \cdot s_2 \equiv z_1r_2 - z_2r_1 \pmod{n}$$ Now we can consider $33$ variables $byte_{1, i}, byte_{2, i}, t$ for $0 \le i \le 15$, and use the $33$ inequalities $$\left( \sum_{i=0}^{15} a \cdot r_2 \cdot byte_{1, i} \cdot 2^{32i} \right) \cdot s_1 - \left( \sum_{i=0}^{15} a \cdot r_1 \cdot byte_{2, i} \cdot 2^{32i} \right) \cdot s_2 + tn =  z_1r_2 - z_2r_1$$ $$0 \le byte_{1, i}, byte_{2, i} \le 255$$ and plug this into Inequality Solving with CVP repository. This gives us $db$ and it solves the problem. 

tonality (30 solves)

Step 1 : Basic Analysis

• We get the ECDSA public key $P = dG$ and two messages.
• We can send a integer $t$, and we get the signature of first message signed with private key $td$.
• We now have to forge any signature of the second message with private key $d$. 

Step 2 : Finding Attack Vector, and "Wishful Thinking"

There's nothing really going on in this problem, so we just need to use the first query very well.

Denote the two messages $m_0, m_1$ and their hashes $z_0, z_1$. Denote the integer we will send as $t$. 

We will receive the signature $r_0, s_0$ such that the point $$(z_0 / s_0) G + (r_0 / s_0) tP$$ has the first coordinate equal to $r_0$. Here, the integer division is done modulo $n$, the order of elliptic curve.

We now have to forge a signature $r_1, s_1$ such that the point $$(z_1 / s_1) G + (r_1 / s_1)P$$ has the first coordinate equal to $r_1$. Here, the integer division is done modulo $n$, the order of elliptic curve. 

We wish to solve this in the easiest way possible - and this will happen when $$z_0/s_0 = z_1/s_1 , \quad (r_0 / s_0)t = (r_1/s_1), \quad r_0 = r_1$$ which can be rearranged as $$t = z_0 / z_1, \quad r_1 = r_0, \quad s_1 = z_1s_0/z_0$$ and submitting this to the server solves the problem.

story (32 solves)

Step 1 : Basic Analysis

• We have to send a sufficiently large UTF-8 string to the server.
• We receive the CRC16, CRC32, CRC64 values of the sent string back.
• We also receive the desired CRC16, CRC32, CRC64 values from the server.
• We have to make a string with the desired CRC values, with the same lowercase text as the original string.

Step 2 : Finding Attack Vector

The obvious problem is that CRCs are not meant to be an encryption of some sort. They satisfy the powerful relation $$crc(x) \oplus crc(y)  \oplus crc(z) = crc(x \oplus y \oplus z)$$ which can be used to solve this problem relatively easily. 

There are several ways to solve this problem, maybe even using finite field representation of CRC. However, I still think the method in Step 3 is much easier to deal with than dealing endian issues and figuring out which polynomial is actually used to compute CRC.

Step 3 : Exploiting with Linearity

Denote $x_{16}, x_{32}, x_{64}$ be the CRC values of "a" * 256.

Also, for each $0 \le i \le 255$, we denote $x'_{i, 16}, x'_{i, 32}, x'_{i, 64}$ as the CRC values of "a" * 256 but the $i$th 'a' is changed to 'A'. 

These values can be computed by 257 server interactions, and the CRC computation is of course deterministic. 

Now we can build the CRC values of any length 256 string with 'a' and 'A' only. We start with $x_{16}, x_{32}, x_{64}$, and if the $i$th character is 'A' instead of 'a', we XOR the values $x'_{i, 16} \oplus x_{16}, x'_{i, 32} \oplus x_{32}, x'_{i, 64} \oplus x_{64}$ to our CRC result. 

Now changing 'a' to 'A' appropriately for the result CRC to match the target is something like a subset sum problem with bitstring XOR.

Of course, looking at each bit separately, this is nothing more than a system of linear equations over $\mathbb{F}_2$.

We solve this, find the locations where we have to change the lowercase/uppercase, and get the flag.

This writeup is a compilation of my thoughts and discussions with others.

My solutions are at https://github.com/rkm0959/Cryptography_Writeups/tree/main/2021/0ctfquals.

Problem 1 : zer0lfsr- (35 solves)