Irish Flan

Yum, time for dessert.

Challenge contributed by CryptoHack

Challenge files:

• output.txt
• irish_flan.py

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 (a product of two unknown prime numbers), a random integer , a secret quaternion (random) and three public quaternions (random), , and . Actually, , and satisfy these relations:

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

Solution

From the above values, we are given and .

• Our objective is to find , which only appears in . So we need to find .
• And to find , we need to find , because there is a relation .
• And we can probably find from and , although we don’t know the exponent .

We may think that can be easily found from , because we know both and . We can express the relation as

One approach is to use a symbolic quaternion:

And try to solve for . In SageMath, the above approach might give some errors (or just output ).

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:

And is a symbolic matrix:

Now, this equation gives us conditions that , , and must satisfy. Since all conditions are linear, we can express them as:

If we try to solve this with SageMath, we will get the trivial solution . However, there are more solutions (we know that because it is invertible). Therefore, there must be linearly dependent conditions in .

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

If we use C.right_kernel_matrix() in SageMath, we will see that the basis of contains two vectors (let’s say and ), which means that

for some integers and . Equivalently, is a linear combination of the vectors of , since ’s coefficients (as vector) belong to .

At this point, if we set whatever value in and (except for ), the relation holds.

However, does not hold. I noticed this when doing some tests and comparing the value I got for and the expected one. It looks like having two degrees of freedom for ’s coefficients is not good.

At this point, we can use the other relation: . 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 , in order to compute , we need some values:

And then,

So, .

Something noticeable is that coordinates of the quaternion get scaled by a certain number when raised to a power.

Using the fact that and , we can define another variable and use three equations (one for each of ). As a result, we end up with another set of linear equations on , , , which can be expressed as:

This time, , which means that there is a single vector in the basis of , let’s call it . Therefore, all values that satisfy the above equations (and thus the conditions) are proportional to .

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

And the actual is for some integer .

But is enough to solve the challenge, because now is the expected . This happens because we have one degree of freedom, so

Finally, we only need 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.