rkm0959

Problem Summary

The goal here is to emit the event SendFlag(). To do so, we need to gain control of all three NFTs. 

In the contract file, there is an ERC721 called "TctfNFT" and ERC20 called "TctfToken". We also see that during the initialization the marketplace contract gets 1337 TctfTokens. In the market's constructor, three NFTs are minted, the first to the NFT contract and the other to the market contract. These three NFTs are put on sale on a price of 1, 1337, and some insanely large price. We'll have to get all these NFTs.

Looking at the contract's methods, we see that

• We may get an airdrop of 5 tokens but only once.
• We can create a sell order of NFT under the condition that we have control (approval or owner) over it.
• We can cancel a sell order of NFT under the condition that we have control over it.
• We can purchase an order of NFT with enough tokens. 
• We can purchase an order of NFT with a coupon, but only once. The issuer of the coupon should be the NFT owner, and we have to supply the signature of the issuer for the coupon. For this problem, we pretty much have to know the private key of the issuer. 
• We can use purchaseTest() function only once. Here, the market creates one order and purchases it on its own.

Approach

The constraint gives us some hints on how to approach the problem. 

The first NFT is very cheap, so we can purchase without any trickery. The two functions purchaseTest() and purchaseWithCoupon() are very suspicious, and we can use these only once each. Therefore, each suspicious functions will have us stealing one NFT. Since purchaseWithCoupon() function gives us power to change a price of an order, we should use it to buy the third NFT. The second NFT costs 1337 tokens, and it just happens that the market contract holds 1337 tokens. Therefore, we should use purchaseTest function to steal those tokens. 

Part 1: The purchaseTest()

There are multiple ways to solve this part of the problem. I'll show my solution and sqrtrev's solution. 

The dangerous thing about many of the market's methods is that it takes the order ID as input. If we simply used a mapping for these orders, it would probably not be a problem. However, we use a variable length array to handle our orders. To keep our array length the same as the number of valid orders, we use a nice algorithm which can be seen in _deleteOrder(). When an element of the array is deleted, the element at the back is put at the location of the deleted element. This is also a strategy used in OpenZeppelin's EnumerableSet contracts to keep index of the elements. Now we see the problem - the value at a specific index may change due to element addition and deletion. 

Now let's take a look at the purchaseTest() function again. It creates order, then purchases the order. 

If we look at the createOrder() function again, we see that the only external calls are done to simply check the approval or ownership, but those are done with staticcalls. Therefore, we can't use that to attack. We also see that we can't perform the attack in purchaseOrder(). Thankfully for us, there is an approve call to the NFT address. This can definitely be used to our advantage. 

Basically, we create a dumb NFT and send it to the TctfMarket. We call purchaseTest() with the NFT. 

Inside the approve() call, we will create another order, which sells a dumb NFT that we own at 1337 tokens. Then, we will remove the order that we just created. This will make the order at the order ID equal to the "sell dumb NFT at 1337 token" order. Now the market will happily purchase this new order, sending us 1337 tokens. This gives us enough funds to buy the second NFT anytime we want. 

sqrtrev's solution is much simple, it simply sends the NFT that is being sold at purchaseTest() to our EOA at the approve() call. Inside the purchaseOrder() function, we see that the funds are sent to the owner of the token, so it'll be sent to us. Looking back, I overcomplicated this part of the problem. Part of it is because I took a look at EnumerableSet recently, I guess. It's all very cool ideas, so it's good. 

Part 2: The purchaseWithCoupon()

The first thing we have to notice is that verifyCoupon() is practically a view function. The getOrder() function inside is  view, so it'll be done with staticcall. The ownerOf() function is also view, so staticcall will be used. Therefore, we can't use the same idea to re-enter with a different order at coupon's order ID. Therefore, we can't do anything malicious until the token transfers come in.

We initially thought that the ideas from Part 1 still work, so I wrote all scripts and then realized that it doesn't work. 

I believed that a compiler bug must be the way to go, and began searching on solidity's list of known bugs.

