DiceCTF 2025 Quals

This year, I wrote four challenges for DiceCTF Quals. In this post, I’ll go over the solutions for each challenge. You can find my solution code at github.com/defund/ctf.

vorpal-sword

This challenge implements the RSA-based oblivious transfer protocol described on Wikipedia. Our goal as the receiver is to leak both messages, thereby breaking the protocol’s security guarantee.

In the protocol, we send a value $v$ to the server, which uses $k_0 := (v - x_0)^d$ and $k_1 := (v - x_1)^d$ as encryption keys for the messages. In particular, the server sends $c_0 := k_0 + m_0$ and $c_1 := k_1 + m_1$, as the ciphertexts. Here, $x_0$ and $x_1$ are random values generated by the server, and $d$ is the RSA private exponent.

The key to attacking this protocol is to notice that we can choose $v := (x_0 + x_1)/2$ (modulo $n$), so that $k_0 = (-(x_0 - x_1)/2)^d$ and $k_1 = ((x_0 - x_1)/2)^d$. Since $d$ is odd, we have $k_0 = -k_1$. This correlation is useful because we can compute $c_0 + c_1 = (k_0 + m_0) + (k_1 + m_1) = m_0 + m_1$, which is the sum of the messages. And since the messages are highly structured strings (either a death or survive message in the choose-your-own adventure game), we can figure out what they are from the sum alone.

winxy-pistol

This is a follow-up to vorpal-sword, where the protocol differs in two ways. First, messages are encrypted differently: the server sends $c_0 := m_0 \oplus H(k_0)$ and $c_1 := m_1 \oplus H(k_1)$, where $H$ is a hash function. This means that the solution from vorpal-sword will not work anymore. Second, the server uses a fixed RSA key, instead of generating a new one each time, for the oblivious transfers. We are going to attack the second change.

Suppose we behave honestly, as described on Wikipedia. For example, if we want to learn $m_0$ then we pick $v := (x_0 + k^e)$, where $k$ is a value we choose and $e$ is the public exponent. This guarantees $k_0 = k$, so we can always decrypt $c_0$. In order to decrypt $c_1$, we will open a new connection with the server and interact with it in parallel with our original connection.

Let $m_0'$ and $m_1'$ be the two messages and $x_0'$ and $x_1'$ be the random values in the new connection. If we pick $v' := v - x_1 + x_0'$, then the key for $m_0'$ will be $k_0' = (v' - x_0') = (v - x_1)^d$, which is precisely $k_1$! Therefore, the corresponding ciphertext will be $c_0' = m_0' \oplus H(k_0') = m_0' \oplus H(k_1)$. By guessing $m_0'$, we can obtain $H(k_1)$ and decrypt $c_1$ in the original connection. If $m_0'$ is a death message in the choose-your-own-adventure game (this is true 50% of the time), then guessing it is easy. Otherwise, we can open a new connection and try again.

fairy-ring

This challenge implements an insecure ring signature scheme. Given a set of public keys (which we do not know the private keys for), our goal is to forge a ring signature for some subset of the keys (we can choose the subset).

Let’s start by looking at how the challenge’s ring signature scheme works. Each public key $\mathsf{pk}_i$ defines a trapdoor function $f_i$, which is hard to invert unless you know the corresponding secret key. In order to sign a message for a ring you are in, you first hash the message to a target value $t$. The signature is a list of preimages $x_1, \dots, x_\ell$ for all of the public keys $\mathsf{pk}_1, \dots, \mathsf{pk}_\ell$ in the ring such that $f(x_1) \oplus \dots \oplus f(x_\ell) = t$. Now suppose you are the $j$-th member of the ring. In order to generate a signature, you first randomly sample $(x_i)_{i \not= j}$. Then, you sample a preimage $x_j$ such that $f(x_j) = t \oplus \bigoplus_{i \not= j} f_i(x_i)$; this is possible since you know the trapdoor for $f_j$. The signature is $x_1, \dots, x_\ell$, which indeed satisfies the verification check.

So how do we forge a signature? It turns out that depending on the trapdoor function, this construction is not secure. In particular, this challenge uses the UOV trapdoor function (see my previous blog post for an intro to UOV). When $f: \mathbb{F}^n \to \mathbb{F}^m$ is a UOV map (actually, a multivariate quadratic map in general), it turns out that we can always find $x, x'$ such that $f(x) - f(x') = y$, for any choice of $y$.

Let’s assume we know how to do this and see how to forge a ring signature. First, we’re going to choose a ring which consists of two copies the same public key (this is allowed by the server). Our goal now is to find $x$, $x'$ such that $f(x) \oplus f(x') = H(m)$, where $f$ is the trapdoor function corresponding to the public key and $m$ is some fixed message we need to sign in order to obtain the flag. Now since the UOV trapdoor function is defined with a binary field, addition/subtraction and xor are actually the same! This means we can just pick $x, x'$ such that $f(x) - f(x') = H(m)$, which we have assumed can be done.

Finally, let’s look at how to find $x, x'$ such that $f(x) - f(x') = y$. First, pick some arbitrary vector $\delta \in \mathbb{F}^n$. Our goal will be to find some $x$ such that $f(x + \delta) - f(x) = y$. Letting $f'$ be the polar form of $f$ (again, see my previous blog post), we can rewrite this as finding $x$ such that $f'(x, \delta) + f(\delta) - f(0) = y$. This is a linear equation in $x$, so we can solve for it.

nil-circ

This is going to be a very high-level explanation. I’m going to assume you have a rough understanding of how the following things work: garbled circuits, the Free-XOR optimization implemented in swanky, and the oblivious transfer protocol being modified in the challenge.

First, let’s look at how the OT protocol is being modified. Instead of computing the keys as $k_0 := H(aB)$ and $k_1 := H(a(B - A))$ (I’m using additive notation here), the server instead computes $k_0 := H(aB)$ and $k_1 := H(a(A - B))$. We can attack this by picking $B := A/2$, so that $k_0$ is equal to $k_1$. The server uses the keys to encrypt a set of wire labels: $k_0$ for the zero-label $W_0$ and $k_1$ for the one-label $W_1$. In particular, the ciphertexts are $c_0 := W_0 \oplus k_0$ and $c_1 := W_1 \oplus k_1$. But since $k_0$ and $k_1$ are equal, this means that we have $c_0 \oplus c_1 = W_0 \oplus W_1$. In the Free-XOR optimization, $\Delta = W_0 \oplus W_1$ is the global offset used across all of the wires. This value must be kept secret for security to hold.

The rest of the challenge is figuring out how to leverage the knowledge of $\Delta$ to obtain the server’s inputs to the garbled circuit. My solution is roughly as follows: since we know the global offset $\Delta$, know both labels for every wire in the circuit. Then whenever we receive a garbled table for an AND gate, we can figure out what the original labels represent, by decrypting the entire truth table. In general, each input labels is some XOR combination of the circuit inputs. We can build a linear system for all of these constraints and solve for the circuit inputs.