DiceCTF @ HOPE - small-fortune

This week, our team organized DiceCTF @ HOPE, which was a CTF for the HOPE 2022: A New Hope conference in New York. Special thanks to the organizers of the HOPE conference for giving us this opportunity, it was good fun to organize!

I ended up writing one medium-ish crypto challenge: small-fortune, which ended up getting 20 solves, and was the least solved crypto challenge of the CTF. All challenge files can be found here

I’ve also included a little section at the bottom which goes over my thought process when making this challenge.

challenge

from Crypto.Util.number import *
from gmpy2 import legendre

flag = bytes_to_long(open("flag.txt", "rb").read())

p, q = getPrime(256), getPrime(256)
n = p * q

x = getRandomRange(0, n)
while legendre(x, p) != -1 or legendre(x, q) != -1:
    x = getRandomRange(0, n)

def gm_encrypt(msg, n, x):
    y = getRandomRange(0, n)
    enc = []
    while msg:
        bit = msg & 1
        msg >>= 1
        enc.append((pow(y, 2) * pow(x, bit)) % n)
        y += getRandomRange(1, 2**48)
    return enc

print("n =", n)
print("x =", x)
print("enc =", gm_encrypt(flag, n, x))

The flag is encrypted bit by bit using the Goldwasser-Micali cryptosystem. Notably, the random $y_k$ values are related, with $y_{k+1} - y_{k} < 2^{48}$ for all $k$.

solution

Goldwasser-Micali is a cryptosystem based on the fact that determining whether some value $x$ is a quadratic residue $\bmod$ some composite number $n$, that is, if there exists some value $a$ where $x \equiv a^{2} \bmod n$, is hard without the factorization of $n$.

To begin, we choose $n = pq$, where $p, q$ are large primes. Then, we choose some value $x$ such that it is not a quadratic residue $\bmod n$. The public key is the pair $(n, x)$, while the secret key is the factorization of $n$.

To encrypt a bit $b$, we first generate some random value $y$. The resulting ciphertext $c$ is computed as:

If the bit is a 0, $x^{b} = 1$, therefore $c = y^{2}$, meaning that it is a quadratic residue $\bmod n$. If the bit is a 1, $c = xy^{2}$. Notice that since $x$ is not a quadratic residue $\bmod n$, $c$ is not a quadratic residue $\bmod n$ either.

So, to encrypt a plaintext $P$, we need to divide it into bits $(b_0, b_1, \dots b_k)$, and then encrypt each bit individually to get a list of ciphertexts $(c_0, c_1, \dots c_k)$.

To decrypt a ciphertext, we just need to determine whether each of the $c_k$’s is a quadratic residue $\bmod n$, which is easy knowing the factorization of $n$.

The $y_k$’s used should be random each time, but in this case, they are not: we know that $y_{k+1} - y_k$ (denote this value as $d_k$) is less than $2^{48}$, which is very small compared to the 512 bit $n$. This hints that we can maybe use Coppersmith or lattice based attacks to solve this challenge.

finding $d_0$

The main idea for this challenge is to obtain a polynomial with one of the $d_k$’s as it’s roots. Since this value is very small, we should hopefully be able to use Coppersmith to obtain it.

First, we note that because of the flag format (hope{}), the last character is a }, and so $b_0 = 1, b_1 = 0$.

Then, we write two polynomials:

which both have $y, d_0$ as roots.

Since they have common roots, we should be able to do some rearranging to get rid of $m$, so we are left with a univariate polynomial in $n$ with $d_0$ as its root. Doing this manually is probably too annoying, but we can use resultants to do this for us.

Once we have our polynomial in $n$ with $d_0$ as the root, all we need to do is chuck small_roots() at it, and hopefully we can recover $d_0$.

finding y_0

Now that we have $d_0$, we can rewrite the polynomials above replacing $n$ with $d_0$:

Since both of these polynomials share a common root of $y_0$, they both have a factor of $(m - y_0)$. We can use polynomial-GCD to hopefully obtain this factor and retrieve $y_0$.

finding the rest of the flag

