# ångstromCTF 2024

May 27, 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.