<- ECSC 2023

Irish Flan

6 minutes to read

Yum, time for dessert.

Challenge contributed by CryptoHack

Challenge files:

We are given a Python script that uses quaternions to hide an AES key used to encrypt the flag. The quaternion implementation is based on Python classes. We can assume that the implementation is correct (although there is a bug in the power of a quaternion, but it is not intended).

Source code analysis

The relevant part of the script is:

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()))))

The Dessert class defines a public modulus $n$ (a product of two unknown prime numbers), a random integer $r$, a secret quaternion $\chi$ (random) and three public quaternions $\alpha$ (random), $\beta$, and $\gamma$. Actually, $\beta$, and $\gamma$ satisfy these relations:

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

In order to encrypt, the script takes a random quaternion $k$ and uses it to derive an AES key. Then, that $k$ value is hidden on the following quaternion operations:

$$ \delta = \gamma^s $$

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

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

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

Solution

From the above values, we are given $\varepsilon$ and $\mu$.

  • Our objective is to find $k$, which only appears in $\mu = \kappa \cdot k \cdot \kappa$. So we need to find $\kappa$.
  • And to find $\kappa$, we need to find $\delta$, because there is a relation $\kappa = \delta^{-1} \cdot \beta \cdot \delta$.
  • And we can probably find $\delta$ from $\varepsilon = \delta^{-1} \cdot \alpha \cdot \delta$ and $\delta = \gamma^s$, although we don’t know the exponent $s$.

We may think that $\delta$ can be easily found from $\varepsilon = \delta^{-1} \cdot \alpha \cdot \delta$, because we know both $\alpha$ and $\varepsilon$. We can express the relation as

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

One approach is to use a symbolic quaternion:

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

And try to solve for $(a, b, c, d)$. In SageMath, the above approach might give some errors (or just output $\delta = 0$).

An alternative approach is using the matrix form of the quaterions (let’s say lowercase greek letters denote quaternions and uppercase greek letters denote matrix forms), which is an equivalent procedure:

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

And $\Delta$ is a symbolic $4 \times 4$ matrix:

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

Now, this equation gives us $16$ conditions that $a$, $b$, $c$ and $d$ must satisfy. Since all conditions are linear, we can express them as:

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

If we try to solve this with SageMath, we will get the trivial solution $a = b = c = d = 0$. However, there are more solutions (we know that $\delta \ne 0$ because it is invertible). Therefore, there must be linearly dependent conditions in $C$.

For some reason, SageMath complains when trying to find the rank of $C$ (which is less than $4$, for sure). We know this because there must be a non-trivial solution. As a result, we know that this solution is inside $\ker{C}$. This is a subspace of vectors that are mapped to zero when multiplied by $C$ from the right.

If we use C.right_kernel_matrix() in SageMath, we will see that the basis of $\ker{C}$ contains two vectors (let’s say $\delta_x$ and $\delta_y$), which means that

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

for some integers $x$ and $y$. Equivalently, $\delta$ is a linear combination of the vectors of $\ker{C}$, since $\delta$’s coefficients (as vector) belong to $\ker{C}$.

At this point, if we set whatever value in $x$ and $y$ (except for $x = y = 0$), the relation $\varepsilon = \delta^{-1} \cdot \alpha \cdot \delta$ holds.

However, $\kappa = \delta^{-1} \cdot \beta \cdot \delta$ does not hold. I noticed this when doing some tests and comparing the value I got for $\kappa$ and the expected one. It looks like having two degrees of freedom for $\delta$’s coefficients is not good.

At this point, we can use the other relation: $\delta = \gamma^s$. I remember from RSA 4.0 in SECCON Quals CTF 2023 that quaternion powers have a certain structure (more information here). So, given a quaternion $\varphi = a + b \;\mathrm{i} + c \;\mathrm{j} + d \;\mathrm{k}$, in order to compute $\varphi^m$, we need some values:

$$ 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 $$

And then,

$$ \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} $$

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

Something noticeable is that $(\mathrm{i}, \mathrm{j}, \mathrm{k})$ coordinates of the quaternion $\varphi$ get scaled by a certain number $X$ when raised to a power.

Using the fact that $\delta = \gamma^s$ and $\delta = x \cdot \delta_x + y \cdot \delta_y$, we can define another variable $X$ and use three equations (one for each of $(\mathrm{i}, \mathrm{j}, \mathrm{k})$). As a result, we end up with another set of linear equations on $x$, $y$, $X$, which can be expressed as:

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

This time, $\dim{\left(\ker{M}\right)} = 1$, which means that there is a single vector in the basis of $\ker{M}$, let’s call it $\vec{v}$. Therefore, all values $(x, y, X)$ that satisfy the above equations (and thus the conditions) are proportional to $\vec{v}$.

But even more, we don’t care about the value of $X$, so we have some values $x_0$, $y_0$ such that

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

And the actual $\delta$ is $\delta = z \cdot \delta_0$ for some integer $z$.

But $\delta_0$ is enough to solve the challenge, because now $\kappa = \delta_0^{-1} \cdot \beta \cdot \delta_0$ is the expected $\kappa$. This happens because we have one degree of freedom, so

$$ \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 $$

Finally, we only need $k = \kappa^{-1} \cdot \mu \cdot \kappa^{-1}$ and we are done.

Flag

After implementing all the required operations, we end up finding the flag:

$ python3 solve.py
ECSC{3qu1v4l3nt_k3y_rec0very_988b09742b}

The full script can be found in here: solve.py.