The rest of the flag can be obtained by writing each subsequent $y_k$ as $y_0 + n_k$, where $n_k$ is some small value. Then, we can try finding small roots of the polynomial $f(n) = (y_0 + n)^{2} - c_k$, where if a small root exists, we know the bit is a 1, otherwise it is a 0. We could also check if small roots exist for $f(n) = x(y_0 + n)^{2} - c_k$, to double check the bit is a 0, but I decided not to.

Solve script below.

from Crypto.Util.number import *
from tqdm import tqdm

exec(open('output.txt').read())

def resultant(f1, f2, var):
    return Matrix(f1.sylvester_matrix(f2, var)).determinant()

pgcd = lambda g1, g2: g1.monic() if not g2 else pgcd(g2, g1%g2)

P.<y, k> = PolynomialRing(Zmod(n))
p1 = x * y^2 - enc[0]
p2 = (y + k)^2 - enc[1]
p3 = resultant(p1, p2, y)
k = min(p3.univariate_polynomial().monic().small_roots())

P.<y> = PolynomialRing(Zmod(n))
p1 = x * y^2 - enc[0]
p2 = (y + k)^2 - enc[1]
p4 = pgcd(p1, p2)
y = n - p4.coefficients()[0]

flag = 0
P.<k> = PolynomialRing(Zmod(n))

for c in tqdm(enc[::-1]):
    flag <<= 1
    poly = x * (y+k)^2 - c
    if len(poly.monic().small_roots()):
        flag += 1

print(long_to_bytes(flag))

Flag: hope{r4nd0m_sh0uld_b3_truly_r4nd0m_3v3ry_t1m3_sh0uld_1t_n0t?}

challenge creation

The final version of this challenge is mostly based on the Coppersmith Short-Pad attack, which is an attack used when the difference between two messages is small, due to short padding for example. The attack works similar to the challenge: rewrite the messages as $y, y + d$ and use resultants to eliminate $y$, leaving a polynomial with $d$ as a small root, which can be solved for with Coppersmith. The resulting $y$ can be determined using polynomial-GCD once $d$ is recovered.

Originally, I did not mean for this to be based off the Coppersmith Short-Pad attack, but rather just a challenge that could be solved using polynomial GCD. I chose to do it like this:

def gm_encrypt(msg, n, x):
    y = getRandomRange(0, n)
    enc = []
    while msg:
        bit = msg & 1
        msg >>= 1
        enc.append((pow(y, 2) * pow(x, bit)) % n)
        y += 1
    return enc

Since $d$ is known, this can be solved using polynomial GCD. The issue is that the differences between $y_k^{2}$ values is very close, as:

This means that we can just look at the differences between $c_k$ values and see which differences are very close together, in which case we know the two bits in question are both 0. If we find some differences which are very close, $y$ can be recovered, and then the rest of the flag is also easily recovered too.

In fact, this works even when the added thing is unknown but remains constant, but again has this rather simple solution.

Eventually, I decided to add a small, but bruteforceable value:

def gm_encrypt(msg, n, x):
    y = getRandomRange(0, n)
    enc = []
    while msg:
        bit = msg & 1
        msg >>= 1
        enc.append((pow(y, 2) * pow(x, bit)) % n)
        y += getRandomRange(0, 2**16)
    return enc

which is basically the same as the current version, except instead of finding $d$ by resultants + Coppersmith, you can just bruteforce it and try polynomial GCD for all possible $d$.

Finally, I realised that you don’t actually need to bruteforce $d$, and you can solve for it for Coppersmith. Since I felt this made it a more interesting challenge, I stuck with it, and I’m pretty pleased with how it turned out, as several people commented how they enjoyed the challenge and found it interesting.

If you did enjoy this challenge (and you are reading this shortly after this post comes out), be sure to check out corCTF 2022, where I’ll also be writing some (hopefully fun!) challenges.

Of course, there was one thing I slightly messed up on, which was setting the modulus $n$ to be 512 bits, and it is theoretically possible to use faas for about $100… as shown below:

alternative “solution”

credit to kalmarunion

(no, you were not meant to factor it)