はやぶさ
9 minutos de lectura
Se nos proporciona un script en Python llamado chall.py:
from falcon import falcon
from flag import flag
from timeout_decorator import timeout
@timeout(30)
def main():
sk = falcon.SecretKey(64)
pk = falcon.PublicKey(sk)
print(pk)
your_sig = bytes.fromhex(input("what is your sig? >"))
if pk.verify(b"Can you break me", your_sig):
print("well done!!")
print(flag)
exit()
print("Broken your wing T_T")
main()
Y también tenemos un script de shell llamado up.sh:
git clone https://github.com/tprest/falcon.py.git
mv falcon.py falcon
echo "import os
import sys
sys.path.append(os.path.dirname(__file__))
" > ./falcon/__init__.py
Análisis del código fuente
El script de Python parece muy corto, pero la cosa es que up.sh está clonando un repositorio de GitHub que será utilizado por el script de Python.
De hecho, este repositorio se llama falcon.py (renombrado a falcon para que el import en Python no dé problemas).
Entonces, centrémonos en chall.py. Básicamente, genera una clave secreta de Falcon con n = 64, imprime la clave pública y solicita la firma de un mensaje determinado ("Can you break me"):
@timeout(30)
def main():
sk = falcon.SecretKey(64)
pk = falcon.PublicKey(sk)
print(pk)
your_sig = bytes.fromhex(input("what is your sig? >"))
if pk.verify(b"Can you break me", your_sig):
print("well done!!")
print(flag)
exit()
print("Broken your wing T_T")
En la criptografía de clave pública, se genera una firma utilizando la clave privada, que es desconocida para nosotros. Además, no debería ser posible derivar la clave privada a partir de la clave pública.
Esta vez, necesitamos romper las firmas Falcon, y será posible porque n = 64 es un valor débil. Solo como referencia, Falcon es uno de los candidatos para el Post-Quantum Cryptography Project del NIST, y los parámetros propuestos son n = 512 y n = 1024, que son valores notablemente más altos en comparación con este reto.
Solución
Falcon es un acrónimo que dice Fast-Fourier Lattice-Based Compact signatures over NTRU. Básicamente, una clave privada de NTRU consiste en los polinomios polinomios, $f, g, F, G \in \mathbb{Z}[x]/(x^n + 1)$ tales que, para un valor conocido $q \in \mathbb{Z}^+$,
$$ f \cdot G - g \cdot F = q \mod{(x^n + 1)} $$
Siempre que el polinomio $f$ sea invertible $\mod{q}$, tenemos la clave pública $h = g \cdot f^{-1} \mod{q}$.
En realidad, hay dos formas de resolver el reto. La primera es explotar la verificación de Falcon, que simplemente mira si una firma dada representa un vector corto:
def verify(self, message, signature):
# ...
# Check that the (s0, s1) is short
norm_sign = sum(coef ** 2 for coef in s0)
norm_sign += sum(coef ** 2 for coef in s1)
if norm_sign > self.signature_bound:
print("Squared norm of signature is too large:", norm_sign)
return False
# If all checks are passed, accept
return True
Y el otro ataque es simplemente para recuperar la clave privada, que es lo que hice durante el CTF.
Todos estos ataques se documentan en la Sección 2.5.1 del paper de Falcon. Algunas lecturas adicionales y otros recursos que utilicé al resolver el reto son:
- NTRU and Lattice-Based Crypto: Past, Present, and Future
- Falcon
- Lattice Attacks on NTRU and LWE: A History of Refinements
- NTRU: A Ring-Based Public Key Cryptosystem
- LatticeHacks: NTRU
Ataque de recuperación de clave
Intentaremos encontrar los polinomios $f$ y $g$ a partir del polinomio público $h$, sabiendo que $h = g \cdot f^{-1} \mod{q}$ y que ambos polinomios son cortos.
Usando el retículo NTRU (que se muestra en los recursos anteriores), podemos ver cómo $[f \quad g]$ pertenece al retículo:
$$ \begin{bmatrix} f & k \end{bmatrix} \cdot \begin{bmatrix} 1 & h \\ 0 & q \end{bmatrix} = \begin{bmatrix} f & h \cdot f + k \cdot q \end{bmatrix} = \begin{bmatrix} f & g \end{bmatrix} \mod{q} $$
Como resultado, si reducimos la base del retículo, probablemente podamos encontrar $f$ y $g$. En lugar de usar el algoritmo LLL, esta vez es mejor usar BKZ. Una vez que tengamos $f$ y $g$, podemos obtener fácilmente $F$ y $G$ a partir de $f$ y $g$ llamando a ntru_solve, como se muestra en la rutina de generación de NTRU:
def ntru_gen(n):
"""
Implement the algorithm 5 (NTRUGen) of Falcon's documentation.
At the end of the function, polynomials f, g, F, G in Z[x]/(x ** n + 1)
are output, which verify f * G - g * F = q mod (x ** n + 1).
"""
while True:
f = gen_poly(n)
g = gen_poly(n)
if gs_norm(f, g, q) > (1.17 ** 2) * q:
continue
f_ntt = ntt(f)
if any((elem == 0) for elem in f_ntt):
continue
try:
F, G = ntru_solve(f, g)
F = [int(coef) for coef in F]
G = [int(coef) for coef in G]
return f, g, F, G
# If the NTRU equation cannot be solved, a ValueError is raised
# In this case, we start again
except ValueError:
continue
Una cosa más a tener en cuenta es que la matriz del retículo NTRU está hecho de polinomios… pero obviamente, necesitamos transformarlo en una matriz con entradas enteras. Esto es fácil porque los polinomios se reducen $\mod{(x^n + 1)}$:
$ sage -q
sage: q = 12 * 1024 + 1
sage: n = 64
sage:
sage: P.<x> = PolynomialRing(Zmod(q))
sage: R = P.quotient(x ** n + 1)
sage:
sage: h_list = [7061, 5175, 9682, 7463, 11079, 3335, 2591, 5148, 4725, 1259, 7346, 3475, 2439, 8779, 2044, 11172, 7201, 8788, 12088, 9521, 11405, 2202, 4573,
....: 6362, 5585, 11674, 8189, 3777, 1870, 9742, 8067, 6636, 5089, 5700, 5686, 9359, 444, 11142, 1927, 382, 6753, 7527, 11940, 7481, 8169, 10312, 5940, 8709,
....: 6940, 7771, 810, 8596, 9070, 1920, 1970, 3412, 1744, 4082, 10049, 3390, 6266, 11869, 8941, 10025]
sage:
sage: h = R(h_list)
sage: h
10025*xbar^63 + 8941*xbar^62 + 11869*xbar^61 + 6266*xbar^60 + 3390*xbar^59 + 10049*xbar^58 + 4082*xbar^57 + 1744*xbar^56 + 3412*xbar^55 + 1970*xbar^54 + 1920*xbar^53 + 9070*xbar^52 + 8596*xbar^51 + 810*xbar^50 + 7771*xbar^49 + 6940*xbar^48 + 8709*xbar^47 + 5940*xbar^46 + 10312*xbar^45 + 8169*xbar^44 + 7481*xbar^43 + 11940*xbar^42 + 7527*xbar^41 + 6753*xbar^40 + 382*xbar^39 + 1927*xbar^38 + 11142*xbar^37 + 444*xbar^36 + 9359*xbar^35 + 5686*xbar^34 + 5700*xbar^33 + 5089*xbar^32 + 6636*xbar^31 + 8067*xbar^30 + 9742*xbar^29 + 1870*xbar^28 + 3777*xbar^27 + 8189*xbar^26 + 11674*xbar^25 + 5585*xbar^24 + 6362*xbar^23 + 4573*xbar^22 + 2202*xbar^21 + 11405*xbar^20 + 9521*xbar^19 + 12088*xbar^18 + 8788*xbar^17 + 7201*xbar^16 + 11172*xbar^15 + 2044*xbar^14 + 8779*xbar^13 + 2439*xbar^12 + 3475*xbar^11 + 7346*xbar^10 + 1259*xbar^9 + 4725*xbar^8 + 5148*xbar^7 + 2591*xbar^6 + 3335*xbar^5 + 11079*xbar^4 + 7463*xbar^3 + 9682*xbar^2 + 5175*xbar + 7061
sage: h * x
8941*xbar^63 + 11869*xbar^62 + 6266*xbar^61 + 3390*xbar^60 + 10049*xbar^59 + 4082*xbar^58 + 1744*xbar^57 + 3412*xbar^56 + 1970*xbar^55 + 1920*xbar^54 + 9070*xbar^53 + 8596*xbar^52 + 810*xbar^51 + 7771*xbar^50 + 6940*xbar^49 + 8709*xbar^48 + 5940*xbar^47 + 10312*xbar^46 + 8169*xbar^45 + 7481*xbar^44 + 11940*xbar^43 + 7527*xbar^42 + 6753*xbar^41 + 382*xbar^40 + 1927*xbar^39 + 11142*xbar^38 + 444*xbar^37 + 9359*xbar^36 + 5686*xbar^35 + 5700*xbar^34 + 5089*xbar^33 + 6636*xbar^32 + 8067*xbar^31 + 9742*xbar^30 + 1870*xbar^29 + 3777*xbar^28 + 8189*xbar^27 + 11674*xbar^26 + 5585*xbar^25 + 6362*xbar^24 + 4573*xbar^23 + 2202*xbar^22 + 11405*xbar^21 + 9521*xbar^20 + 12088*xbar^19 + 8788*xbar^18 + 7201*xbar^17 + 11172*xbar^16 + 2044*xbar^15 + 8779*xbar^14 + 2439*xbar^13 + 3475*xbar^12 + 7346*xbar^11 + 1259*xbar^10 + 4725*xbar^9 + 5148*xbar^8 + 2591*xbar^7 + 3335*xbar^6 + 11079*xbar^5 + 7463*xbar^4 + 9682*xbar^3 + 5175*xbar^2 + 7061*xbar + 2264
sage: h * x ** 2
11869*xbar^63 + 6266*xbar^62 + 3390*xbar^61 + 10049*xbar^60 + 4082*xbar^59 + 1744*xbar^58 + 3412*xbar^57 + 1970*xbar^56 + 1920*xbar^55 + 9070*xbar^54 + 8596*xbar^53 + 810*xbar^52 + 7771*xbar^51 + 6940*xbar^50 + 8709*xbar^49 + 5940*xbar^48 + 10312*xbar^47 + 8169*xbar^46 + 7481*xbar^45 + 11940*xbar^44 + 7527*xbar^43 + 6753*xbar^42 + 382*xbar^41 + 1927*xbar^40 + 11142*xbar^39 + 444*xbar^38 + 9359*xbar^37 + 5686*xbar^36 + 5700*xbar^35 + 5089*xbar^34 + 6636*xbar^33 + 8067*xbar^32 + 9742*xbar^31 + 1870*xbar^30 + 3777*xbar^29 + 8189*xbar^28 + 11674*xbar^27 + 5585*xbar^26 + 6362*xbar^25 + 4573*xbar^24 + 2202*xbar^23 + 11405*xbar^22 + 9521*xbar^21 + 12088*xbar^20 + 8788*xbar^19 + 7201*xbar^18 + 11172*xbar^17 + 2044*xbar^16 + 8779*xbar^15 + 2439*xbar^14 + 3475*xbar^13 + 7346*xbar^12 + 1259*xbar^11 + 4725*xbar^10 + 5148*xbar^9 + 2591*xbar^8 + 3335*xbar^7 + 11079*xbar^6 + 7463*xbar^5 + 9682*xbar^4 + 5175*xbar^3 + 7061*xbar^2 + 2264*xbar + 3348
sage:
sage: (h * x ** 3).list() == (-h).list()[-3:] + h.list()[:-3]
True
El tema es que sumar polinomios en $\mod{(x^n + 1)}$ y $\mod{q}$ es solo agregar cada coeficiente del término de grado correspondiente.Y multiplicar por $x$ simplemente desplaza los coeficientes del polinomio, poniendo el coeficiente de grado más alto en la posición más baja con signo negativa.
Como resultado, dado que la reducción del retículo solo realiza combinaciones lineales enteras de filas, podemos transformar el polinomio $h$ en una matriz de bloque de $n \times n$, de modo que el retículo NTRU sea equivalente a:
$$ \begin{bmatrix} 1 & h \\ 0 & q \end{bmatrix} \equiv \left[ \begin{array}{cccc|cccc} 1 & & & & h_0 & h_1 & \dots & h_{n - 1} \\ & 1 & & & h_{n - 1} & h_0 & \dots & h_{n - 2} \\ & & \ddots & & \vdots & \vdots & \ddots & \vdots \\ & & & 1 & h_1 & h_2 & \dots & h_0 \\ \hline & & & & q & & & \\ & & & & & q & & \\ & & & & & & \ddots & \\ & & & & & & & q \\ \end{array} \right] $$
Donde
$$ h(x) = h_0 + h_1 \cdot x + h_2 \cdot x^2 + \dots + h_{n - 1} \cdot x^{n - 1} $$
Implementación
Una vez que tenemos esto, solo necesitamos tomar los coeficientes del polinomio $h$:
q = 12 * 1024 + 1
n = 64
P = PolynomialRing(Zmod(q), names='x')
x = P.gens()[0]
R = P.quotient(x ** n + 1)
io = get_process()
io.recvuntil(b'h = ').decode()
h = R(literal_eval(io.recvlineS()))
Luego, construimos la matriz:
M = Matrix(ZZ, 2 * n, 2 * n)
M[:n, :n] = identity_matrix(ZZ, n)
M[n:, n:] = q * identity_matrix(ZZ, n)
M[:n, n:] = Matrix(ZZ, [(h * R([0] * i + [1])).list() for i in range(n)])
Ahora, estamos listos para reducir el retículo usando BKZ (algunos ajustes de block_size pueden ser necesarios, 32 funciona bien). La primera fila contendrá los coeficientes de $f$ y de $g$:
L = M.BKZ(block_size=n // 2)
row = L[0]
A continuación, necesitamos encontrar $F$ y $G$. Para esto, usaremos ntru_solve de la librería Falcon. Sin embargo, necesitamos transformar los coeficientes de $f$ y $g$ para que estén centrados, es decir: $f_i, g_j \in [\frac{- q + 1}{2}, \frac{q - 1}{2}]$ en lugar de $f_i, g_j \in [0, q - 1]$, que se puede hacer con lift_centered en SageMath:
center = lambda x: int(Mod(x, q).lift_centered())
f, g = R(list(row[:n])), R(list(row[n:]))
assert h == g * f.inverse()
f_list = list(map(center, f.list()))
g_list = list(map(center, g.list()))
F_list, G_list = ntru_solve(f_list, g_list)
F, G = R(F_list), R(G_list)
assert f * G - g * F == 0
En este punto, estamos listos para obtener la clave secreta y firmar el mensaje para obtener la flag:
sk = falcon.SecretKey(n, polys=(f_list, g_list, F_list, G_list))
sig = sk.sign(b'Can you break me')
io.sendlineafter(b'what is your sig? >', sig.hex().encode())
io.recvuntil(b'well done!!\n')
io.success(io.recvlineS())
Flag
Si ejecutamos el script, obtendremos la flag:
$ python3 solve.py hayabusa.chals.sekai.team 1337
[+] Opening connection to hayabusa.chals.sekai.team on port 1337: Done
[+] b'SEKAI{1_l1k3_7h15_mu51c_h0w_4b0u7_y0u_:https://www.youtube.com/watch?v=uUvthLpSHrQ}'
[*] Closed connection to hayabusa.chals.sekai.team port 1337
El script completo se puede encontrar aquí: solve.py.