Then I came across https://blog.soliditylang.org/2022/08/08/calldata-tuple-reencoding-head-overflow-bug/

Literally everything matched the challenge - 

• This solidity bug was patched in 0.8.16. The challenge uses 0.8.15.
• It's stated that the last component must be static-sized array. It is bytes32[2].
• It's stated that one dynamic component is needed. There is a bytes value. 
• The bug clears the first 32 bytes of the first dynamic tuple. That happens to be order ID.
• In the blog, it is stated that "Plausible attacks against affected contracts can only occur in situations where the contract accepts a static calldata array as a part of its input and forwards it to another external call without modifying the content." This is exactly what happens in purchaseWithCoupon() and verifyCoupon(). The SignedCoupon struct is sent in as a calldata, and it's directly forwarded.

Some testing shows that if we send a SignedCoupon with order ID 1, it's forwarded to verifyCoupon with order ID 0. 

This means that if we have some order that we control at order 0 and the order for the third NFT at some other place, we can use the coupon. This is because the order used to verify the coupon is the order 0, which we own the NFT of. This means that we can sign our own coupon, but use it on the order for the third NFT with the solidity bug. All that's left is to combine these.

Part 3: Combining Everything

We'll denote the order for the NFTs that we need to get as order #1, #2, #3. We note that for the bug at Part 2, we need a order that we control at the order ID 0. With this in mind, we will set up our attack as follows. We'll use sqrtrev's approach on Part 1.

