DiceCTF 2022

This year I wrote two cryptography challenges for DiceCTF. As always, you can find my solution code at github.com/defund/ctf.

pow-pow

Verifiable delay functions (VDFs) offer a neat way to enforce time delays in distributed protocols and other applications. Basically, the goal is to design a function which requires $T$ steps to compute, even with parallelism. By estimating the performance of modern hardware, we obtain a lower bound on how quickly anyone can evaluate the function. The classic example is computing $$h = g^{2^T}$$ in an RSA group. To the best of our knowledge, this requires $T$ sequential squarings. However, the function alone does not constitute a VDF. We also need to generate a “proof of work,” which allows others to efficiently verify $h$ is correct. There are multiple ways to do this, and this challenge presents a modified version of Wesolowski’s VDF. For more background, see vdfresearch.org (and this survey in particular).

Returning to the challenge, our goal is to provide a valid proof of work. Since $T$ is prohibitively large, we cannot possibly evaluate the VDF. Nonetheless, let’s take a look at how to generate the proof. The idea is for us to provide an intermediate value which allows the server to compute $h$ with relatively few squarings. For some 128-bit integer $m$, let $q$ and $r$ be the quotient and remainder of $2^T$ divided by $m$. If we supply $\pi = g^q$, the server can easily verify $h = \pi^m g^r$, since this only requires 256 squarings.

Note that $m$ is “randomly sampled” by hashing $g$ and $h$. However, the sample space is all 128-bit integers, which is flawed. The attack is as follows: let $L$ be the product of all primes less than $2^{20}$, with additional multiplicity for the small primes. The exact value of $L$ is not so important, but we will succeed whenever $m$ divides $L$ (this happens quite often). In this case, we can trick the server by choosing $$g = 2^L, \quad h = 1, \quad \pi = 2^{-r (L/m)}.$$

psych

This challenge is inspired by GJN20, which introduced a generic timing attack on the Fujisaki-Okamoto transform. In order to achieve CCA security, the FO transform’s decryption algorithm re-encrypts the plaintext to verify that the the original ciphertext was well-formed. As it turns out, this equality check must be constant-time to guarantee security. The authors demonstrated a real-world attack against FrodoKEM, which used memcmp in its reference implementation. The idea is as follows: a FrodoKEM ciphertext is a tuple $(c_1, c_2)$, and we will modify $c_2$ in order to induce timing differences in the decryption algorithm. If we attempt to decrypt $(c_1, c_2')$, there are two scenarios:

• $c_2'$ is sufficiently close to $c_2$, and the decryption algorithm recovers the original plaintext (this is common in lattice-based schemes like FrodoKEM). In this case, the re-computed ciphertext is $(c_1, c_2)$.

• The decryption algorithm obtains a different plaintext. In this case, the re-computed ciphertext is totally different.

In the first scenario, memcmp will iterate over the bytes of $c_1$ before returning. In the second scenario, memcmp will immediately return. Although both decryptions will fail, we can leverage this timing difference to find the “borderline” value of $c_2$, and this is enough to recover the secret key.

In this challenge, we consider a similar setup for SIKE, an isogeny-based KEM. If you aren’t familiar with SIKE, I would highly suggest reading Craig Costello’s tutorial. To summarize, the public and private keys correspond with Alice’s SIDH keypair. The encryption algorithm generates an ephemeral SIDH keypair for Bob, derives a shared key $j(E_{AB})$, and outputs the ciphertext $$(P_A', Q_A', R_A', H(j) \oplus m),$$ where $R_A' = P_A' - Q_A'$ is used to recover the curve $E_B$. In order to exploit the timing difference, we will modify $Q_A'$ and $j$, while also recalculating $R_A'$. If the decryption recovers $m$, the original and re-encrypted ciphertexts will share a common prefix $P_A'$. Otherwise, they will look totally different. We can distinguish the two cases by observing how long it takes for the decryption to fail.

Let’s fix $E_B$ and $P_A'$ according to an honestly generated ciphertext, and abstract the timing attack into an oracle. We query the oracle with a point $Q \in E_B$ and $j$, and it outputs whether or not the $j$-invariant of $E_B/\langle P_A' + [k_A] Q \rangle$ is $j$. This setup is similar to a well-known adaptive attack on SIDH, except that in this case we are not allowed to modify $P_A'$.

I’ll proceed by explaining hellman’s solution, since it’s much simpler than mine. The idea is to query the oracle with a point $Q$ of order 2, so that $[k_A] Q$ only depends on the LSB of $k_A$. In other words, there are only 2 possible $j$-invariants, and we can query the oracle to determine which one is correct. Now that we know the LSB of $k_B$, we can query the oracle with a point of order 4, and again there only 2 possible $j$-invariants to guess. By repeating this process, we can leak the entire secret key and decrypt the flag.