DiceCTF 2022

February 06, 2022

This year I wrote two crypto challenges for DiceCTF. Full solution code is available at github.com/defund/ctf.

pow-pow

The idea behind this challenge is constructing a false proof of work. In this case, I slightly modified Wesolowski’s verifiable delay function (VDF); for more background, see vdfresearch.org.

We want to prove to the server that we have computed h = g^(2^T). When the group order is unknown (e.g. the RSA group), we don’t know any better way than T sequential squarings. On the other hand, the server wants to efficiently verify the solution. It uniformly samples a challenge m from [0, 2^128). The prover then must compute pi := g^(2^T // m). Finally, the server verifies h = pi^m g^r, where r := 2^T mod m. This is all made non-interactive with the Fiat-Shamir transform.

Now, to trick the server notice that in general, a significant fraction of integers are smooth. I computed L to be the product of all primes less than 2^20, along with some additional powers for the smaller ones. Whenever the hash function evaluates to an m which divides L, we will able to solve the challenge. For example, let g := 2^L, h := 1, and pi := 2^(-r*L//m).

psych

The story of this challenge begins with GJN20, which introduced a generic timing attack on the Fujisaki-Okamoto transform. The idea is if the ciphertext equality check is not constant-time, e.g. memcmp, we can break CCA security. We first compute an honest encapsulation and then perturb the later bytes of the ciphertext. Suppose the malicious ciphertext decrypts to the same message. Then the decapsulation will derive the proper random coins and construct the honest ciphertext. Since the honest and malicious ciphertexts share the same prefix, memcmp will take longer to determine inequality. On the other hand, if the malicious ciphertext decrypts to a different message memcmp should terminate almost instantly. The authors apply this to Frodo, a lattice-based KEM where the solution is fairly obvious. Here, we will figure out how to attack SIKE, which is based on supersingular isogenies. If you are not familiar with SIKE, I would highly suggest reading Craig Costello’s primer.

A SIKE ciphertext consists of a SIDH public key followed by H(j) ⊕ m, where j is the j-invariant both parties obtain through key exchange. Let’s reformulate the timing attack as an oracle. We may query whether a public key pk yields a particular j-invariant j by supplying the ciphertext pk || H(j') ⊕ m. However, remember that pk must share a prefix with an honest ciphertext. A SIDH public key consists of the x-coordinates of three points, P, Q, and P - Q. Hence the most intuitive way to maintain a shared prefix is performing an adaptive attack on SIDH where the first basis point is fixed. Something like GPST16 will not work because it modifies both.

This is when I will deviate from my solution to describe hellman’s, since it is much more elegant. Let P and Q be the honest basis points. Suppose we supply [2^(e2-1)] Q instead of Q. The server will compute kernel P + [k 2^(e2-1)] Q. Since the order of Q is 2^(e2-1), the kernel will only depend on the LSB of k. We can query the oracle to determine whether it is set. Then we continue with [2^(e2-2)] Q to determine the second bit, and so on to obtain the entire key.

Now, one may notice that we are providing a basis point that is not of order 2^e2. I will briefly sketch my solution, which does not have this issue. Note: this condition is irrelevant to the challenge and SIKE in general. For simplicity, assume k is odd (the solution is easily generalizable). Instead of querying on [2^i] Q, I used [2^i + 1] Q. The server computes the kernel P + [k] [2^i + 1] Q. Taking a step back, we can imagine the isogeny with kernel P + [k] Q as a chain of 2-isogenies E_0 -> E_1 -> ... -> E_e2. Notice that the isogenies computed from kernels P + [k] Q and P + [k] [2^i + 1] Q == P + [k] Q + [k 2^i] Q diverge at the curve E_i. Let phi_i be the composition of the first i 2-isogenies, S_i be phi_i(P + [k] Q), and G_i be [2^i] phi_i([k] Q). Suppose we know S_{i+1} and G_{i+1}. The goal will be to recover S_i and G_i using the oracle. There are three candidate E_i curves, namely the ones connected to E_{i+1} by a 2-isogeny. If i+1 < e2 we can rule out one of them since S_i must lie above the kernel E_i -> E_{i+1}, or equivalently S_{i+1} cannot lie above the kernel of the dual. For each candidate E_i -> E_{i+1}, we take the preimage of S_{i+1} to obtain candidates for S_i. We take the preimage of G_{i+1} and then compute its division points to obtain candidates for G_i. The proper combination satisfies the following: the isogeny with domain E_i and kernel S_i + G_i and the isogeny with domain E_0 and kernel P + [k] [2^i + 1] Q have isomorphic codomains. Using the oracle, we can identify the correct pair. Starting with i = e2, notice that S_i and G_i are both the identity. We inductively recover the intermediate images. Once we reach i = e2//2, we can actually compute the isogeny with kernel G_i to arrive at the public key’s curve. This means that we have succesfully computed the dual isogeny. We solve an extended discrete logarithm (easy since the group order is smooth) to recover the key from the kernel.