• Get the TctfToken airdrop. Currently, the orders on the market is [#1, #2, #3].
• Perform sqrtrev's attack. We'll get 1337 tokens, and the orders on the market is still [#1, #2, #3].
• We'll buy NFT #2 with our 1337 tokens, and the orders on the market is [#1, #3]
• We'll mint a dumb NFT to ourself, and create an order. The orders on the market is [#1, #3, us].
• Now we'll buy NFT #1 with 1 token. The orders on the market is [us, #3].
• Now the order ID 0 is an order we control - so the attack from Part 2 works. We buy NFT #3 with 1 token. 

This will give us the flag. Foundry testing is very easy to do, but hardhat scripting was a bit painful. It can be done though.

https://github.com/rkm0959/Cryptography_Writeups/blob/main/2022/WAConQual/rsa-secret-sharing-chal.py

https://github.com/rkm0959/Cryptography_Writeups/blob/main/2022/WAConQual/rsa-secret-sharing-exploit.py

RSA Secret Sharing: by rkm0959 (2 solves in General, 1 solve in Junior)

ON 2-out-of-3 SECRET SHARING BASED ON RSA - MemeCrypt 2022

Solution

Denote $a_i, x_i, b_i$ to be the initial LCG parameters of $LCG_i$. Denote $LCG_{i, j}$ to be the $j$th value that $i$th LCG generated. 

Note that we control $a_1, x_1, b_1$. We see that with $a_i \not\equiv 1 \pmod{q}$, $$LCG_{i, j} \equiv a_i^j x_i + \frac{a_i^j - 1}{a_i - 1} b_i \equiv a_i^j \left(x_i + \frac{b_i}{a_i - 1} \right) - \frac{b_i}{a_i-1} \pmod{q}$$

We are generating roughly $1024$ bit primes, so with heuristics on prime gap we may assume that we will get our 8 primes generated in our first 6000 tries. Our first goal is to find out which of those 6000 tries were the ones that we actually generated a prime successfully.

To do so, we send random $a = a_1, x = x_1, b = b_1$ to the server. This generates random enough values for the LCG we control, and these LCG values will be the value of our primes modulo $q$. For each $n$, there will be two indices $u, v$ such that $$n \equiv LCG_{1, u} \cdot LCG_{1, v} \pmod{q}$$ and we may find these $u, v$ via simple brute force. 

Now we move on to finding the parameters for LCG2, the second LCG. If two indices $u, v$ generated $n$, we see $$n \equiv (LCG_{2, u} q + LCG_{1, u})(LCG_{2, v}q + LCG_{1, v}) \pmod{q^2}$$ and with the knowledge of $u, v, LCG_{1, u}, LCG_{1, v}$, we can write $$LCG_{1, v} LCG_{2, u} + LCG_{1, u} LCG_{2, v} \equiv \frac{n - LCG_{1, u}LCG_{1,v}}{q} \pmod{q}$$ Denote $$C \equiv x_2 + \frac{b_2}{a_2 - 1} \pmod{q}, \quad D \equiv - \frac{b_2}{a_2 - 1} \pmod{q}$$ and we can now write, with $LCG_{2, u} \equiv a_2^u C + D \pmod{q}$ and $LCG_{2, v} \equiv a_2^v C + D \pmod{q}$, that $$\left( LCG_{1, v}  a_2^u + LCG_{1, u} a_2^v \right) C + \left( LCG_{1, u} +LCG_{1, v} \right) D  \equiv \frac{n - LCG_{1, u}LCG_{1,v}}{q} \pmod{q}$$

Note that we have four $n$, so four such equations - and we note that $(C, D, -1)$ is orthogonal to $$\left( LCG_{1, v} a_2^u + LCG_{1, u} a_2^v, LCG_{1, u} + LCG_{1, v}, \frac{n - LCG_{1, u} LCG_{1, v}}{q} \right)$$ when considered as vectors in $\mathbb{F}_q^3$. Therefore, given three such vectors, they will be linearly dependent. This can be expressed algebraically by taking three such vectors, making a matrix with them, and then claiming its determinant is zero. 

This determinant will be a polynomial of $a_2$ over $\mathbb{F}_q$. There are now two ways to finish.

The first one is to directly factor this polynomial to find its roots. This is efficient enough to solve the challenge.

The second one is to get two such polynomials, using the fact that we are given not three, but four such equations. Then we can simply take the GCD of two polynomials to get a polynomial of much smaller degree. This can be solved to get $a_2$.

With $a_2$ calculated, we can solve the linear system to get $C, D$, and then we can solve for $x_2, b_2$ by $$x_2 \equiv C+D \pmod{q}, \quad b_2 \equiv -D(a_2-1) \pmod{q}$$ We can even check for validity of $a_2$ by checking if all four $n \pmod{q^2}$ can be recalculated accordingly. 

We now have full knowledge of the second LCG. There are now two ways to finish. 

The first one is to use Coppersmith's Attack - since we know 2/3 of each primes we can definitely factor each $n$. 

The second one is to apply this same logic to the third LCG - the details are practically the same. 

Comments

To solve the PoW efficiently, instead of doing the entire bytes_to_long you should just check the last 4 bytes of SHA256.

Sending random $a_1, x_1, b_1$ rather than $1, 1, 1$ is a bit better because with $1, 1, 1$, you can't really distinguish $3 \cdot 10 = 5 \cdot 6$ and stuff like that. With random values, it's should be possible to show that such collisions occur with a very low probability, with for example Schwartz-Zippel lemma. Proving this in mathematically precise fashion is left as an exercise for the reader. 

Before computing GCD or factorizing polynomials, it's helpful to reduce the degrees by dividing out some obvious parts.

By giving $a_2$ to the participants of Junior Division, we allow them to go straight into Coppersmith's Attack without setting up for the determinant or doing polynomial stuff. However, the only solver from Junior Division solved this challenge without Coppersmith's Attack. 

We note that to solve the problem, we do not need the first and third RNGs to be an LCG. Also, there's no need to let the participants select their values of $a_1, x_1, b_1$. However, letting the participants choose their $a_1, x_1, b_1$ opens up the possibility for other ideas that end up not working. The intended trap was to select $a_1, x_1, b_1$ so that the first LCG always output the same value. This does not help to solve the challenge to the best of author's knowledge. Letting the third RNG to not be an LCG forces the participant to know Coppersmith's Attack - but I did not really want to test this, since finding the $a_2$ part is already hard enough for WACon 2022 Quals. However, for Junior Division, I decided to award the knowledge of Coppersmith's Attack by giving them $a_2$. I think this was reasonable. 

It's also possible to solve LCG3 easier than the two methods described in the solution - this is due to the solvers in the Junior Division.

Since we have $$n = (LCG_{3, u} q^2 + LCG_{2, u} q + LCG_{1, u})(LCG_{3, v} q^2 + LCG_{2, v} q+ LCG_{1, v})$$ we can rewrite this as $$n' = \frac{n-(LCG_{2,u}q+LCG_{1,u})(LCG_{2,v}q+LCG_{1,v})}{q^2}$$ $$= LCG_{3,u}LCG_{3,v} q^2 +(LCG_{3,u}LCG_{2,v}+LCG_{3,v}LCG_{2,u})q + (LCG_{3,u}LCG_{1,v} + LCG_{3,v}LCG_{1,u}) $$ and now since this value can be calculated as we know $LCG_{1,u},LCG_{1,v},LCG_{2,u},LCG_{2,v},q$. 

Let $$\alpha = \left\lfloor \frac{LCG_{3,u}LCG_{1,v} + LCG_{3,v}LCG_{1,u}}{q} \right\rfloor$$ This is usually on the order of $q$, but by selecting $a_1 = x_1 = b_1 = 1$ we can force this value to be small, usually less than $10^4$.

We now have $$LCG_{3,u}LCG_{1,v} + LCG_{3,v} LCG_{1,u} \equiv n' \pmod{q}$$ and $$LCG_{3,u}LCG_{2,v} + LCG_{3,v}LCG_{2,u} \equiv \lfloor n' / q \rfloor - \alpha \pmod{q}$$ Therefore, if we know $\alpha$, we can solve this using a linear system easily. Since $\alpha$ is in a brute forcable range, we are done. 

This is a beautiful solution that I have overlooked, congratulations to the team! It's very cool that this solution uses the exact setup $a_1 = x_1 = b_1 = 1$ that I advised not to do in my second comment above. Of course, this means that they had to deal with a multiple possibilities for the index, i.e. the reason I advised not to use $a_1=x_1=b_1=1$. To see how they did it, consult their writeup in Korean. 

I gave participants four $n$ instead of three $n$ to make the knowledge of fast polynomial factorization or SageMath not required.

The description "2-out-of-3 secret sharing" comes from Coppersmith's Attack - note that if two share generators collaborate, they can find 2/3 of the primes and therefore can factorize $n$ using Coppersmith's Attack. I thought about making a challenge to check their understanding of why this challenge is about 2-out-of-3 secret sharing, but decided not to do it. Of course, only having one share generator does not allow you to factorize $n$, so this scheme fits the definition of "2-out-of-3 secret sharing". 

The flag was 

WACon{we_should_probably_use_a_better_RNG_than_LCG!!!_(and_hopefully_remove_the_trusted_third_party_:wink:)}

which notes that a trusted third party or TEE is required to check the primality of generated values and compute $n$. 

One of the solvers from General Division practically never studied cryptography in their life, but they are quite strong players in the Korean competitive programming scene. They actually solved all three cryptography challenges, which is a fascinating feat.

Of course, note that we didn't set challenges that require huge amount of prior knowledge in cryptography. 

10 Solves in General Division. Author : Barkingdog

Solution

This is a RSA challenge. We see that menu1 generates primes that have equal upper 296 bits, i.e. $UPPER$. It then returns the value $lower$, which is the value of the lower 216 bits. If we can somehow find the value of $UPPER$, this leads us to knowing much more than half of the upper bits of $p$, so we will be able to factor $n$ via standard RSA attacks using coppersmith algorithm.

Now we focus on finding $UPPER$. Each time we are given $lower$, we know that $UPPER + lower$ is a prime. 

Therefore, for each small primes $p<700$, we actually have a relatively strong information $$UPPER + lower \not\equiv 0 \pmod{p}$$ or $$UPPER \not\equiv -lower \pmod{p}$$ which is good enough to remove one possible candidate of $UPPER \pmod{p}$. 

Given sufficient number of $lower$ such that $UPPER + lower$ is a prime, we will be able to remove all but one possible candidate for $UPPER \pmod{p}$ for each prime $p <700$. This essentially means that we can recover $UPPER \pmod{p}$ for each prime $p<700$.

Combining these information with Chinese Remainder Theorem along with the bound $UPPER < 2^{512}$ is strong enough to deduce the value of $UPPER$. This solves the problem. The code below is due to the challenge author barkingdog.

2 Solves in General Division. Author : rkm0959

Solution

There are four independent challenges that needs to be solved within 300 seconds. 

The flavor of the first two challenges and the last two challenges are a bit different.

For the first two challenges, there is fixed a secret key $k$ and a pseudorandom function $F_k(x)$ which outputs a "random" value in $\mathbb{F}_p$.

We have to distinguish this pseudorandom function with an actual random function. To do this, we can choose our inputs $x$ and then the server will give either $F_k(x)$ or a random value. We have to pass this distinguish test 64 times for each of the two challenges.

For the last two challenges, there is a fixed secret key $k$ and a pseudorandom function $F_k(x)$ which outputs a "random" value in $\mathbb{F}_p$.

We have to recover the secret key $k$. To do this, we can choose our inputs $x$ and the server will give $F_k(x)$. 

Generator 1

The pseudorandom function is $$F_k(x) = \left( \langle k, x \rangle \pmod{2} + \langle k, x \rangle \pmod{3} \right) \pmod{2}$$ with $k \in \{0, 1\}^{256}$ and $x \in \{0, 1\}^{256}$. We can choose whatever $x$ we want and get either $F_k(x)$ or some random $\mathbb{F}_2$ element. 

The most natural distinguishment we get is that $F_k(0) = 0$ regardless of $k$. If we query the output at $x = 0$ and get $1$ as the result, we can immediately conclude that our function is an actual random function. Are there any more inputs like this?

It turns out there are. If $x$ is a unit vector $e_i$ with $i$th coordinate $1$ and others $0$, then we can easily show that $F_k(x)$ must be $0$ regardless of $k$. Now the solution is straightforward - take $60$ of these $x$ values and send them to the server. If all return values are $0$, the function is extremely likely to be a pseudorandom function $F_k(x)$. If at least one return value is $1$, the function must be an actual random function. 

Generator 2

This time, the pseudorandom function is $$F_k(x) = \left( \langle k, x \rangle \pmod{5} + \langle k, x \rangle \pmod{7} \right) \pmod{5}$$ with $k \in \{0, 1\}^{256}$ and $x \in \{0, 1\}^{256}$. The problem is, now the input $x$ is SHA256 hashed first then encoded into $\{0,  1\}^{256}$.

Therefore, we can't really choose what value of $x$ to use - practically, we can only use random inputs to our mysterious function. 

The key idea is rather hard to find because it is surprisingly simple. The idea is that the output distribution of $F_k(x)$ is not uniform over $\mathbb{F}_5$. This can be either tested with some random trials with code or computed with some basic combinatorics, also with code.

The details of both methods are not hard, so I'll not go into the details here. In practice, if you send $6000$ random inputs, we can determine whether the function is $F_k(x)$ or actually random function by checking if the most frequent number appeared more than $1310$ times.

Computing the success probability relatively precisely left to the readers as exercise - this should not be difficult albeit a bit tedious.

Generator 3

We now have to find the secret key $k$. The pseudorandom function is $$F_k(x) = \left( \langle k, x \rangle \pmod{5} \right) \pmod{2}$$ with $k \in \{0, 1, 2, 3\}^{64}$ and $x \in \{0, 1, 2, 3, 4\}^{64}$. The input $x$ is also SHA256 hashed. 

The key idea is linearization. If $F_k(x) = 1$, this implies that $\langle k, x \rangle \pmod{5}$ is either $1$ or $3$ - so $$ \left( \langle k, x \rangle - 1  \right) \left( \langle k, x \rangle - 3 \right) \equiv 0 \pmod{5}$$ Since we know the value of $x$, this gives a quadratic equation on $k$'s each coordinate values. We collect a few thousand such equations.

Now, this can be solved by considering each monomials of degree at most 2 as independent variables, and solving the linear equation. 

Generator 4

This time, $p$ and $q$ are very large - $p$ is 256 bits and $q$ is 128 bits. The pseudorandom function is $$F_k(x) = \left( \langle k, H(x) \rangle \pmod{p} + \langle k, H(x) \rangle \pmod{q} \right) \pmod{p}$$ where $k \in \{0, 1, \cdots , 2^{256}-1 \}^{16}$ and $H(x) = (h^1(x), h^2(x), \cdots, h^{16}(x))$ where $h^n(x)$ is $x$ after SHA256 applied $n$ times then converted into an integer. Note that we once again have no essental control over $H(x)$, so it's practically a random vector.

The idea is that $p$ is much larger than $q$, and $\langle k, H(x) \rangle \pmod{q}$ is between $0$ and $q$. Therefore, the result $F_k(x)$ gives us a range of length $q$ which the value $\langle k, H(x) \rangle \pmod{p}$ must lie. Since we can compute $H(x)$, each input $x$ gives us a precise range for a random linear combination of $k$'s values in mod $p$. Now this reduces to a simple lattice attack with CVP, and my repository is strong enough to solve this challenge. For details, check out https://github.com/rkm0959/Inequality_Solving_with_CVP, or Samsung Software Membership blog.

Background

A PRF takes a key $k$ and an input $x$ and deterministically outputs $y = F(k, x)$. 

A PRF is secure if no efficient adversaries can distinguish (with non-negligible probability) between $F$ and a truly random function between the input/output space. Here, the adversary may query any $x$ and read the output which is either $F(k, x)$ or a random value.

If an adversary who can only query random $x$ in the domain cannot distinguish (with non-negligible probability) between $F$ and a truly random function, the PRF $f$ is called weakly secure PRF, or weak PRF. So Generator 2, 3, 4 are all about (something similar to) weak PRFs.

PRFs and weak PRFs are building blocks of cryptography - Boneh & Shoup's book has an interesting exercise regarding them (18.16), and there are plenty of papers on them as well. The PRFs of the form given in the challenge, i.e. $$F(k, x) = \left( \langle k, x \rangle \pmod{p} + \langle k, x \rangle \pmod{q} \right) \pmod{p}$$ comes from the paper "Exploring Crypto Dark Matter: New Simple PRF Candidates and Their Applications" by Boneh, Ishai, and Passel`egue. This paper was in TCC 2018. The main idea was that these functions are relatively simple to calculate via secure multiparty computation - but since I'm not very knowledgeable in this area yet I cannot explain more details.  

Some attacks on this PRF is noted in the TCC 2018 paper - in page 7, where they mention the PRF with $p=2$ and $q=3$, they also note that in a constant-modulus regime the fact that the modulus is composite is important to prevent a direct linearization attack. Generator 3 covers this idea. They also note that lattice style attacks are possible (BKW) which is done in Generator 4. 

More details are found on page 36, where they outline more attacks. Remark 6.4 explains once again about possible lattice attacks (Generator 4) and Remark 6.5 is once again on linearization attacks (Generator 3). At the start of page 37, there is a note that there is construction is not a PRF - that vectors with Hamming weight 1 is enough for distinguishment. Finding this idea was given as a challenge via Generator 1. 

After a few years, Cheon et al (who taught me cryptography in univ, thanks) wrote about an statistical attack on this PRF in their paper "Adventures in Crypto Dark Matter: Attacks and Fixes for Weak Pseudorandom Functions". This paper was in PKC 2021. Their main idea was simple but very effective - the output distribution of the said PRF was surprisingly far from the uniform distribution. Their calculations are outlined on Section 4, starting at page 8 of the paper. Their calculations are on the PRF with the setting $p=2$ and $q=3$, but the result for arbitrary primes $p, q$ are on Remark 4.4, at the top of page 12. Reading this paper gave me the motivation for setting up this challenge.

Comments

• Note the cache is there to prevent same inputs giving different outputs in the case an actual random function is used.
• The server computes both $F_k(x)$ and the actual random function then returns the output to prevent timing attacks.
• Generator 1 is intended to be a soft introduction to the challenge, letting participants get a sense of what's going on.
• Generator 3's main idea (linearization) have appeared in multiple CTFs before. I can recall three of them.
• When writing the exploit, sending queries in batches is extremely important to fit the time requirements.

Super Guessers won SECCON CTF 2021, with a clean all-solve. I have repeated in this CTF, i.e. won this CTF two years in a row, last year with a strong union of (mostly) Korean cybersecurity professionals. The writeups from last year is at https://rkm0959.tistory.com/165.

This year, there is no collab, only Super Guesser, which is cool :)

Due to some other busy work, I didn't participate fully and solved 3 out of 6 cryptography challenges, and others were done by Baaarkingdog. I also finished one misc challenge, (it was our final solve) but it built on work of many others. (I just finished the challenge)

Challenges were very clean and good, and not painfully difficult (this is usually expected from Japan I think, :))

