DiceCTF 2021

It’s been a while since I wrote challenges for a CTF! Solution code here.

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) - each one being encrypted separately.

I’ll refer to the u-values as nonces, since they’re used to randomize ciphertexts. In particular, each y^m is multiplied by u^r, which I’ll refer to as the mask. The challenge’s vulnerability is that nonces aren’t randomly chosen. Rather, each successive nonce is generated via LCG: u, au+c, a(au+c)+c, etc.

The first insight is that we can extract some information from the encrypted flag thanks to the flag format. If we already know the nibble m associated with a ciphertext, we can divide by y^m to get the corresponding mask. For simplicity, let’s just consider the first 5 bytes of the flag: dice{. Two nibbles per byte gives 10 masks total: k1, k2, k3, etc.

Let’s take a step back and reformulate our goal. We have an initial sequence of masks generated from the unknown values u, a, and c. Our goal is to predict future masks. Then, we divide each ciphertext by its corresponding mask to obtain y raised to the power of m, which is only between 0 and 15. Decryption then proceeds as described on the Wikipedia page.

To motivate the final solution, let’s consider the scenario where a and c are actually public parameters. In that case, the setup is identical to that of the Franklin-Reiter related message attack for RSA. We can construct two univariate polynomials that have the common root u:

     x^r - k1 == 0 mod n
(ax+c)^r - k2 == 0 mod n

Taking their polynomial GCD hopefully gives the polynomial x-u with root u.

Another possibility is to expand each polynomial into a sum of r+1 terms by the binomial theorem. If we gather r+1 such equations, we can imagine them as a linear system where each monomial is an independent unknown. This might also be appealing when c is unknown.

But in any case, we don’t have enough masks to do that. Things fall apart further when a is unknown, since each successive polynomial increases in term count.

What we need is a better mathematical tool which combines these ideas: Gröbner basis reduction! Informally, this process takes a set of multivariate polynomials and outputs another set in a reduced form (the Gröbner basis). It might be more conducive to finding roots, such as the example with x-u above. It also preserves some key properties about the original set - in our case we care that roots remain the same.

So, let’s take a couple of these polynomials and compute their Gröbner basis. We get something like this:

c^17 + 134...154
u + 316...980*c
a + 166...006

Notice that implies a solution for a and c^17 and relates u with c by a multiplicative factor. This turns out to be sufficient for generating masks, since we can now represent each nonce as some multiple of c. Hence each mask is some multiple of c^17, which we have!

signature sheep scheming signature schemes

I’m not going to explain what’s going on conceptually in the challenge, since it’s not too important for solving the challenge. Also, I don’t have enough time before the CTF ends :(

We have r = s - Sc. If we collect r, c samples from a bunch of signatures we can build the matrix equation R = S' - SC. In particular, notice that both S and C are generated from a Gaussian with small variance. Since each entry is small, their matrix multiplication is never wraps around the modulus (besides dipping into negatives). Same goes for adding S' which is also a short matrix. Thus we can lift this matrix equation into the integers.

From here, the solution I came up with is to notice that R = S' - SC approximates R = SC, since S' is small. Thus we can use least squares regression to find S.