Multiplication as a Service

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: brute_force_dlp, chinese_remainder_theorem, invalid_curve_attack, pohlig_hellman_algorithm, small_subgroup_confinement

Summary

Walkthrough of the CUSTOM Crypto Multiplication as a Service. Task: ECC scalar multiplication oracle on y²=x³+2x+3 over F_10007 that does not validate input points lie on the curve. Solution: Invalid curve attack — send points from curves with smooth orders, sol

---

title: "Multiplication as a Service" id: 20260515_tjctf_multiplication_as_a_service category: crypto difficulty: medium event: tjctf-2026 tags: ["crt", "ecc", "pohlig_hellman", "discrete_logarithm", "scalar_multiplication", "invalid_curve_attack", "point_validation"] techniques: ["brute_force_dlp", "chinese_remainder_theorem", "invalid_curve_attack", "pohlig_hellman_algorithm", "small_subgroup_confinement"] tools: ["python3", "pwntools"] indicators: ["ECC scalar multiplication oracle", "server does not validate point is on curve", "point_add uses only coefficient a", "never checks b", "small prime field (p=10007)", "unlimited oracle queries"]

Multiplication as a Service — TJCTF 2026

Description

"Mendacem oportet esse memorem." — A liar must have a good memory.

The server implements an ECC scalar multiplication oracle. It reads a flag, converts it to an integer secret_d = int.from_bytes(flag, "big"), and for any user-supplied point P = (x, y) computes and returns Q = secret_d * P on the curve y² = x³ + 2x + 3 over F_10007. The server runs in a loop, accepting unlimited queries.

The goal is to recover secret_d (and thus the flag) using only the oracle responses.

Analysis

Server Code

 python read-only • copy allowed Copy
P = 10007
A = 2
B = 3

def point_add(P1, P2):
    # ...
    if x1 == x2 and y1 == y2:
        s = (3 * x1 * x1 + A) * mod_inv(2 * y1, P)  # Only uses A, never B!
    else:
        s = (y2 - y1) * mod_inv(x2 - x1, P)
    s %= P
    x3 = (s * s - x1 - x2) % P
    y3 = (s * (x1 - x3) - y1) % P
    return (x3, y3)

Critical vulnerability: The point_add function only uses the curve coefficient a=2 (in the point doubling formula s = (3x² + a) / 2y). It never checks or uses b=3. The server also never validates that the input point (x, y) satisfies y² ≡ x³ + 2x + 3 (mod 10007).

This means the server will compute scalar multiplication on any curve of the form y² = x³ + 2x + b' for arbitrary b', as long as we supply a point from that curve. The arithmetic is identical — only a matters for the addition/doubling formulas.

Attack Strategy: Invalid Curve Attack

The invalid curve attack exploits missing point validation to confine the secret scalar into small subgroups on attacker-chosen curves:

1. Find invalid curves with smooth orders: For each b' ∈ [0, 10006] where b' ≠ 3, compute the order of E': y² = x³ + 2x + b' over F_10007. Factor each order and collect small prime factors.

2. Find points of specific prime order: For each small prime q dividing some invalid curve's order, find a point of exact order q on that curve by computing (order/q) * G for a random point G on E'.

3. Query the oracle: Send each point of order q to the server. Since the server only uses a=2, it computes Q = secret_d * P using the invalid curve's group structure. The result Q lies in the subgroup of order q.

4. Solve small DLP: Since q is small (≤1000), brute-force the discrete logarithm: find k such that k * P = Q, giving secret_d ≡ k (mod q).

5. CRT reconstruction: Combine all residues via the Chinese Remainder Theorem. If the product of all primes exceeds secret_d, the flag is uniquely determined.

Key Numbers

• 131 distinct small primes collected from ~10,000 invalid curves over F_10007
• Combined CRT modulus: 1026 bits — more than sufficient for the ~250-bit flag
• Flag recovered at k=0 (direct CRT result, no offset needed)

Solution

Step 1: Precompute Invalid Curve Data

For each b' ∈ [0, 10006], compute the curve order using the formula #E = p + 1 - t where t is the trace of Frobenius (computable by counting points or using Schoof's algorithm — for p=10007 brute force is fast). Factor each order and for each small prime factor q, find a point of exact order q.

This produces prime_data.json mapping each small prime to (b_value, point_coordinates, curve_order).

Step 2: Query Oracle and Solve DLPs

 python read-only • copy allowed Copy
