TRXCTF crypto writeups

Table of Contents

factor.com - Writeup

Author: magicfrank
Difficulty: ★☆☆☆☆
Solves: 43/550

This challenge is similar to standard RSA, except that the modulus $N$ is a product of multiple primes, some of which can be very small.

Exploiting the Structure

Instead of waiting for all primes to be small (which could take an impractical amount of time), we can extract small pieces of information at a time by factoring parts of $N$.

If we manage to extract even one small prime factor $q$ of $N$, we can immediately start recovering the flag:

Breaking It Down

We are given the standard RSA equation:

$$ \text{flag}^e \mod N = c $$

If we find a small prime $q$ that divides $N$, we can reduce the equation modulo $q$:

$$ c \mod q = (\text{flag}^e \mod N) \mod q = \text{flag}^e \mod q $$

Since $e$ is known, we can compute the $e$-th root modulo $q$ to recover:

$$ \text{flag} \mod q $$

Reconstructing the Full Flag

By repeating this process for multiple small prime factors, we collect a system of modular equations:

$$ \text{flag} \mod q_1, \quad \text{flag} \mod q_2, \quad \dots, \quad \text{flag} \mod q_n $$

Finally, using the Chinese Remainder Theorem (CRT), we reconstruct the original flag.

factordb.com - Writeup

Author: magicfrank
Difficulty: ★☆☆☆☆
Solves: 32/550

Disclaimer: It’s magicfrank speaking at 20 Feb 00:57 2025. I really hope nobody actually uploads the factorization to factordb.com, but let’s see.

Understanding the Leak

This challenge is a standard RSA with a leak where we have to factorize the modulus.

The function generating the leak is particularly bad because each bit of leak_i only depends on the lower (least significant) bits of $p$ and $q$.

This means:

  • $\text{LEAK} \mod 2$ only depends on $p \mod 2$ and $q \mod 2$.
  • $\text{LEAK} \mod 2^2$ depends only on $p \mod 4$, $q \mod 4$.
  • $\text{LEAK} \mod 2^3$ depends only on $p \mod 8$, $q \mod 8$.

Since each step only depends on previously discovered bits, we can reconstruct $p$ and $q$ one bit at a time by trying all possible values and checking against both $N$ and the leak.

Recovering the Factors

We recover $p$ and $q$ bit by bit using brute-force with constraints. We start with the least significant bit (LSB) and systematically build up to the full values.

Step-by-Step Example

  1. Finding the first bit

    • Since $N \mod 2 = 1$, we know that both $p$ and $q$ must be 1.
    • The possible values for $(p \mod 2, q \mod 2)$ are:
      • (0,0) → 0 × 0 = 0 (incorrect)
      • (0,1) → 0 × 1 = 0 (incorrect)
      • (1,0) → 1 × 0 = 0 (incorrect)
      • (1,1) → 1 × 1 = 1 (correct ✅)

    So the only valid choice is (1,1).

  2. Finding the second bit

    • Now, we try all possibilities for the second-least significant bit, while keeping the first bit fixed.

    • Possible values:

      • (1,1)
      • (1,3)
      • (3,1)
      • (3,3)

    • We check which of these satisfy both:

      • $N \mod 4$
      • $\text{LEAK} \mod 4$

    • In this case N%4 = 1

      • (1,1) → 1 × 1 = 1 (correct ✅)
      • (1,3) → 1 × 3 = 3 (incorrect)
      • (3,1) → 3 × 1 = 3 (incorrect)
      • (3,3) → 3 × 3 = 1 (correct ✅)

    • We have two valid choices: (1,1) and (3,3), so let’s check the leak function

    • LEAK%4 = 2

      • (1,1) → (0x1337 + 1 + 1) ^ (0x1337 * 1 * 1) & (1 | 0x1337137) = 2 (correct ✅)
      • (3,3) → (0x1337 + 3 + 3) ^ (0x1337 * 3 * 3) & (3 | 0x1337137) = 2 (correct ✅)

    • Both are valid, so we can continue with both.

  3. Finding the third bit

    • Now partial p and q could be either (1,1) or (3,3)
    • Possible values:
      • (1,1)
      • (1,5)
      • (5,1)
      • (5,5)
      • (3,3)
      • (3,7)
      • (7,3)
      • (7,7)
    • Check on N%8=5
      • (1,1) → 1 × 1 = 1 (incorrect)
      • (1,5) → 1 × 5 = 5 (correct ✅)
      • (5,1) → 5 × 1 = 5 (correct ✅)
      • (5,5) → 5 × 5 = 1 (incorrect)
      • (3,3) → 3 × 3 = 4 (incorrect)
      • (3,7) → 3 × 7 = 5 (correct ✅)
      • (7,3) → 7 × 3 = 5 (correct ✅)
      • (7,7) → 7 × 7 = 1 (incorrect)
    • Check on LEAK%8=2
      • (1,5) → (0x1337 + 1 + 5) ^ (0x1337 * 1 * 5) & (1 | 0x1337137) = 6 (incorrect)
      • (5,1) → (0x1337 + 5 + 1) ^ (0x1337 * 5 * 1) & (5 | 0x1337137) = 6 (incorrect)
      • (3,7) → (0x1337 + 3 + 7) ^ (0x1337 * 3 * 7) & (3 | 0x1337137) = 2 (correct ✅)
      • (7,3) → (0x1337 + 7 + 3) ^ (0x1337 * 7 * 3) & (7 | 0x1337137) = 2 (correct ✅)
    • We have two valid choices: (1,5) and (3,7)
      • Note that the leak in this case actually helped us by eliminating half of the possibilities!

  4. Finding the fourth bit

    • …

