Irish Flan

Yum, time for dessert.

Challenge contributed by CryptoHack

Challenge files:

• output.txt
• irish_flan.py

Se nos proporciona un script en Python que usa cuaterniones para ocultar una clave AES utilizada para cifrar la flag. La implementación de los cuaterniones se basa en clases de Python. Podemos suponer que la implementación es correcta (aunque hay un error en la potencia de un cuaternión, pero no es intencionado).

Análisis del código fuente

La parte relevante del script es:

class Dessert:
    def __init__(self):
        self.n = getPrime(1024) * getPrime(1024)
        self.R = Z(self.n)
        r = secrets.randbelow(self.n**8)
        self.χ = Q(*[self.R(secrets.randbelow(self.n)) for _ in "abcd"])  
        self.α = Q(*[self.R(secrets.randbelow(self.n)) for _ in "abcd"])
        self.β = self.χ**-1 * self.α**-1 * self.χ
        self.γ = self.χ**r

    @property
    def pub(self):
        return (self.n,
                self.α,
                self.β,
                self.γ)

    def encrypt(self, m):
        k = Q(*[self.R(secrets.randbelow(self.n)) for _ in "abcd"])
        K = hashlib.sha256(str(k).encode()).digest()
        c = AES.new(K, AES.MODE_CBC, iv=b"\0" * 16).encrypt(pad(m, 16))
        s = secrets.randbelow(self.n**8)
        δ = self.γ**s
        ε = δ**-1 * self.α * δ
        κ = δ**-1 * self.β * δ
        μ = κ * k * κ
        return (c, μ, ε)


if __name__ == "__main__":
    flan = Dessert()
    print("Public key:", ",".join(map(str, flan.pub)))
    with open("flag.txt") as f:
        print("Encryption:", ",".join(
              map(str, flan.encrypt(f.read().strip().encode()))))

La clase Dessert define un módulo público $n$ (un producto de dos números primos desconocidos), un entero aleatorio $r$, un cuaternión secreto $\chi$ (aleatorio) y tres cuaterniones públicos $\alpha$ (aleatorio), $\beta$, y $\gamma$. Además, $\beta$, y $\gamma$ satisfacen estas relaciones:

$$ \beta = \chi^{-1} \cdot \alpha^{-1} \cdot \chi \qquad \gamma = \chi^r $$

Para cifrar, el script toma un cuaternión aleatorio $k$ y lo usa para derivar una clave de AES. Entonces, ese valor de $k$ está oculto en las siguientes operaciones entre cuaterniones:

$$ \delta = \gamma^s $$

$$ \varepsilon = \delta^{-1} \cdot \alpha \cdot \delta $$

$$ \kappa = \delta^{-1} \cdot \beta \cdot \delta $$

$$ \mu = \kappa \cdot k \cdot \kappa $$

Solución

De los valores anteriores, se nos proporcionan $\varepsilon$ y $\mu$.

• Nuestro objetivo es encontrar $k$, que solo aparece en $\mu = \kappa \cdot k \cdot \kappa$. Entonces necesitamos hallar $\kappa$.
• Y para hallar $\kappa$, tenemos que tener $\delta$, porque $\kappa = \delta^{-1} \cdot \beta \cdot \delta$.
• Y probablemente podremos encontrar $\delta$ a partir de $\varepsilon = \delta^{-1} \cdot \alpha \cdot \delta$ y $\delta = \gamma^s$, aunque no sabemos el exponente $s$.

Podemos pensar que $\delta$ se puede encontrar fácilmente de $\varepsilon = \delta^{-1} \cdot \alpha \cdot \delta$, porque sabemos tanto $\alpha$ como $\varepsilon$. Podemos expresar la relación como

$$ \delta \cdot \varepsilon - \alpha \cdot \delta = 0 $$

Un enfoque es usar un cuaternión simbólico:

$$ \delta = a + b \;\mathrm{i} + c \;\mathrm{j} + d \;\mathrm{k} \pmod{n} $$

E intentar resolver para $(a, b, c, d)$. En SageMath, el enfoque anterior puede dar errores (o simplemente devolver $\delta = 0$).

Un enfoque alternativo es utilizar la forma matricial de los cuateriones (digamos que las letras griegas en minúsculas denotan cuaterniones y las letras griegas mayúsculas denotan formas matriciales), que es un procedimiento equivalente:

$$ \Delta \cdot E - A \cdot \Delta = 0 $$

Y $\Delta$ es una matriz simbólica de $4 \times 4$:

$$ \Delta = \begin{pmatrix} a & b & c & d \\ -b & a & -d & c \\ -c & d & a & -b \\ -d & -c & b & a \end{pmatrix} \pmod{n} $$

Ahora, la ecuación nos da $16$ condiciones que deben cumplir $a$, $b$, $c$ y $d$. Como todas las condiciones son lineales, podemos expresarlas como:

$$ C \cdot \begin{pmatrix} a \\ b \\ c \\ d \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} $$