#!/usr/bin/env python3
"""
Invalid Curve Attack on ECC scalar multiplication oracle.
Loads precomputed prime data, queries remote server, recovers flag via CRT.
"""

from pwn import *
import json

P = 10007
A = 2

def mod_inv(x, p):
    return pow(x % p, -1, p)

def point_add(P1, P2, a=A, p=P):
    if P1 is None:
        return P2
    if P2 is None:
        return P1
    x1, y1 = P1
    x2, y2 = P2
    if x1 == x2 and (y1 + y2) % p == 0:
        return None
    if x1 == x2 and y1 == y2:
        s = (3 * x1 * x1 + a) * mod_inv(2 * y1, p)
    else:
        s = (y2 - y1) * mod_inv(x2 - x1, p)
    s %= p
    x3 = (s * s - x1 - x2) % p
    y3 = (s * (x1 - x3) - y1) % p
    return (x3, y3)

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x1, y1 = extended_gcd(b % a, a)
    return g, y1 - (b // a) * x1, x1

def crt(residues, moduli):
    result, mod = residues[0], moduli[0]
    for i in range(1, len(residues)):
        r2, m2 = residues[i], moduli[i]
        g, x, _ = extended_gcd(mod, m2)
        if (r2 - result) % g != 0:
            continue
        lcm = mod * m2 // g
        result = (result + mod * ((r2 - result) // g) * x) % lcm
        mod = lcm
    return result, mod

def query_server(io, x, y):
    io.recvuntil(b"x = ")
    io.sendline(str(x).encode())
    io.recvuntil(b"y = ")
    io.sendline(str(y).encode())
    response = io.recvline().decode().strip()
    if "inf" in response:
        return None
    parts = response.replace("Q = ", "").split()
    return (int(parts[0]), int(parts[1]))

def solve_dlp(Q, point, prime):
    """Brute-force DLP in subgroup of small prime order."""
    if Q is None:
        return 0
    cur = None
    for i in range(prime):
        if cur == Q:
            return i
        cur = point_add(cur, point, A, P)
    return None

def main():
    # Load precomputed invalid curve data (131 primes)
    with open("prime_data.json") as f:
        raw = json.load(f)
    prime_data = {}
    for prime_str, (b, pt, order) in raw.items():
        prime_data[int(prime_str)] = (b, tuple(pt), order)
    primes = sorted(prime_data.keys())
    print(f"[*] Loaded {len(primes)} primes from cache")

    # Connect to remote
    context.log_level = 'error'
    io = remote("tjc.tf", 31313, timeout=15)
    io.recvuntil(b"Curve:")
    io.recvline()

    residues, moduli = [], []
    for i, prime in enumerate(primes):
        b, point, order = prime_data[prime]
        Q = query_server(io, point[0], point[1])
        k = solve_dlp(Q, point, prime)
        if k is not None:
            residues.append(k)
            moduli.append(prime)
        if (i + 1) % 20 == 0:
            print(f"[*] Progress: {i+1}/{len(primes)} primes queried")
    io.close()

    # CRT reconstruction
    secret_d, mod = crt(residues, moduli)
    print(f"[*] secret_d ≡ {secret_d} (mod M)")
    print(f"[*] Modulus has {mod.bit_length()} bits")

    # Recover flag
    for k in range(100000):
        candidate = secret_d + k * mod
        if candidate <= 0:
            continue
        try:
            flag_bytes = candidate.to_bytes(
                (candidate.bit_length() + 7) // 8, "big"
            )
            if b"tjctf{" in flag_bytes:
                print(f"[+] FLAG: {flag_bytes.decode()}")
                return
        except:
            pass

if __name__ == "__main__":
    main()

Step 3: Run and Recover Flag

[*] Loaded 131 primes from cache
[*] Progress: 20/131 primes queried
[*] Progress: 40/131 primes queried
...
[*] Progress: 120/131 primes queried
[*] secret_d ≡ 13480003234703408403126709436951282838902635060439314674537647253922534796914045 (mod 590882...011790)
[*] Modulus has 1026 bits
[+] FLAG: tjctf{REDACTED}

Key Takeaways / Lessons

• Mastering brute_force_dlp, chinese_remainder_theorem, invalid_curve_attack, pohlig_hellman_algorithm, small_subgroup_confinement was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-05-15 • CUSTOM • Multiplication as a Service • Difficulty: Medium