…. …

BFS Implementation

We won’t do it by hand (it’s certainly possible, but humans invented computers for a reason).

from collections import deque

def bfs(n, leak):
    start = (0, 0, 1)  ## (p_guess, q_guess, bit_position)
    queue = deque([start])
    ccc = 0

    while queue:
        pk, qk, k = queue.popleft()
        ccc += 1
        if ccc % 100 == 0:
            print(f"\r{k}", end='')

        if pk * qk > n:
            continue
        if pk * qk == n:
            print("FOUND", pk, qk)
            return pk, qk
        
        ## Try all possible combinations of the next bit
        poss = [(0,0), (0,2**(k-1)), (2**(k-1),0), (2**(k-1),2**(k-1))]
        for pos in poss:
            new_pk, new_qk = pk + pos[0], qk + pos[1]
            if (F(new_pk, new_qk) % 2**k == leak % 2**k and 
                (new_pk * new_qk) % 2**k == n % 2**k):
                queue.append((new_pk, new_qk, k+1))

babyDLP - Writeup

Author: magicfrank
Difficulty: ★★★★☆
Solves: 9/550

This challenge has two main parts:

  • Recovering d (straightforward)
  • Recovering the flag (a bit more challenging)

Recovering d

This is a classic biased-nonce attack, which can be solved using LLL.

We are given the equations:

$$ R = (k_1 + k_2) \cdot G $$$$ s = \frac{h \cdot k_2 + d \cdot R.x}{k_1} $$

where k1 and k2 are two 32-bit random values.
Each time we make a signing query, we get the equation:

$$ s \cdot k_1 = h \cdot k_2 + d \cdot R.x $$

Here, k1 and k2 are the unknowns, and d is the secret key we want to extract.

Since both k1 and k2 are small (32-bit), we can solve this as a system of linear equations with small unknowns using LLL.

For details on this I’ve written a blog post here:
https://magicfrank00.github.io/writeups/posts/lll-to-solve-linear-equations/

Recovering the Flag

At this point, we are given $ \text{flag} \mod \text{p}$

The issue is that the flag is around 350 bits, while the prime is only 195 bits. Brute-forcing the missing 150 bits isn’t feasible.

After writing this challenge, I realized there’s an extremely similar challenge by Neobeo. Instead of re-explaining the solution, I’ll just link his excellent writeup here:

https://web.archive.org/web/20240412075022/https://demo.hedgedoc.org/s/DnzmwnCd7

Overview on my solution

We can represent the flag bytestring as a sum of its character values multiplied by powers of 256:

$$ c_0 \cdot 256^{43} + c_1 \cdot 256^{42} + \dots + c_{42} \cdot 256 + c_{43} $$

where each $c_i$ corresponds to a character in the flag.

We’re given this equation, but with an extra modulus term, so we end up with:

$$ c_0 \cdot 256^{43} + c_1 \cdot 256^{42} + \dots + c_{42} \cdot 256 + c_{43} = m + k \cdot p $$

where:

  • $m$ is the value we are given.
  • $p$ is the order of the curve (modulus).
  • $c_i$ are the characters of the flag.

We are looking to find a solution to this equation where each $c_i$ is very small. Applying LLL in a naive way won’t give the solution, but we can apply a few tricks to reduce the size of the unknowns even more and then solve with LLL:

  1. We know the flag format starts with TRX{, so we can simply subtract this known prefix from the equation. (same for })

  2. We know the remaining flag characters are mostly lowercase ASCII letters, meaning each $c_i$ is close to the average lowercase ASCII value (≈106).
    So we rewrite the equation as:

    $$ (c_0 + 106) \cdot 256^{43} + (c_1 + 106) \cdot 256^{42} + \dots + (c_{42} + 106) \cdot 256 + (c_{43} + 106) = m + k \cdot p $$

    Now, each unknown $c_i$ is very close to 0 (within about ±15), which makes LLL effective.

  3. Brute-forcing for more precision:
    If we brute-force just the first unknown character, we reduce the problem complexity by another 5 bits, making the solution even more precise.

