# DiceCTF 2022

February 6, 2022This 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, requires $T$ sequential squarings. However, this 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, check out 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.

Notice that $m$ is “randomly sampled” by hashing $g$ and $h$; if we somehow knew $m$ in advance, we could choose $h = g^r$ and $\pi = 1$, which would trick the server. Even so, the scheme is still flawed. The idea 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 leak 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 as an oracle. We query the oracle with a point $Q \in E_B$ and $j$. The oracle outputs whether or not the $j$-invariant of $E_B/\langle P_A' + [k_A] Q \rangle$ is $j$. This setup is similar to the well-known adaptive attack of GPST16, except that in this case we are not allowed to modify $P_A'$.

At this point I will explain hellman’s solution, which is far simpler than mine. The idea is to query the oracle with a point $Q$ of order 2, so that $[k_A] Q$ will only depend 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.