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 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 in an RSA group. To the best of our knowledge, this requires 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 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 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 with relatively few squarings. For some 128-bit integer , let and be the quotient and remainder of divided by . If we supply , the server can easily verify , since this only requires 256 squarings.
Note that is “randomly sampled” by hashing and . However, the sample space is all 128-bit integers, which is flawed. The attack is as follows: let be the product of all primes less than , with additional multiplicity for the small primes. The exact value of is not so important, but we will succeed whenever divides (this happens quite often). In this case, we can trick the server by choosing
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
and we will modify
in order to induce timing differences in the decryption algorithm. If we
attempt to decrypt
there are two scenarios:
is sufficiently close to , 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 .
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
before returning. In the second scenario,
immediately return. Although both decryptions will fail, we can leverage
this timing difference to find the “borderline” value of
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 , and outputs the ciphertext where is used to recover the curve . In order to exploit the timing difference, we will modify and , while also recalculating . If the decryption recovers , the original and re-encrypted ciphertexts will share a common prefix . 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 and according to an honestly generated ciphertext, and abstract the timing attack into an oracle. We query the oracle with a point and , and it outputs whether or not the -invariant of is . This setup is similar to a well-known adaptive attack on SIDH, except that in this case we are not allowed to modify .
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 of order 2, so that only depends on the LSB of . In other words, there are only 2 possible -invariants, and we can query the oracle to determine which one is correct. Now that we know the LSB of , we can query the oracle with a point of order 4, and again there only 2 possible -invariants to guess. By repeating this process, we can leak the entire secret key and decrypt the flag.