Si intentamos resolver esto con SageMath, obtendremos la solución trivial $a = b = c = d = 0$. Sin embargo, hay más soluciones (sabemos que $\delta \ne 0$ porque es invertible). Por lo tanto, debe haber condiciones linealmente dependientes en $C$.

Por alguna razón, SageMath no permite calcular el rango de $C$ (que es menor que $4$, seguro). Sabemos esto porque debe haber una solución no trivial. Como resultado, sabemos que esta solución está dentro $\ker{C}$. Este es un subespacio de vectores que se mapean al vector nulo cuando se multiplican por $C$ por la derecha.

Si usamos C.right_kernel_matrix() en SageMath, veremos que la base del $\ker{C}$ contiene dos vectores (digamos $\delta_x$ y $\delta_y$), que implica que

$$ \delta = x \cdot \delta_x + y \cdot \delta_y $$

para ciertos enteros $x$ y $y$. De manera equivalente, $\delta$ es una combinación lineal de los vectores de $\ker{C}$, ya que los coeficientes de $\delta$ (como vector) pertenecen a $\ker{C}$.

En este punto, si establecemos cualquier valor en $x$ y en $y$ (excepto $x = y = 0$), la relación $\varepsilon = \delta^{-1} \cdot \alpha \cdot \delta$ se cumple.

Sin embargo, $\kappa = \delta^{-1} \cdot \beta \cdot \delta$ no se sostiene. Me di cuenta de esto al hacer algunas pruebas y comparar el valor que obtuve de $\kappa$ y el esperado. Parece que tener dos grados de libertad para los coeficientes de $\delta$’s no es bueno.

En este punto, podemos usar la otra relación: $\delta = \gamma^s$. Aquí recordé del reto RSA 4.0 de SECCON Quals CTF 2023 que la potencia de un cuaternión tiene una cierta estructura (más información aquí). Entonces, dado un cuaternión $\varphi = a + b \;\mathrm{i} + c \;\mathrm{j} + d \;\mathrm{k}$, para calcular $\varphi^m$, Necesitamos algunos valores:

$$ S = -(b^2 + c^2 + d^2) $$

$$ X = \sum_{i = 0}^{\lfloor\frac{m - 1}{2}\rfloor} {m \choose m - 2i - 1} \cdot a^{m - 2i - 1} S^i $$

Y luego,

$$ \begin{cases} a_m = \displaystyle\sum_{i = 0}^{\lfloor\frac{m}{2}\rfloor} {m \choose m - 2i} \cdot a^{m - 2i} S^i \\ b_m = b X \\ c_m = c X \\ d_m = d X \end{cases} $$

Así, $\varphi^m = a_m + b_m \;\mathrm{i} + c_m \;\mathrm{j} + d_m \;\mathrm{k}$.

Algo notable es que las coordenadas $(\mathrm{i}, \mathrm{j}, \mathrm{k})$ del cuaternión $\varphi$ se escalan por un cierto número $X$ al elevarse a un exponente.

Usando el hecho de que $\delta = \gamma^s$ y $\delta = x \cdot \delta_x + y \cdot \delta_y$, podemos definir otra variable $x$ y usar tres ecuaciones (una para cada $(\mathrm{i}, \mathrm{j}, \mathrm{k})$). Como resultado, terminamos con otro conjunto de ecuaciones lineales en $x$, $y$, $X$, que se puede expresar como:

$$ M \cdot \begin{pmatrix} x \\ y \\ X \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} $$

Esta vez, $\dim{\left(\ker{M}\right)} = 1$, lo cual significa que hay un solo vector en la base del $\ker{M}$, llamémoslo $\vec{v}$. Por consiguiente, todos los valores $(x, y, X)$ que satisfacen las ecuaciones anteriores (y, por lo tanto, las condiciones) son proporcionales a $\vec{v}$.

Pero aún más, no nos importa el valor de $X$, por lo que tenemos algunos valores $x_0$, $y_0$ tales que

$$ \delta_0 = x_0 \cdot \delta_x + y_0 \cdot \delta_y $$

Y el $\delta$ real es $\delta = z \cdot \delta_0$ para un cierto entero $z$.

Pero $\delta_0$ es suficiente para resolver el reto, porque ahora $\kappa = \delta_0^{-1} \cdot \beta \cdot \delta_0$ es el $\kappa$ esperado. Esto sucede porque solo tenemos un grado de libertad, así que

$$ \delta^{-1} \cdot \beta \cdot \delta = (z \cdot \delta_0)^{-1} \cdot \beta \cdot (z \cdot \delta_0) = \delta_0^{-1} \cdot \beta \cdot \delta_0 $$

Finalmente, solo necesitamos hallar $k = \kappa^{-1} \cdot \mu \cdot \kappa^{-1}$ y habremos terminado.

Flag

Después de implementar todas las operaciones requeridas, terminamos encontrando la flag:

$ python3 solve.py
ECSC{3qu1v4l3nt_k3y_rec0very_988b09742b}  

El script completo se puede encontrar aquí: solve.py.