# ångstromCTF 2024

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