AmateursCTF 2025

AmateursCTF 2025 – crypto/addition (330 pts)

“it does addition”

Challenge Overview

• The server prints:

n, e = (N, 3)

• Then repeatedly asks:

scramble the flag:

• For each s, the server returns:

scrambling...
c = <integer>

• The secret flag is encoded as an integer F.

• The server computes:
[
c_s = (F + s)^3 \bmod n
]

• We control s.

Crypto Background: Franklin–Reiter (e = 3)

• (C_1 = M^3 \bmod n)

• (C_2 = (M + S)^3 \bmod n)

Attack Plan

1. Query many times with:
• s = 0 → candidates for (C_1)
• s = 1 → candidates for (C_2)

2. Brute-force all (c1, c2) pairs.

3. For each candidate m:
• Check if pow(m, 3, n) == c1.

4. If valid, extract the flag from m.

Exploit Script

#!/usr/bin/env python3
from pwn import *
from Crypto.Util.number import inverse, long_to_bytes
import ast

# Franklin–Reiter solver for e=3
def solve_franklin_reiter(c1, c2, s, n):
    try:
        num = s * (2 * c1 + c2 - s**3)
        den = c2 - c1 + 2 * s**3
        den_inv = inverse(den, n)
        return (num * den_inv) % n
    except ValueError:
        return None

HOST = 'amt.rs'
PORT = 42963

try:
    r = remote(HOST, PORT)
except Exception as e:
    exit()

# Parse n,e
line = r.recvline().decode().strip()
n, e = ast.literal_eval(line.split('=')[1].strip())

c_zeroes = []
c_ones = []
s = 1
num_queries = 400

for _ in range(num_queries):
    # s = 0
    r.sendlineafter(b'scramble the flag: ', b'0')
    r.recvline()
    c1 = int(r.recvline().decode().split('=')[1])
    c_zeroes.append(c1)

    # s = 1
    r.sendlineafter(b'scramble the flag: ', b'1')
    r.recvline()
    c2 = int(r.recvline().decode().split('=')[1])
    c_ones.append(c2)

r.close()

# Brute-force pairs
found = False
for c1 in c_zeroes:
    if found: break
    for c2 in c_ones:
        m = solve_franklin_reiter(c1, c2, s, n)
        if m is None:
            continue
        if pow(m, 3, n) == c1:
            flag_long = m >> 256
            flag_bytes = long_to_bytes(flag_long, 72)
            try:
                print(flag_bytes.rstrip(b'\x00').decode())
            except:
                print(flag_bytes)
            found = True
            break

if not found:
    print("No matching pair found.")

Important Implementation Details

Consuming the Status Line

r.recvline()  # consume “scrambling...”

Why Many Queries?

Flag Encoding

1. M >> 256 yields flag_long

2. Convert to bytes

3. Strip null padding

Solver Output:

Flag:

amateursCTF{1_h0p3_you_didnT_qU3ry_Th3_s3RVer_100k_tim3s_1b9490c255fe83}

AmateursCTF: Addition 2 Write-up

Challenge Overview

1. Flag Setup: The flag is read and left-shifted by 256 bits. Let's call this $F$.

2. Modulus: A standard 2048-bit RSA modulus $N$ is generated.

3. Encryption Loop:
• It generates 100,000 candidates.
• Each candidate is $m = F + r$, where $r$ is a random 256-bit integer.
• It asks for a user input scramble ($\delta$).
• It calculates $c = (F + r + \delta)^3 \pmod N$.

Vulnerability Analysis

• The Flag ($F$) is shifted 256 bits, so it's roughly $2^{832}$.

• The random padding ($r$) is small: $2^{256}$.

• The modulus ($N$) is $2^{2048}$.

• The exponent $e$ is 3.

Linearization Attack

The Attack Strategy

1. Collect Samples: We request 3 ciphertexts ($C_1, C_2, C_3$) setting the scramble value to 0.

2. Calculate Differences:
• $D_1 = C_1 - C_2 \approx 3F^2(r_1 - r_2)$
• $D_2 = C_2 - C_3 \approx 3F^2(r_2 - r_3)$

