DiceCTF 2023

This year I wrote two challenges for DiceCTF, both based on post-quantum cryptography. A nontrivial aspect of the “vinaigrette” challenge was understanding and interfacing with the C backend, which I won’t talk about in this post. However, you can find my solution code at github.com/defund/ctf.

seaside

In this challenge, we are presented with an isogeny-based oblivious transfer protocol built with the CSIDH group action. If you aren’t familiar with CSIDH, I would suggest reading sections 1.1, 6, and 7 of the original paper.

To summarize the oblivious transfer protocol, Alice has two messages $m_0$ and $m_1$. Bob wishes to learn one of the messages, $m_b$ for some $b \in \{0, 1\}$. We have two security guarantees: Bob should not learn anything about the other message, and Alice should not learn Bob’s choice. To accomplish this, the two parties perform the following steps:

1. Alice samples group elements $[\mathfrak{a}_0]$ and $[\mathfrak{a}_1]$, then sends the curves $[\mathfrak{a}_0] E_0$ and $[\mathfrak{a}_1] E_0$ to Bob.

2. Bob chooses one of Alice’s curves based on the message he wants to learn, namely $[\mathfrak{a}_b] E_0$. He samples a group element $[\mathfrak{b}]$, applies it to the curve to get $[\mathfrak{b}] [\mathfrak{a}_b] E_0$, and sends it to Alice. Note that Bob’s choice is hidden by $[\mathfrak{b}]$.

3. Alice inverts $[\mathfrak{a}_0]$ and $[\mathfrak{a}_1]$, then applies each element to Bob’s curve to get $$[\mathfrak{a}_0]^{-1} [\mathfrak{b}] [\mathfrak{a}_b] E_0, \quad [\mathfrak{a}_1]^{-1} [\mathfrak{b}] [\mathfrak{a}_b] E_0.$$ She uses the first curve as a key to encrypt $m_0$, and the second curve to encrypt $m_1$. Finally, she sends both ciphertexts to Bob.

4. Since $m_b$ is encrypted with $[\mathfrak{a}_b]^{-1} [\mathfrak{b}] [\mathfrak{a}_b] E_0 = [\mathfrak{b}] E_0$, which Bob knows, he can decrypt the corresponding ciphertext.

The flaw with this protocol stems from a peculiarity of the CSIDH group action. Namely, for any curve $[\mathfrak{a}] E_0$, $[\mathfrak{a}]^{-1} E_0$ is its quadratic twist, which is easily computable. To see why this is useful, let’s return to the challenge. The server acts as Alice, we act as Bob, and our goal is to learn both messages. Instead of behaving according to the protocol, suppose we send $E_0$ to the server. This will result in the keys $[\mathfrak{a}_0]^{-1} E_0$ and $[\mathfrak{a}_1]^{-1} E_0$, both of which we can compute. This allows us to decrypt both ciphertexts, yielding the flag.

vinaigrette

This challenge is about the UOV multivariate signature scheme. If you aren’t familiar with UOV, I would suggest reading my previous blog post. We are also working with a specific implementation, which is described here.

Our goal is to forge a signature for a particular message, given a signing oracle which accepts any other message. In the original UOV implementation, the message $M$ is first hashed to a target vector $$\mathbf{t} = H(M \mathbin\Vert \mathsf{salt}),$$ where $\mathsf{salt}$ is randomly sampled for every signature. To find a preimage, the signer chooses an initial vector $$\mathbf{v} = H(M \mathbin\Vert \mathsf{salt} \mathbin\Vert \mathsf{seed} \mathbin\Vert \mathsf{ctr}),$$ where $\mathsf{seed}$ is secret and $\mathsf{ctr}$ is usually zero (but incremented if we need a different initial vector). The preimage will be a vector in $v + O$, where $O$ is the secret subspace. In the challenge, the code has been slightly modified so that the initial vector vector is now computed as $$\mathbf{v} = H(M \mathbin\Vert \mathsf{seed} \mathbin\Vert \mathsf{ctr}).$$ This leads to a vulnerability: if we repeatedly invoke the signing oracle with the same message, $\mathbf{v}$ will be constant (assuming $\mathsf{ctr}$ is zero), yet $\mathbf{t}$ will be new each time (thanks to the salt). Given two preimages $\mathbf{v} + \mathbf{o}_1$ and $\mathbf{v} + \mathbf{o}_2$, their difference is a vector in the secret subspace. By sampling more preimages, we can recover the full subspace and sign for arbitrary messages, thereby breaking the scheme.