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 and . Bob wishes to learn one of the messages, for some . 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:
Alice samples group elements and , then sends the curves and to Bob.
Bob chooses one of Alice’s curves based on the message he wants to learn, namely . He samples a group element , applies it to the curve to get , and sends it to Alice. Note that Bob’s choice is hidden by .
Alice inverts and , then applies each element to Bob’s curve to get She uses the first curve as a key to encrypt , and the second curve to encrypt . Finally, she sends both ciphertexts to Bob.
Since is encrypted with , 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 , 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 to the server. This will result in the keys and , 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 is first hashed to a target vector where is randomly sampled for every signature. To find a preimage, the signer chooses an initial vector where is secret and is usually zero (but incremented if we need a different initial vector). The preimage will be a vector in , where is the secret subspace. In the challenge, the code has been slightly modified so that the initial vector vector is now computed as This leads to a vulnerability: if we repeatedly invoke the signing oracle with the same message, will be constant (assuming is zero), yet will be new each time (thanks to the salt). Given two preimages and , 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.