3. Eliminate the Unknown: By taking the ratio $D_1 / D_2$, the large unknown term $3F^2$ cancels out:
$$\frac{D_1}{D_2} \approx \frac{r_1 - r_2}{r_2 - r_3}$$

4. Recover Nonces: The values $(r_1 - r_2)$ are relatively small integers (approx 256 bits). We can use Continued Fractions on the ratio $D_1/D_2$ to find the "best rational approximation," which will reveal the integer values of the nonce differences.

5. Solve for Flag: Once we have the nonce difference (let's call it $\Delta r$), we calculate the slope:
$$\text{Slope} = \frac{D_1}{\Delta r} \approx 3F^2$$
Then, $F \approx \sqrt{\text{Slope} / 3}$.

Solution Script

from pwn import *
from Crypto.Util.number import long_to_bytes
import math

def get_rational_approximation(num, den):
    """
    Standard continued fraction algorithm to recover the fraction p/q 
    that best approximates num/den, where q is around 256 bits.
    """
    convergents = []
    x_num, x_den = abs(num), abs(den)
    p_2, q_2 = 0, 1
    p_1, q_1 = 1, 0
    
    while x_den != 0:
        a = x_num // x_den
        p = a * p_1 + p_2
        q = a * q_1 + q_2
        
        # If denominator exceeds expected nonce size (256 bits), stop.
        if q.bit_length() > 265:
            break
        convergents.append((p, q))
        x_num, x_den = x_den, x_num % x_den
        p_2, q_2 = p_1, q_1
        p_1, q_1 = p, q

    return convergents[-1] if convergents else (0, 1)

def solve():
    r = remote('amt.rs', 45157)

    # 1. Parse N and e
    log.info("Waiting for n, e...")
    while True:
        line = r.recvline().decode().strip()
        if "n, e =" in line:
            break
    
    val_str = line.split('=')[1].strip().strip('()')
    parts = val_str.split(',')
    n = int(parts[0])
    
    # 2. Collect 3 Ciphertexts
    ciphertexts = []
    samples = 3
    log.info(f"Collecting {samples} samples. PLEASE WAIT (Server is slow)...")
    
    for i in range(samples):
        r.recvuntil(b'scramble the flag: ')
        r.sendline(b'0')
        r.recvuntil(b'c = ')
        c_val = int(r.recvline().strip())
        ciphertexts.append(c_val)
        log.info(f"Got sample {i+1}/{samples}")

    # 3. Differential Analysis
    diffs = [ciphertexts[i+1] - ciphertexts[i] for i in range(len(ciphertexts)-1)]
    D1 = diffs[0]
    D2 = diffs[1]

    log.info("Calculating flag from differences...")
    
    # Recover delta_r using continued fractions
    dr1, dr2 = get_rational_approximation(D1, D2)
    
    # Calculate slope (approx 3 * F^2)
    slope = abs(D1) // abs(dr1)
    
    # Recover F
    F = math.isqrt(slope // 3)
    
    # Shift back (flag was shifted << 256)
    flag_int = F >> 256
    
    try:
        flag = long_to_bytes(flag_int)
        log.success(f"FLAG: {flag.decode()}")
    except Exception as e:
        log.error(f"Error decoding: {e}")

if __name__ == "__main__":
    solve()

Execution Output

Flag:

amateursCTF{n0_th3_fl4g_1s_n0T_th3_Same_1f_y0U_w3r3_w0ndeRing_533e72a10}

misc/snake Amateurs2025

Step 1: Connect

Step 2: Register an Account

1. When prompted, type register and press Enter.

2. The system will give you a UID (e.g., 9457385429662). Copy this number.

3. For the Password, type pass and press Enter.

Step 3: Log Out

1. Type settings and press Enter.

2. Type logout and press Enter.

Step 4: Malicious Login (The Injection)

1. Type login and press Enter.

2. At the UID: prompt, do exactly this:Plaintext
• Type your UID followed by a space and a backslash: [YOUR_UID] \
• Press Enter.
• Type this exact payload: pass data/d;1d;data/#
• Press Enter.
Example of what it looks like on your screen:
UID: 9457385429662 \
pass data/d;1d;data/#

4. flag:

Flag:

amateursCTF{y0u_ar3_th3_r3al_w1nn3r_0f_sn4k3}