---
tags: ctf,ctf-writeup,amateursCTF
---
# AmateursCTF 2024 - cell-service writeup
- Category: Crypto
- Score: 472/500
- Solve: 7

## Source code
- We were given 2 files: Problem source code in *cell-service.py* and the data in *out.txt* (compressed in *out.zip*). However, due to the enormous size of *out.txt*, I'll not show it here.

def num_to_ascii(n):
    a = 0
    while n % p == 0:
        n //= p
        a += 1
    return chr(a)

def unhex(n):
    return int(n, 16)

def eval_tower(tower):
    while tower:
        b = tower.pop()
        if isinstance(b, str):
            x, y = map(unhex, tower.pop())
            a = unhex(b)
        else:
            x, y = map(unhex, b)
        a = (pow(x, a) + pow(y, a)) // p
    return num_to_ascii(a)

def eval_towers(towers):
    cat = ""
    for tower in towers:
        cat += eval_tower(tower)
    return cat

with open('out.txt') as f:
    p = int(f.readline())
    print(eval_towers(eval(f.readline())))

## Challenge Analysis
We can summarize the problem as follows:
- In *out.txt*, we were given a list of 64 elements: $lst = [e_0, e_1, ..., e_{63}]$ and a 128-bit prime $p$.
- Each element $e_i$ corresponds to a character in the flag and is represented by a list contains 9999 pairs of number $(x_{ij}, y_{ij})$ and a number $a_i$: $e_i = [a, (x_{i,0}, y_{i,0}), (x_{i,1}, y_{i,1}), ..., (x_{i,9998}, y_{i,9998})]$ (*I reversed the list for the ease of representation.*)
- An interesting point is that $p$ divides sum of each pair: $$p|x_{ij} + y_{ij}$$
- The flag is computed as follow:
- Denote $v_p(x)$ to be the greatest power in which a prime $p$ divides $x$.
- Character $i$ of the flag is $v_p(t_{9998})$ where sequence $t_n$ is computed as following: $$t_j = \begin{cases} \frac{x_{ij}^{t_{j - 1}} + y_{ij}^{t_{j - 1}}}{p} & \text{ if } j >= 1,\\ \frac{x_{i, 0}^a + y_{i,0}^a}{p} & \text{ if j = 0} \end{cases}$$

## My Approach
- In the first version of the challenge (which is said to be broken by Neobeo), $a$ (or $t_j$) is not divided by $p$ after each iteration.

- My first thought is to the **Euler's theorem**. The idea is to calculate $t_{9998}\space mod\space p$, $t_{9998}\space mod\space p^2$, ... and so on. However, this requires me to calculate Euler's totient function 9999 times on $p, p^1, p^2, ..., p^{127}$. Sage cannot automatically handles this due to the size of $p$.
- I then shifted the approach to **Carmichael function** $\lambda(x)$ - a reduced version of Euler's totient function, which requires the factorization of $x$. I stole the Sage's implementation of Carmichael function and tweaks it a little bit to work in this case. However, it didn't work.
- The problem is that at some step, $t_j$ is divisible by $p$, preventing us from applying the property of Carmichael function (and Euler's theorem too).
- I also thought of **Hensel's lemma** but stopped diving further. Sadly, it is closely related to the intended solution of this challenge (FML).
- After some unknown period of time, the author announced that a fix had been delivered for *cell-service*.
- This time, $a$ (or $t_j$) is not by $p$ after each iteration. This further ensures that my original approach was not correct. However, I failed to find a new approach until the end of competition :(.

## The Intended Solution
- After the CTF, I dived into the CTF's Discord server to see how other teams solved it.

- **Lifting-the exponent Lemma**, hmm. Never heard of it. Anyway, I'll give it another shot.
- In short, we need the following result to solve the problem:
Let $p$ be a prime number and let $x$ and $y$ be two integers that are not divisible by $p$. Then for an odd positive integer $n$: if $p | x + y$, then $v_p(x^n + y^n) = v_p(x + y) + v_p(n)$
- From these, we can rewrite the $v_p(t_j)$ as: $$v_p(t_j) = v_p(\frac{x_{ij}^{t_{j - 1}} + y_{ij}^{t_{j - 1}}}{p}) = v_p(x_{ij} + y_{ij}) + v_p(t_{j - 1}) - 1 $$
- Continuously expand the above equation gave us the way to compute between $v_p(t_j)$ from $v_p(t_0), v_p(t_1), ..., v_p(t_{j - 1})$.
- However, the equation no longer holds if $t_{j - 1}$ is even, which is equivalent to the fact that $x_{ij} + y_{ij}$ is even. In this case, $v_p(t_j) = 0$. (Need proof or not?).
- Eventually, in order to solve the challenge, we just need to iterate through $e_i$, calculate $v_p(x_{ij} + y_{ij})$ and add it to the current power until we encountered an even case.
- Solve script:

from out import output # import the array from out.txt

def calc_power(a, p):
    if a == 0:
        return 0
    power = 0
    while a % p == 0:
        power += 1
        a //= p
    return power

p = 183905317677500011457945744395125586799
flag = ''

# Convert hex string to integers
for i in  range(len(output)):
    output[i][-1] = int(output[i][-1], 16)
    for j in range(9999):
        x, y = output[i][j]
        x, y = int(x, 16), int(y, 16)
        output[i][j] = (x, y)

for i in range(len(output)):
    power = 0
    a = output[i][-1]
    for j in range(9999):
        x, y = output[i][j]
        if (x + y) % 2 == 0:
            break
        power += calc_power(x + y, p) - 1 # Apply the LTE Lemma here

    flag += chr(power)
    print(f'{flag = }')

**Flag: amateursCTF{3xponents_4re_cool_or_s0mething?!?_4d767c85f66f530c}**