cryptofreehard

MadMath

hackthebox

Task: two-stage HTB crypto. Stage 1 recovers RSA n from only (d,e) because structured primes p=a^2*g+1,q=b^2*g+1 make phi a perfect square, then ECM-factors sqrt(phi) to rebuild n and decrypt the AES passphrase. Stage 2 is an AES-ECB ECC oracle returning (FLAG^exp mod g_order)*G on a prime-order curve; the real DLP is multiplicative in (Z/N)* (N-1 fully smooth), solved by Pohlig-Hellman using integer scalar-mult as a linear-action point-BSGS comparator.

$ ls tags/ techniques/
rsaaes_ecbeccpohlig_hellmanperfect_square_phifactor_from_structured_primesgmp_ecmprime_order_curvemultiplicative_dlpsmooth_group_orderpoint_commitmentlinear_scalar_action
recover_n_from_d_via_perfect_square_phiecm_factorizationcurve_parameter_recovery_from_pointspari_ellcardpohlig_hellman_multiplicative_grouppoint_bsgs_comparatorcrtprimitive_root_discrete_log

$ cat /etc/rate-limit

Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.

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.

...

$ grep --similar

Similar writeups