# DiceCTF 2021

February 07, 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`.