MadMath — HackTheBox

Description

They told me it was only numbers. Then the numbers started laughing.

A two-stage crypto challenge. We are given crypto_madmath/server.py. A secret module imports PASSPHRASE, curve_a, curve_p, g_order (all hidden), and the flag lives in flag.txt on the server.

Server flow per connection:

1. gen(1024) builds an RSA keypair with structured primes, then prints d and c = PASSPHRASE^e mod n (e = 0x10001). n is never given.
2. An ECC oracle loop: KEY = sha256(PASSPHRASE), cipher = AES-ECB(KEY). For each user-supplied exp with 1 < exp < g_order, it returns cipher.encrypt(pad(str(point_mul(pow(FLAG, exp, g_order))))). Here point_mul(k) = k*G on y^2 = x^3 + curve_a*x + b (mod curve_p), and FLAG = bytes_to_long(flag.txt) with assert FLAG < g_order <= 1<<257.

Goal: recover FLAG.

Analysis

The gen() structure (why phi is a perfect square)

FactorWalker builds smooth numbers as products of primes up to 70 bits. gen(1024) produces:

p = a**2 * g + 1
q = b**2 * g + 1

with the same even g (~256 bits) used for both primes, and a, b ~128-bit smooth values. Therefore:

phi = (p-1)(q-1) = (a^2 * g) * (b^2 * g) = a^2 * b^2 * g^2 = (a*b*g)^2

phi is a perfect square, and every prime factor of R = sqrt(phi) = a*b*g is <= 70 bits — directly factorable with ECM.

The Stage-2 trap (why curve ECDLP is the wrong move)

After recovering the AES key and decrypting oracle outputs to exact points, the curve can be recovered from observed points. The recovered curve has prime order N (256-bit), with a ~128-bit trace — not anomalous, not supersingular, large embedding degree. The curve ECDLP is genuinely hard. That is the "MadMath" trap.

The real observation: g_order == N == #E == order(G), and N-1 is fully smooth (largest prime ~4.08e8 ≈ 2^29) — the FactorWalker smoothness signature. The intended discrete log lives in the multiplicative group (Z/N)*, not on the curve. The point s*G is just an opaque commitment to the residue s = FLAG^exp mod N.

Solution

Stage 1 — recover n from (d, e), decrypt PASSPHRASE

1. e*d - 1 = k*phi for some k < e. Because phi is a perfect square, iterate k = 1..e and keep every k for which (e*d-1)/k is a perfect square. Each gives a candidate phi and R = sqrt(phi) = a*b*g. Try all candidates (largest first); do not early-return on the first.
2. Factor R (~512-bit, all prime factors ≤ 70 bits) with GMP-ECM, recursing into composite cofactors with increasing B1 until fully factored.
3. phi = R^2, so phi's factorization is the R-primes with doubled exponents. DFS-partition phi into a divisor D such that D+1 and phi/D+1 are both prime → p = D+1, q = phi/D+1, n = p*q. Multiple candidates are possible.
4. PASSPHRASE = long_to_bytes(pow(c % n, d, n)); pick the candidate that decrypts to printable ASCII.

Result: PASSPHRASE = "Korea <3 Discrete Logarithm Problems" (a hint at the multiplicative DLP). AES KEY = sha256(PASSPHRASE).

from math import isqrt
from sympy import isprime
from collections import Counter
import subprocess

e = 0x10001
ECM = "/opt/homebrew/Cellar/gmp-ecm/7.0.7/bin/ecm"

def recover_phi(d):
    """Every k where (e*d-1)/k is a perfect square -> (k, phi, R=sqrt(phi))."""
    ed1 = e*d - 1
    res = []
    for k in range(1, e):
        if ed1 % k: continue
        c = ed1 // k
        r = isqrt(c)
        if r*r == c:
            res.append((k, c, r))
    res.sort(key=lambda t: -t[1].bit_length())   # largest phi first
    return res

def _recover_from_phi(phi, R):
    rfacs = factor_R(R)                # full prime factorization via GMP-ECM
    cnt = Counter(rfacs)
    primes = [(pr, ex*2) for pr, ex in sorted(cnt.items())]  # phi = prod pr^(2ex)
    bound = isqrt(phi) * 1024
    results = []
    def dfs(i, D):
        if D > bound: return
        if i == len(primes):
            other = phi // D
            if D <= other and isprime(D+1) and isprime(other+1):
                results.append((D+1, other+1))
            return
        pr, ex = primes[i]; m = 1
        for _ in range(ex+1):
            dfs(i+1, D*m); m *= pr
    dfs(0, 1)
    return [(p, q, p*q) for (p, q) in results]

Verified 8/8 across random regenerations, ~5–20s.

Stage 2 — recover the curve, then the multiplicative DLP

