DiceCTF 2021

February 7, 2021

It’s been a while since I wrote challenges for a CTF! Besides the writeups in this post, you can find my solution code at github.com/defund/ctf.


We’re given an implementation of the Benaloh cryptosystem along with a public key and encrypted flag. Since the block size is r=17r = 17, the flag is split into nibbles (4 bits), and each nibble is encrypted separately.

To encrypt a message mm, the algorithm first computes ymy^m. It then randomizes this value by sampling a nonce uu and multiplying by the mask uru^r. In this challenge, the vulnerability is that the nonces are not randomly chosen, but instead generated via LCG. Let’s call the initial seed value u0u_0. Then we have masks of the form u0u_0, au0+ca u_0 + c, a(au0+c)+ca (a u_0 + c) + c, and so on.

Our first insight is that if we already know some nibble mm, we can divide the associated ciphertext by ymy^m to recover its mask. Since we know the flag starts with dice{, we can recover 10 masks total, which we’ll call α1,,α10\alpha_1, \dots, \alpha_{10}. Given this sequence of masks, our goal will be to predict future masks. From there, we can derandomize the ciphertexts and solve the discrete logarithm, which is easy since mm ranges from 0 to 15.

To motivate the final step of the solution, let’s consider the scenario where aa and cc are public parameters. In this case, the setup is identical to that of the Franklin-Reiter related-message attack on RSA. We can construct two univariate polynomials xrα1=0(ax+c)rα2=0\begin{aligned} x^r - \alpha_1 & = 0 \\ (ax + c)^r - \alpha_2 & = 0 \end{aligned} with the common root u0u_0, and their polynomial GCD will be xu0x - u_0.

Unfortunately, we do not have the luxury of dealing with univariate polynomials. Since aa and cc are unknown in the challenge, we instead have multivariate polynomials with a common root (a,c,u0)(a, c, u_0). This calls for a more powerful tool, namely Gröebner basis reduction. Informally, this process is a hybrid of polynomial GCD and Gaussian elimination. It attempts to reduce a set of multivariate polynomials into a simpler form, while preserving roots.

Using the known masks, let’s define a few polynomials (you only need four) and compute their Gröeber basis. We get something like c17+134154=0u+316980c=0a+166006=0.\begin{aligned} c^{17} + 134 \ldots 154 & = 0 \\ u + 316 \ldots 980 c & = 0 \\ a + 166 \ldots 006 & = 0. \end{aligned} Although we cannot directly recover uu, we can rewrite each nonce as some constant multiple of cc. It follows that we can rewrite each mask as a constant multiple of c17c^{17} — but we know this value! As a result, we can compute the remaining masks and recover the flag.

signature sheep scheming signature schemes

For some context, I came up with this challenge while trying to make a legitimately secure signature scheme. As you can see, that didn’t work out — although I guess a CTF challenge isn’t so bad either :)

If you aren’t familiar with lattice-based cryptography, I would highly suggest reading Chris Peikert’s survey. Other than that, the challenge setup is pretty simple: the server signs arbitrary messages, and our goal is to recover its secret key.

In order to generate a keypair, the algorithm samples a uniform public matrix AA, a short secret matrix SS, and a short error matrix EE. The private key is SS, and the public key is AA along with B=AS+EB = AS + E. This is a fairly common idea; see FrodoKEM for a real-world example.

On the other hand, the signing algorithm is completely made up. Essentially, it is a sigma protocol made non-interactive via the Fiat-Shamir transform. The prover first commits to an “ephemeral key” b=As+eb = A s + e. The verifier’s challenge is a short vector cc, and the server’s response is r=sScr = s - S c. Finally, the verifier checks that ArA r is approximately equal to bBcb - Bc.

The issue is that this sigma protocol is not zero-knowledge. By collecting a bunch of samples, we can build the matrix equation R=S+SCR = S' + SC. Although this might appear like an LWE instance at first glance, all of the matrices are short. In fact, the computation will never wrap around the modulus. As a consequence, we can lift this equation to the integers. All that remains is to solve for SS by treating SS' as an error term. I personally did a least squares optimization, although lattice reduction should also work.