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

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

...