DiceCTF 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.

benaloh

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

To encrypt a message $m$, the algorithm first computes $y^m$. It then randomizes this value by sampling a nonce $u$ and multiplying by the mask $u^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 $u_0$. Then we have masks of the form $u_0$, $a u_0 + c$, $a (a u_0 + c) + c$, and so on.

Our first insight is that if we already know some nibble $m$, we can divide the associated ciphertext by $y^m$ to recover its mask. Since we know the flag starts with dice{, we can recover 10 masks total, which we’ll call $\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 $m$ ranges from 0 to 15.

To motivate the final step of the solution, let’s consider the scenario where $a$ and $c$ 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 $$\begin{aligned} x^r - \alpha_1 & = 0 \\ (ax + c)^r - \alpha_2 & = 0 \end{aligned}$$ with the common root $u_0$, and their polynomial GCD will be $x - u_0$.

Unfortunately, we do not have the luxury of dealing with univariate polynomials. Since $a$ and $c$ are unknown in the challenge, we instead have multivariate polynomials with a common root $(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 $$\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 $u$, we can rewrite each nonce as some constant multiple of $c$. It follows that we can rewrite each mask as a constant multiple of $c^{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 $A$, a short secret matrix $S$, and a short error matrix $E$. The private key is $S$, and the public key is $A$ along with $B = 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 = A s + e$. The verifier’s challenge is a short vector $c$, and the server’s response is $r = s - S c$. Finally, the verifier checks that $A r$ is approximately equal to $b - 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' + 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 $S$ by treating $S'$ as an error term. I personally did a least squares optimization, although lattice reduction should also work.