はやぶさ

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 unos 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:

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á hecha de polinomios… pero obviamente, necesitamos transformarlo en una matriz con números enteros. Esto es fácil porque los polinomios se reducen en $\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$ es simplemente desplazar los coeficientes del polinomio, poniendo el coeficiente de grado más alto en la posición más baja con signo negativo.

Como resultado, dado que la reducción del retículo solo realiza combinaciones lineales enteras con las filas, podemos transformar el polinomio $h$ en una matriz 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.