DiceCTF 2022

February 6, 2022

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


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 TT 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=g2Th = g^{2^T} in an RSA group. To the best of our knowledge, this requires TT 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 hh 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 TT 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 hh with relatively few squarings. For some 128-bit integer mm, let qq and rr be the quotient and remainder of 2T2^T divided by mm. If we supply π=gq\pi = g^q, the server can easily verify h=πmgrh = \pi^m g^r, since this only requires 256 squarings.

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


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 (c1,c2)(c_1, c_2), and we will modify c2c_2 in order to induce timing differences in the decryption algorithm. If we attempt to decrypt (c1,c2)(c_1, c_2'), there are two scenarios:

In the first scenario, memcmp will iterate over the bytes of c1c_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 c2c_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(EAB)j(E_{AB}), and outputs the ciphertext (PA,QA,RA,H(j)m),(P_A', Q_A', R_A', H(j) \oplus m), where RA=PAQAR_A' = P_A' - Q_A' is used to recover the curve EBE_B. In order to exploit the timing difference, we will modify QAQ_A' and jj, while also recalculating RAR_A'. If the decryption recovers mm, the original and re-encrypted ciphertexts will share a common prefix PAP_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 EBE_B and PAP_A' according to an honestly generated ciphertext, and abstract the timing attack into an oracle. We query the oracle with a point QEBQ \in E_B and jj, and it outputs whether or not the jj-invariant of EB/PA+[kA]QE_B/\langle P_A' + [k_A] Q \rangle is jj. This setup is similar to a well-known adaptive attack on SIDH, except that in this case we are not allowed to modify PAP_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 QQ of order 2, so that [kA]Q[k_A] Q only depends on the LSB of kAk_A. In other words, there are only 2 possible jj-invariants, and we can query the oracle to determine which one is correct. Now that we know the LSB of kBk_B, we can query the oracle with a point of order 4, and again there only 2 possible jj-invariants to guess. By repeating this process, we can leak the entire secret key and decrypt the flag.