This is a writeup of the solution to the CRYPTO challenge of the m0leCon 2021 Finals.

⚠️ Code blocks need to be executed in a Sage environment. They won't work with the vanilla Python interpreter.

Challenge

I took years to generate this ciphertext, how fast will you decrypt it?

Flag format: ptm{...}

Note: this challenge was released as a "speedrun" in the original CTF (first solvers get more points). The first correct solution was submitted after 8 minutes.

Author: @Drago_1729

Attached with the problem description is its source code: slooow.zip:

• chall.py containing the Python source code of an encryption function
• output.txt containing the encrypted flag

Preliminary observations

chall.py

p = (1 << 255) - 19

Declared at the top is p, a prime number.

def encrypt(flag):
    res = []
    for i, c in enumerate(flag):
        val = f(10**(20+i))
        mask = int.from_bytes(sha256(str(val)).digest(), "big")
        num = int.from_bytes(sha256(c.encode()).digest(), "big")
        res.append((mask*num) % p)
    return res

Next, we can see the encryption algorithm. For every letter of the plaintext, identified by the index $i$, it computes a value val using function f with argument $10^{20 + i}$. That value and the character are hashed separately and then multiplied together modulo p. The result is appended into an array and returned.

def f(n):
    res = 5
    for _ in range(n):
        res = (res**2-2) % p
    return res

Taking a closer look at function f we can see that the function $x_n = x_{n - 1}^2 - 2 \ \text{mod} \ p$ (where $x_0 = 5$) is iterated n times. Keeping in mind that n will be at least $10^{20}$, we can safely assume that it is impractical to compute f as is.

output.txt

[28335972461715929029549703474744235564956581966750837731515436991813559294419,
 37403273962683825476706766986016116652096926190225822145906203630154751124127,
 ...
 20683259830940408896673758833391608352503039219404794272476581194379608541097,
 55414473181295446142015440809398852386813618115944521051995707998928249796248]

The output file contains an array of 54 integers, of 256 bits each. We can safely assume that this is the output of the encrypt function with the flag given as plaintext.

Searching for a closed form solution

Knowing that it is fairly impractical to get any information from the sha256 output digests, we must find a way to simplify function f, ideally bringing down the complexity from $\mathcal{O}(N)$ to $\mathcal{O}(1)$, where $N=n$.

Searching around for closed form solutions to iterated functions, we can learn that:

$$x_n \mapsto a x_{n - 1}^{2}+b x_{n - 1} +{\frac {b^{2}-2b-8}{4a}}$$

has a closed form:

$$n \mapsto {\frac {2\alpha ^{2^{n}}+2\alpha ^{-2^{n}}-b}{2a}}$$

where:

$$\alpha ={\frac {2ax_0+b\pm {\sqrt {(2ax_0+b)^{2}-16}}}{4}}$$

In our specific case we have coefficients $a = 1$ and $b = 0$.

So now we can simply calculate $\alpha$, plug it into the closed form along with $n = 10^{20+i}$ and decode every character of the flag?

Not so fast... The iterated function for which we found a closed form generates an always increasing sequence of integers. Our function f operates under $\text{mod} \ p$, so instead we get a still huge but eventually cyclic sequence of integers. To get to our desired close form we must keep this in mind.

A walk in the finite field woods

Taking a closer look at the equation for $\alpha$, we can observe that it's in the form of a quadratic formula. So $\alpha$ is the root of a second degree polynomial with coefficients $a = 2$, $b = -(2ax_0 + b)$ and $c = 2$. In our case the polynomial would look like $2x^2 - 10x + 2$. Our objective now is to find the roots of this polynomial $\text{mod} \ p$.

We can represent the polynomial ring in one indeterminate over a finite field $\text{GF}(p)$. We can then find the roots of this polynomial:

sage: F.<alpha> = GF(p)

sage: R.<x> = PolynomialRing(F, 'x')

sage: f = 2 * x^2 - 10 * x + 2

sage: f.roots(multiplicities=False)
[]

Oh! No roots? That seems odd. Let's check if the polynomial is irreducible in this polynomial ring.

sage: f.is_irreducible()
True

We can leverage field extension theory to deduce that this is due to the fact that the roots of a second degree polynomial do not belong to $\text{GF}(p)$, but instead they are part of $\text{GF}(p^2)$.

sage: F.<alpha> = GF(p^2)

sage: R.<x> = PolynomialRing(F, 'x')

sage: f = 2 * x^2 - 10 * x + 2

sage: roots = f.roots(multiplicities=False)
sage: roots
(7135491744499822517601019775201591905370636666957345689383307065704368190844*alpha + 32515768181578960114693256139772772916002814499888813854556049534830466505399,
 50760552874158275194184472729142362021264355665862936330345484938252196629105*alpha + 25380276437079137597092236364571181010632177832931468165172742469126098314555)

Bingo! We have $\alpha \ \text{mod} \ p$.

Big powers

Now we can apply the mapping $n \mapsto {\frac {2\alpha ^{2^{n}}+2\alpha ^{-2^{n}}-b}{2a}}$ to retrieve the $n$-th element of the sequence $\text{mod} \ p$. Taking into account our coefficient, we can simplify the mapping to $n \mapsto \alpha ^{2^{n}}+\alpha ^{-2^{n}}$.

So let's compute the $10^{20}$-th element:

sage: roots[0]^(2^(10^20))+roots[0]^(-2^(10^20))
OverflowError: exponent must be at most 9223372036854775807

We have a small problem, the $2^{10^{20}}$ has $30102999566398119522$ decimal digits, while the maximum supported exponent has only $19$ decimal digits. We need to find a way to simplify this power.

Luckily we can leverage the multiplicative order of $\alpha$, defined for $a \ \text{mod} \ p$ as the smallest positive integer $k$ such that $a^k \equiv 1 \ \text{mod} \ p$. Using this notion we can deduce that $a^n \ \text{mod} \ p = a^{n \ \text{mod} \ k} \ \text{mod} \ p$, so instead of computing the power we can computer the power $\text{mod} \ k$ using the square-and-multiply algorithm.

Knowing this we can finally rewrite f as:

def f(i):
    cc = roots[0]^2.powermod(i, roots[0].multiplicative_order())
    return cc + 1 / cc

Cracking the code

Having greatly simplified function f, we can simply brute-force each character by computing sha256 digests of printable character.

dictionary = {}
for i in printable:
  dictionary[int.from_bytes(sha256(i.encode()).digest(), "big")] = i

def match(mask, c):
  for item in dictionary:
    if (item * mask) % p == c:
      return dictionary[item]
  raise Exception("No match found")

def decrypt(cypher):
  res = []
  for i, c in enumerate(cypher):
    val = f(10^(20+i))
    mask = int.from_bytes(sha256(str(val).encode()).digest(), "big")
    res.append(match(mask, c))
  return res

Executing decrypt on the output yields the correct flag!

sage: "".join(decrypt(output))