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
.