# DiceCTF 2021

February 7, 2021It’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`

.