Solve code
from Crypto.Util.number import bytes_to_long
for c in 'abcdefghijklmnopqrstuvwxyz_':
    FLAG_LEN = 44
    AVG_VALUE = 106

    known_format = 'TRX{'+c
    base = (bytes_to_long(known_format.encode()) << (8*(FLAG_LEN-len(known_format)))) + ord('}')

    m_ = (d - base) % p
    kbitlen = max(0,8*(FLAG_LEN-len(known_format)) - m_.bit_length())

    P = PolynomialRing(ZZ, ','.join(['k'] + [f'c{i}' for i in range((FLAG_LEN-(len(known_format) + 1)))]))
    k_sym = P.gen(0)
    cs = P.gens()[1:]


    eq = sum((cs[i] + AVG_VALUE)*256**(FLAG_LEN-(len(known_format) + 1)-i) for i in range((FLAG_LEN-(len(known_format) + 1))))  - m_ ## c0*256^43 + c1*256^42 + ... + c15*256^1 = m_ + k*p
    M,mons = Sequence([eq]).coefficients_monomials(sparse=False)
    M = block_matrix(QQ, [
        [M.T,1],
        [-p, 0]
    ])

    ww = [1] + [16]*len(cs) + [1]
    ws = diagonal_matrix([max(ww)//x for x in ww],sparse=False)
    M *= ws
    M = M.BKZ(block_size=100,proof=False)
    M = M / ws

    green = ('\033[92m', '\033[0m')
    grey = ('\033[90m', '\033[0m')
    from string import ascii_lowercase
    for row in M:
        if abs(row[-1]) == 1 and row[0] == 0:
            try:
                s = (bytes((row * row[-1])[1:-1] + vector([AVG_VALUE]*len(cs))))
                if all(x in (ascii_lowercase+'_').encode() for x in s):
                    print(green[0], known_format.encode() + s + b'}', green[1])
                    ## break
                else:
                    print(grey[0], known_format.encode() + s + b'}', grey[1])
            except:
                pass

Brainrot - Writeup

Author: magicfrank
Difficulty: ★★★☆☆
Solves: 4/550

We’re given three equations and need to recover a flag, which we can split into five parts:

$$ f_0, f_1, f_2, f_3, f_4 $$

These equations represent the evaluation of a polynomial at specific points. The unknowns (the flag parts) are the coefficients of this polynomial. The given values are just different points where the polynomial has been evaluated:

$$ P(x) = \sum_{i=0}^{4} \mathrm{rot}_{8000}(f_i) \cdot x^i $$

We also have two modulus values that play a role in how the results are structured:

$$ m_1 = \text{b2l}(b'\text{cant\_give\_you\_everything}') $$$$ m_2 = \text{b2l}(b'\text{only\_half!!!}') $$

The Given Equations

The challenge gives us three polynomial evaluations, but with a double modulo operation applied. First, the result is reduced modulo $m_1$, and then that result is further reduced modulo $m_2$:

$$ \begin{aligned} P(0x\text{deadbeef}) \mod m_1 \mod m_2 &= r_1 \\ P(13371337) \mod m_1 \mod m_2 &= r_2 \\ P(0x\text{cafebabe}) \mod m_1 \mod m_2 &= r_3 \end{aligned} $$

$\mathrm{rot}_{8000}$

The function $\mathrm{rot}_{8000}$ applies a specific transformation that encodes each flag part using UTF-16. It can be expressed as:

$$ \mathrm{rot}_{8000}(\text{'FLAG'}).encode('utf-16') = 0xfffe0000000000000000 + \sum_{i=0}^{3} ((0x40 + \text{FLAG}[i]) \times 256 + 0x1f) \times 256^{2(3-i)} $$

(This can be recovered just by playing with this function a bit)

Working Around the Moduli

To simplify things, we introduce two helper variables $k_1$ and $k_2$:

$$ \text{eq} - k_1 \cdot m_1 - k_2 \cdot m_2 = \text{res} $$

Since $k_2$ is roughly $m_1 / m_2$, we end up with a system of three equations where the solutions are small and bounded.

Solving with LLL

At this point, solving the equations comes down to finding small solutions to a linear system. This is exactly what LLL is good for.

A great explanation of how to use LLL for problems like this can be found here:
https://magicfrank00.github.io/writeups/posts/lll-to-solve-linear-equations/

Solve code

from Crypto.Util.number import bytes_to_long as b2l
outs = [25655763503777127809574173484, 8225698895190455994566939853, 10138657858525287519660632490]
points = [0xdeadbeef, 13371337, 0xcafebabe]
mod1 = b2l(b'cant_give_you_everything')
mod2 = b2l(b'only_half!!!')

P = PolynomialRing(ZZ, ','.join([f'f{i}{j}' for i in range(10) for j in range(4)] + [f'k{i}' for i in range(len(outs))]))
fsym = P.gens()[:-len(outs)]
fsym = [sum([((fsym[i*4+j] + 76 + 0x40)*256 + 0x1f)*(256**2)**(3-j) for j in range(4)])+ 0xfffe0000000000000000 for i in range(10)]
ksym = P.gens()[-len(outs):]

eqs = []
for i in range(len(points)):
    eqs.append(sum([(fsym[j])*points[i]**j for j in range(10)]) - (ksym[i])*mod2 - outs[i])

A,mons = Sequence(eqs).coefficients_monomials(sparse=False) 
L = block_matrix(QQ, [
    [A.T, 1],
    [mod1, 0]
])

ws = diagonal_matrix([1]*len(eqs) + [44]*len(P.gens()[:-len(outs)]) + [(mod1//mod2) >> 1]*len(ksym) + [1], sparse=False)
L /= ws
L = L.BKZ(block_size=40, proof=False)
L *= ws
for row in L:
    if row[:len(eqs)] == 0 and row[-1] in [-1,1]:
        try:
            print(bytes(x+76 for x in (row*row[-1])[3:-4]))
        except:
            pass

lepton - Writeup

Author: magicfrank & Vertux
Difficulty: ★☆☆☆☆
Solves: 72/550

The unintended solution consisted in just sending the point ‘0,0’, so that $\varphi{(0,0)}$ return 0, encrypting the flag with sha256(0)

lepton2 - Writeup

Author: magicfrank & Vertux
Difficulty: ★★★★☆
Solves: 16/550

This challenge is inspired by Seashells from N1CTF 2024.

To solve this we exploit the fact that sagemath gives an error when calling .xy() on the 0 point, so we can use this as an oracle to recover the privkey one bit at a time.

The writeup is basically the same as https://magicfrank00.github.io/writeups/writeups/n1ctf2024/seashells/