ångstromCTF 2024

This year I wrote five challenges for ångstromCTF. Besides the writeups in this post, you can find my solution code at github.com/defund/ctf.

random rabin

This is an implementation of the Rabin cryptosystem. The server encrypts a random message, decrypts it, and gives a random plaintext (out of four) to us. Our task is to recover the original message. Let’s call the original message x. Then the four possible plaintexts are x, -x, y, and -y. If the server gives x or -x, we are done. Otherwise, notice that x + y is a non-trivial multiple of p, a prime factor of the RSA modulus (see here for an explanation). And since we know that x is small (16 bytes), y must be a good approximation of p. We can apply Coppersmith’s method to recover a small root of the polynomial f(X) = X + y modulo the hidden factor p, which gives us x.

Update: turns out you can also just square whatever value you get, modulo n, and then take the integer square root. Much easier!

tss1

This challenge models a two-party Schnorr threshold signature scheme. The server acts as one party, and we act as the other. Our goal is to produce an aggregate signature for a message which the server refuses to sign. In tss1, we can accomplish this with a rogue key attack. Let’s say the server’s public key is P. If we were honest we would generate our own public key Q, and the aggregate key would be P + Q. Instead, we’ll send a fake public key P - Q so that the aggregate key is simply Q. This means that we can produce aggregate signatures without the help of the server.

Simon Says

We’re given three different encryptions of the flag, under the same key but with 68, 69, and 72 rounds of encryption. Since it’s the same key, the 72-round ciphertext can be thought of as encrypting the 68-round ciphertext under only four rounds of encryption. This means that we can recover the last four round keys, e.g. with a SAT solver. Since the key schedule is linear, we can easily recover the original key and decrypt the flag.

BLÅHAJ

This is supposed to be a harder version of the ikea challenge from Midnight Sun CTF 2023 Quals. In that challenge, you needed to factor a 2048-bit RSA modulus given p + b^2 q and a^2 p + q, where a and b are random 1024-bit integers. Everything is the same here, except now we are given p + bq and ap + q. This rules out the approximation trick used to solve ikea.

Let c = p + bq and d = ap + q. Then cd = a p^2 + b q^2 = dp + cq. In other words, we have derived a multilinear equation cd - dp - cq = 0 (you can also find this with a Gröbner basis reduction). Since p and q are both half the bitlength of n, we can apply LLL (with a small amount of brute force) to find this short solution.

tss2

We have the same setup as tss1, except now the server validates our public key by asking for a signature. This is a perfect situation to apply the ROS attack, by leveraging the fact that we can open up many concurrent connections to the server. I unfortunately don’t have enough time to explain the attack in detail, but the high-level summary is that we open 256 concurrent connections, and choose our nonces so that we can take a linear combination of the server’s signature shares and obtain a new signature share for the target message. It’s a really cool attack, and I highly suggest reading through the paper.