oOoOoO (by kurenaif)

Thinking about the effect of each "o" or "O" for the value of bytes_to_long(message), we see that this problem is essentially a subset sum problem over modulo $M$. Indeed, the problem is equivalent to solving the system $$ \sum_{i=0}^{127} [79^k \text{   or   } 111^k] \equiv S \pmod{M}$$ which is same as $$\sum_{i=0}^{127} [79^k \pmod{M} \text{   or   } 111^k \pmod{M}] \equiv S \pmod{M}$$ Since the left hand side is between $0$ and $128M$, we can just solve the following for $0 \le c \le 127$. $$\sum_{i=0}^{127} [79^k \pmod{M} \text{  or   } 111^k \pmod{M}] = (S \pmod{M}) + cM$$ which is now a standard knapsack problem, and can be solved via CJLOSS algorithm.

XXX (by theoremoon)

We have 796 bit prime $p$ and around 320 bit $x$, which is the flag.

We are given 6 parameters $(a_i, b_i)$ such that $y_i^2 \equiv x^3 + a_ix + b_i \pmod{p}$ and $y_i < x$. 

Subtracting, we see that $$(a_1 - a_j)x + (b_1 - b_j) \equiv y_1^2 - y_j^2 \pmod{p}$$ so $$-2^{640} < (a_1 - a_j) x + (b_1 - b_j) \pmod{p} < 2^{640}$$ which can be rewritten as $$ -2^{640} < (a_1 - a_j) x + (b_1 - b_j) + p c_j< 2^{640}$$ for $2 \le j \le 6$. Since we know all $a_j, b_j$ values, the only unknown is $x$ and $c_j$ values, and this can be plugged in my CVP repository. 

Sign Wars

There are two mistakes - one is the insecure random of "prequel" which fixes the middle 128 bits, and the insecure python random which is used in the "original". The natural plan is to attack the "prequel" first using the insecure random via standard LLL, find the python random seed using some library, then directly find the random $k$ values for the "original". The latter part can be done very easily with some libraries, so we'll focus on the first one. We write the system as follows. For each 60 equations, we have $$ks \equiv z_1 + rd \pmod{n}$$ $$k \equiv s^{-1}z_1 + rs^{-1}d \pmod{n}$$ $$k_1 + z_1 \cdot 2^{128} + k_3 \cdot 2^{256} \equiv s^{-1}z_1 + rs^{-1}d \pmod{n}$$ $$ 0 \le k_1 = z_1(s^{-1} - 2^{128}) + rs^{-1}d - k_3 \cdot 2^{256} \pmod{n} < 2^{128}$$ $$0 \le z_1(s^{-1} - 2^{128}) + rs^{-1}d - k_3 \cdot 2^{256} + cn < 2^{128}$$ and now this can be plugged in CVP repository. Note that $d, z_1$ is fixed and $0 \le z_1 < 2^{128}$, $0 \le k_3 < 2^{128}$.