Challenge analysis
We are given a custom signature scheme and want to retrieve the secret key in order to make new signatures.
From the given source code of the scheme, here is how it approximately works :
- Parameters : a prime $Q$, a bound $B$ and a size $N$
- Setup : Choose $a(x)$, a uniformly generated polynomial of degree $N - 1$ over $\mathbb{F}_Q[X]$. Generate two random polynomials $s_1, s_2$ of degree $N - 1$ where all the coefficients are in the set $\lbrace -1, 0, 1\rbrace$. Output $(a, t := a * s_1 + s_2)$ the public key, keep $s_1, s_2$ secret.
- Sign : generate two random polynomials $(y_1, y_2)$ of degree $N - 1$ with all coefficients between $-B$ and $B$, do some computations with the hash of the message to obtain $c \in \mathbb{F}_Q[X]$. Then output $(y_1, z_1 := s_1 * c + y_1, z_2 := s_2 * c + y_2, c)$
There is no need to understand how to verify a message to solve the challenge. Finaly the coefficients of $s_1$ and $s_2$ are hashed to generate an AES key under which the flag will be encrypted.
Solve
To retrieve the flag, we have to retrieve the key, which implies to retrieve $s_1$ and $s_2$. To do that, we have ~500 signatures.
However, a single one is all we need ! If you look at the output of the signing algorithm, you can retrieve $s_1$ for free : $s_1 = \frac{z_1 - y_1}{c}$.
Then, one may use the fact that we have ~500 signatures to generate a system of equations to retrieve $s_2$… or just figure out that we have the public key where $t = a * s_1 + s_2$ ! Because we now have $s_1$ then one can easily compute $s_2 = t - a * s_1$.
Note that we are working in the quotient ring : $\mathbb{F}_Q[X]/X^{N} + 1$ where $N = 512$ here. We can decude that from the poly_mul function from the source code :
def poly_mul(self, p1,p2):
res = np.convolve(p1, p2)
res = [0] * (2 * self.N - 1 - len(res)) + list(res)
a = list(map(int, res[:self.N]))
b = list(map(int, res[self.N:] + [0]))
res = self.poly_sub(a, b)
return res
The first line of the function is “classical” polynomial multiplication. But then the second to fifth lines are reducing the obtained polynomial modulo $X^512 + 1$.
Here is the sage code of the solve :
# Load the parameters of the scheme
from gaston import Q, N
# Load the public key, the signatures and the encrypted flag
with open("output.txt") as f:
lines = f.readlines()
parameters = eval(lines[0])
signatures = eval(lines[1])
ct = eval(lines[2])
# Define the finite field, and the ring
F = GF(Q)
R.<x> = PolynomialRing(F)
# M is the modulus polynomial we are working with
M = x^N + 1
# Load the public parameters
a = load_poly(F, x, parameters["a"])
t = load_poly(F, x, parameters["t"])
# Load one signature
y1 = load_poly(F, x, signatures[0]["y1"])
z1 = load_poly(F, x, signatures[0]["z1"])
z2 = load_poly(F, x, signatures[0]["z2"])
c = load_poly(F, x, signatures[0]["c"])
# Retrieve s_1 and s_2 :
s1 = ((z1 - y1) * c.inverse_mod(x^N + 1)).mod(M)
s2 = (t - a * s1).mod(M)
# Derive the key and decrypt the ciphertext
import hashlib
from Crypto.Cipher import AES
# /!\ use sparse=False, otherwise you'll miss some coefficients
coeff = str(list(s1.coefficients(sparse=False))) + str(list(s2.coefficients(sparse=False)))
key = hashlib.sha256(coeff.encode()).digest()
cipher = AES.new(key, AES.MODE_CBC, iv=bytes.fromhex(ct["iv"]))
cipher.decrypt(bytes.fromhex(ct["enc"]))
# FCSC{c3b929519b28954612bf81af628dd93b6adef1e79539887729e1a2a27569eeb0}