Unstable

Author: 0xIDA

Solvers

• solve.py

Platform: FlagYard · Category: crypto · Difficulty: Medium

Flag

FlagY{66439c227ac76fc4a79b77b7d8bfd488}

Challenge

TCP service runs Challenge.py:

• Flag is XOR'd with a single random byte key, then split in half.
• Each half is encrypted under a Rabin-like map: ct = m * (m + myprime) mod n
• Primes are constructed as p = 3 * myprime * r + 2 with shared 128-bit myprime.
• Padded (256-byte) ciphertexts are also given but not needed.

Exploitation chain

1. Connect to instance; collect n1, ct1, ct2, n2, ct3, ct4.
2. Recover shared prime: myprime = gcd(n1-4, n2-4) (strip factor 3 if present) — because each prime ≡ 2 (mod myprime) ⇒ n ≡ 4 (mod myprime).
3. Unpadded message halves are short (≈19–20 bytes), so m*(m+myprime) < n and there is no modular reduction.
4. Solve quadratic over the integers:
   • disc = myprime^2 + 4*ct is a perfect square
   • m = (-myprime + sqrt(disc)) / 2
5. Concatenate halves and brute single-byte XOR (0–125) until FlagY{...} appears.

Tools

• Python3, gmpy2, pwntools remote
• Host: tcp.flagyard.com (dynamic port)

Notes

• Padded cts and full factorization of n are unnecessary once you notice the unpadded m is small.