DiceCTF 2023

February 5, 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.


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 m0m_0 and m1m_1. Bob wishes to learn one of the messages, mbm_b for some b{0,1}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 [a0][\mathfrak{a}_0] and [a1][\mathfrak{a}_1], then sends the curves [a0]E0[\mathfrak{a}_0] E_0 and [a1]E0[\mathfrak{a}_1] E_0 to Bob.

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

  3. Alice inverts [a0][\mathfrak{a}_0] and [a1][\mathfrak{a}_1], then applies each element to Bob’s curve to get [a0]1[b][ab]E0,[a1]1[b][ab]E0.[\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 m0m_0, and the second curve to encrypt m1m_1. Finally, she sends both ciphertexts to Bob.

  4. Since mbm_b is encrypted with [ab]1[b][ab]E0=[b]E0[\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 [a]E0[\mathfrak{a}] E_0, [a]1E0[\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 E0E_0 to the server. This will result in the keys [a0]1E0[\mathfrak{a}_0]^{-1} E_0 and [a1]1E0[\mathfrak{a}_1]^{-1} E_0, both of which we can compute. This allows us to decrypt both ciphertexts, yielding the flag.


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 MM is first hashed to a target vector t=H(Msalt),\mathbf{t} = H(M \mathbin\Vert \mathsf{salt}), where salt\mathsf{salt} is randomly sampled for every signature. To find a preimage, the signer chooses an initial vector v=H(Msaltseedctr),\mathbf{v} = H(M \mathbin\Vert \mathsf{salt} \mathbin\Vert \mathsf{seed} \mathbin\Vert \mathsf{ctr}), where seed\mathsf{seed} is secret and ctr\mathsf{ctr} is usually zero (but incremented if we need a different initial vector). The preimage will be a vector in v+Ov + O, where OO is the secret subspace. In the challenge, the code has been slightly modified so that the initial vector vector is now computed as v=H(Mseedctr).\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, v\mathbf{v} will be constant (assuming ctr\mathsf{ctr} is zero), yet t\mathbf{t} will be new each time (thanks to the salt). Given two preimages v+o1\mathbf{v} + \mathbf{o}_1 and v+o2\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.