# 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.