Recover the curve. Decrypt all oracle responses with the AES key to exact points (x,y). Points satisfy y^2 = x^3 + a*x + b mod curve_p. Eliminate a,b across point pairs; the gcd of cross-difference resultants yields curve_p (prime, 256-bit). Solve two points for curve_a, b. Use PARI/GP ellcard / ellorder (set default(parisize,"2G") to avoid stack overflow) for the order:

curve_p = 60848817910369111880334871105011015293762638801805685625660812011580778435781
curve_a = 18865174068405431581497284369000395014185291302481098978271679810889706729685
G       = (40733212845287381659537354559134076551920727536123123802035255333770142251507,
           5939195932044123182011708420242714254691399994280021264443261849355562421816)
N       = 60848817910369111880334871105011015293954578314645948866266287745965108392789  # PRIME

N-1 factors fully smooth: 2^2·7^4·29·47·6991^2·4909·21821·3686341·1325227·101411^2·766079·138827527·407639629^2.

The linear-action primitive. Integer scalar multiplication of the commitment acts linearly on the hidden residue:

c * (s*G) == (c*s mod N) * G

This lets us read residues in small subgroups via a point-BSGS without ever solving the full curve ECDLP — work drops from O(q) to O(sqrt(q)).

Pohlig-Hellman in (Z/N)*. Pick a primitive root g (g=2), write FLAG = g^x mod N. Recover x mod q^k for each prime power q^k || (N-1), digit by digit. For digit i, query exponent e_i = (N-1)/q^{i+1}. Then FLAG^{e_i} = R_i^{x mod q^{i+1}} where R_i = g^{e_i}. Cancel the already-known lower digits by an integer multiply of the target point (the linear action), leaving (G_q^{digit_i})*G, and read digit_i with a point-BSGS in the order-q subgroup. CRT all residues → x → FLAG = g^x mod N.

# point-BSGS: find d in [0,q) such that  T == (G_q^d mod N) * G
def point_bsgs(E, G, T, G_q, q, baby_cache):
    M = math.isqrt(int(q)) + 1
    if id(G_q) in baby_cache:
        baby, M = baby_cache[id(G_q)]
    else:
        baby = {}; r = mpz(1)
        for j in range(M):
            baby[E.mul(r, G)] = j           # baby[(G_q^j)*G] = j
            r = (r * G_q) % N
        baby_cache[id(G_q)] = (baby, M)
    invGqM = int(invert(powmod(G_q, M, N), N))   # integer = G_q^{-M} mod N
    cur = T
    for i in range(M + 1):
        if cur in baby:
            d = i*M + baby[cur]
            if d < q: return d
        cur = E.mul(invGqM, cur)               # giant step = integer-mult target

def recover_mod_qk(oracle_point, E, G, g, q, k):
    G_q = powmod(g, (int(N)-1)//q, N)          # order q
    baby_cache = {}; low = 0
    for i in range(k):
        e_i = (int(N)-1) // (q ** (i+1))       # exponent on FLAG
        T   = oracle_point(e_i)                # (R_i^{x mod q^{i+1}})*G
        R_i = powmod(g, e_i, N)                # order q^{i+1}
        if low:                                # cancel known lower digits (linear action)
            c = int(invert(powmod(R_i, low, N), N))
            T = E.mul(c, T)
        digit = point_bsgs(E, G, T, G_q, q, baby_cache)
        low += digit * (q ** i)
    return low % (q ** k)

Full chain (solve_flag.py): Stage 1 reads d,c → recovers n → decrypts PASSPHRASE → derives the key; Stage 2 wires an oracle_point(exp) that decrypts the AES-ECB reply to (x,y) and feeds flag_core.recover_flag. ~20 oracle queries, ~34s with gmpy2 EC arithmetic.

FLAG int = 32715399094269510894392478485627661754772505500287507026284076333174707535741
long_to_bytes -> b'HTB{REDACTED}'

The curve, N, and PASSPHRASE are fixed constants across connections; only d,c regenerate, so Stage-2 constants can be hardcoded.

Pitfalls

• Pohlig-Hellman ON the curve fails. The curve order N is prime and ECDLP is hard. The DLP must be moved to (Z/N)* multiplicatively.
• Pure point-equality (AES-ECB determinism) only reveals ord(FLAG)/periods, not FLAG. The integer-scalar-mult linear-action trick is what reduces work from O(q) to O(sqrt(q)).
• PARI/GP ellcard stack overflows at default size; set default(parisize,"2G").
• recover_n must try ALL perfect-square k candidates and collect every (p,q,n), then disambiguate by which n decrypts c to printable ASCII. A single early-return picks a spurious phi.
• Each new TCP connection regenerates d,c (re-solve Stage 1), but the curve and g_order are fixed constants — hardcode them across connections.