TL;DR
The service is an unrestricted RSA decryption oracle that leaks only popcount(x^d mod n); because 2y mod n is a pure left shift (identical popcount) exactly when 2y < n, a popcount change along a doubling chain proves a modular wrap, and for the chain seeded at m those wrap flags are literally the binary digits of m/n. Three chains (k = 1, 3, 5, 2051 queries each) driven through a beam search recovered all 2048 bits of the secret m in ~1020–1080 s, which was then submitted verbatim to get the flag.
01Recon
The archive contained a single 510-byte prob.py (local copy at /home/kali/Desktop/CTF/Crpto/ popcnt_oracle.tar.gz/prob.py):
e = 65537
while True:
p = getPrime(1024); q = getPrime(1024)
if gcd((p-1)*(q-1), e) == 1: break
n = p * q
d = pow(e, -1, (p-1)*(q-1))
m = secrets.randbelow(n)
c = pow(m, e, n)
print(f"{e = }"); print(f"{n = }"); print(f"{c = }")
while True:
x = int(input("x> "))
if x == m:
print(flag)
break
print(pow(x, d, n).bit_count())Observations that shape the attack:
- Unlimited, unpadded, unblinded decryption. No query cap, no rejection of malleated ciphertexts, no check that x!= c. The only defence is that the return value is a single small integer (0–2048) rather than the plaintext.
- The flag check is x == m, not a decryption of the flag. So the target is recovering the plaintext m, factoring n is not required and no partial- d leak is needed.
- Fresh key + fresh m per connection. p, q, m are generated at process start, so a dropped socket costs a complete re-query. This turned out to be the dominant operational constraint.
- Server-side answer rate measured at ~5.9–6.25 answers/sec (≈0.16 s per 2048-bit pow(x, d, n), no CRT), vs. 6153 queries done in 97.5 s locally. Full remote run ≈ 17 min.
- pwntools was not installed on the box (ModuleNotFoundError: No module named 'pwn'), so the exploit was written against raw socket with a writer thread and a regex answer scanner.
Banner shape confirmed against a live instance:
e = 65537
n = 13865772848690584914911522440805572816742770820957440571 ... [621 chars]
c = 10642851944200752564572311993873177781358910079411299649 ... [621 chars]
x>02The bug
Two composed flaws.
- Homomorphic oracle access. Sending x = c · k^e mod n makes the server compute x^d = (m^e · k^e)^d = k·m mod n, so the oracle is exactly
O(k) = popcount(k·m mod n)for any attacker-chosen k. Textbook RSA malleability, no padding check exists to stop it.
**2. popcount is not invariant under modular reduction, and its failure is informative.** For y ∈ [0, n):
- if 2y < n, then 2y mod n == 2y, which is y shifted left one place → popcount identical;
- if 2y ≥ n, the value becomes 2y − n and the popcount usually changes.
Contrapositive: a popcount change between consecutive elements of a doubling chain proves a wrap occurred. Formally, with v_j = k·2^j·m mod n,
wrap(v_j → v_{j+1}) ⟺ 2·v_j ≥ n ⟺ floor(k·2^(j+1)·m / n) is odd(with f_j = frac(k·2^j·m/n), f_{j+1} = 2f_j − [2f_j ≥ 1] and floor(k·2^(j+1)m/n) = 2·floor(k·2^j m/n) + floor(2 f_j), so the low bit is exactly [2·v_j ≥ n]). For k = 1 those bits are literally the binary expansion of m/n, so 2048 chained queries pin m to within one integer.
The measurement is one-sided: observed change ⇒ true wrap, but a real wrap can coincidentally preserve popcount. Measured hidden-wrap rates: 18.6 % at ~13-bit n, 2.38 % at 512 bits, 1.85 % at 1024 bits, 0.84 % at 2048 bits, so ~9–17 of the ~1024 wraps per chain are silently missed. One-sidedness is what makes the correction sound: pruning any candidate that predicts a 0 where a chain measured a 1 can never discard the truth.
Edge cases checked and clean: n = pq is odd so 2y == n is impossible (no boundary tie); y = 0 never wraps; m = 0 gives an all-zero chain and is still recovered; gcd(k, n) = 1 for k ∈ {3,5} against 1024-bit primes.
POPCOUNT LEAKS ONE BIT PER QUERY
2,051 QUERIES LATER, ALL 2,048 BITS OF IT
03Exploitation
- Parse the banner. Read three lines and pull e, n, c (int(line.split(b"=")[1])). n.
bit_length()was 2047 or 2048 depending on the instance; chain length L = n.bit_length()+ 3 (2050 or 2051). - Build each doubling chain non-adaptively. For a multiplier k, the queries are a geometric progression in ciphertext space, no round-trip dependency, so the whole batch is precomputed:
def chain_queries(c, e, n, k, L):
two_e, x, out = pow(2, e, n), c * pow(k, e, n) % n, []
for _ in range(L):
out.append(x)
x = x * two_e % n # multiplies the plaintext by 2
return outAnswer j is popcount(k·2^j·m mod n).
- Pipeline the batch. All L decimal integers are joined with \n, pushed by a daemon writer thread in 256 KB chunks while the main loop
recv()s and scans with re.findall(rb"\d+", buf.replace(b"x> ", b" ")), the x> prompt is stripped before the digit scan so prompts are not mistaken for answers. Three chains k = 1, 3, 5 → 3 × 2051 = 6153 queries (or 3 × 2050 = 6150). ~3.8 MB sent, ~50 KB received. - Convert popcounts to wrap bits.
measured[j] = 1 if pc[j+1] != pc[j] else 0A 1 is proof of a wrap; a 0 is "no wrap" with ~0.84 % error, always in the direction of a missed 1.
- Beam search over A = floor(2^i · m / n). Chain k = 1 drives the branching: if measured[i] == 1, bit i+1 of m/n is forced to 1 (single child 2A+1); if 0, both children are kept, with +1 penalty on the 2A+1 child (that would mean a hidden wrap). Chains k = 3, 5 cross-check. For a candidate B at depth i+1, m/n ∈ [B/2^(i+1), (B+1)/2^(i+1)), so k·2^(j+1)·m/n ∈ [kB/2^s, (kB+k)/2^s) with s = s₀ = k.
bit_length()+1 and j = i − s₀. The chain bit is determined iff the interval does not straddle a 2^s boundary:
determined ⟺ (k*B >> s) == ((k*B + k - 1) >> s)
pred = (k*B >> s) & 1(upper endpoint kB+k−1, not kB+k, because [A, A+1) with integer A cannot straddle a 2^s boundary for s ≥ 1, this test is tight, not merely conservative). Then:
- measured == 1 and pred == 0 → prune (sound: a change proves a wrap);
- pred == 1 and measured == 0 → penalty += 1 (a plausible hidden wrap).
Survivors are sorted by penalty and kept if pen <= best + 40, capped at beam_width = 600.
- Interval → integer. Each surviving A gives lo = ceil(A·n / 2^nbits); candidates lo−1 … hi are emitted and deduped. The correct m is the unique candidate satisfying pow(m, e, n) == c. Live runs emitted 876 and 1125 candidates at beam=600 gap=40 and hit m on the first beam pass.
- Submit m on the same socket and regex the flag out of the reply (rb"[A-Za-z0-9_]\{[^}]\}").
Validation before touching the remote (offline, ranktest.py, RSA-2048, k = 1,3,5, beam 600): the true candidate never fell below rank 2 with a penalty gap ≤ 1–2, and the beam search itself ran in ~1.1 s. A 9-agent adversarial review confirmed the math: the shift invariant held over 1,165,890 exhaustive (y, n) pairs with 0 violations, and the wrap identity over 30,608,640 cases for k ∈ {1,3,5,7,9} with 0 mismatches. Under-provisioned configs were also measured: k = 1,3,5 at beam 150 → 3/3 (rank ≤ 6), but k = 1,3 at beam 2000 → 1/3.
Run log.
- Local end-to-end (--local against a spawned
prob.py): m recovered, FLAG: BHFlagY{local_test}, 98.7 s total. - tcp.flagyard.com:23476, run 2 (
solve2.py): chain k=1 350 s, k=3 721 s, k=5 1082 s; beam=600 gap=40 - > 876 candidates; BHFlagY{...} in 1082 s.
- tcp.flagyard.com:19546: beam=600 gap=40 -> 1125 candidates; BHFlagY{...} in 1021 s.
Stream-integrity check on the raw dump (chain k=1, 2047-bit n): 2050 entries as expected; popcounts min 954 / max 1117 / mean 1022.0 / sd 22.7 against the expected 1023.5 / 22.6; zero out-of- range values (a truncated read would surface as a tiny value like 10); proven wraps 990/2049 = 0.483 against the ~0.495 expected, the 0.012 shortfall is the hidden-wrap rate, matching the independently measured 0.84 %.
Key code def chain_queries(c, e, n, k, L): """x_j = c * k^e * (2^e)^j -> oracle answers popcount(k*2^j*m mod n).""" two_e, x, out = pow(2, e, n), c * pow(k, e, n) % n, [] for _ in range(L): out.append(x) x = x * two_e % n return out
def measured_bits(popcounts):
"""popcounts[j] = popcount(k*2^j*m mod n) -> measured wrap bits (one-sided)."""
return [1 if popcounts[j + 1] != popcounts[j] else 0
for j in range(len(popcounts) - 1)]
def beam_search(n, mbits, beam_width=600, max_penalty_gap=40, progress=None):
"""mbits: {k: [measured wrap bits]} for odd multipliers k (1 must be present)."""
nbits = n.bit_length()
checks = [(k, k.bit_length() + 1) for k in sorted(mbits) if k != 1]
drive = mbits[1]
cands = [(0, 0)] # (penalty, A) with A = floor(2^i*m/n)
for i in range(nbits):
nxt = []
mb = drive[i] # true bit i+1 of m/n, one-sided
for pen, A in cands:
kids = [(pen, 2 * A + 1)] if mb else [(pen, 2 * A), (pen + 1, 2 * A + 1)]
for p, B in kids:
ok = True
for k, s0 in checks:
j = i - s0
if j < 0:
continue
s = s0
u = k * B
if (u >> s) != ((u + k - 1) >> s):
continue # not yet determined by this candidate
pred = (u >> s) & 1
m_ = mbits[k][j]
if m_ and not pred:
ok = False # sound prune: a change PROVES a wrap
break
if pred and not m_:
p += 1 # plausible hidden wrap
if ok:
nxt.append((p, B))
nxt.sort(key=lambda t: t[0])
best = nxt[0][0]
cands = [t for t in nxt if t[0] <= best + max_penalty_gap][:beam_width]
out, seen, res = [], set(), []
for pen, A in cands:
lo = (A * n + (1 << nbits) - 1) >> nbits
hi = ((A + 1) * n + (1 << nbits) - 1) >> nbits
for m in range(max(lo - 1, 0), hi + 1):
out.append((pen, m))
for pen, m in out:
if m not in seen:
seen.add(m); res.append(m)
return res # caller keeps the one with pow(m, e, n) == c04Dead ends
- Self-inflicted kill on the first remote run. The exploit was launched under timeout 900; the output file's last write was at exactly 914 s after start, i.e. SIGTERM landed at ~5900/6153 answers, roughly 40 s from done. Because every connection draws a fresh m, this cost a complete re-run. Fixed by raising
the wrapper to timeout 3000 and dumping raw popcounts to answers.json after each chain so the analysis phase is reproducible offline (--replay). • A "stalled" run that wasn't. The exploit's stdout was piped through grep -v, which block-buffers; the output file sat at one line for 15 minutes. Misread as a hang until /proc/<pid>/io and ss -tni were checked: bytes_sent / bytes_acked = 3,798,645/3,798,646 (all queries delivered), bytes_received climbing, lastrcv 108 ms. The hardened runner writes unbuffered progress straight to stderr instead. • Instance TTL, not a per-connection cap. tcp.flagyard.com:13490 reset the connection at ~570 s mid-chain-3 (ConnectionResetError: [Errno 104]); a follow-up probe got ConnectionRefused, proving the container had expired rather than enforcing a session limit. Since the attack needs ~17 min of query time at ~6.1 answers/sec, a fresh instance was required and had to be attacked immediately on spawn. • The 2-chain shortcut does not exist. Tested against the real saved popcounts from a solved run: k=1,3 failed at beam 600, 5000 and 20000 (42,867 candidates, none satisfying m^e ≡ c); only k=1,5 at beam 5000 recovered, on a single sample, luck, not reliability. Consistent with the offline stress result of 1/3 for k=1,3 at beam 2000. The third chain is load-bearing; ~1 query per recovered bit per chain is essentially the information-theoretic floor for this oracle. • Defects found by the 9-agent adversarial review (all robustness/efficiency, none affecting soundness): best = nxt[0][0] is unguarded, so an emptied beam raises an opaque IndexError instead of a clean failure (reproduced with beam_width=1, max_penalty_gap=0 on a 64-bit modulus); each cross- check chain bit is tested at exactly one depth s₀ and discarded if undetermined there, throwing away 543,513 of 2,571,038 = 21.2 % of available cross-check information; the interval→integer step emits 3 candidates where m == lo always (0 counterexamples over 210,677 exhaustive pairs plus 20,000 random cases at 64/512/2048 bits), tripling the 2048-bit modexp verification cost; and structured m (n−1, n−2, n−4, (n−1)//2, n//3) inflate hidden wraps ~10× and push the true candidate to rank 10239, defeating the beam heuristic but never the pruning rule, irrelevant here since prob.py uses secrets.randbelow(n). The network reviewer separately flagged no socket timeout, a header parser assuming e/n/c are the first three lines, and a \d+ scan that can return a digit-truncated final answer at a recv() boundary (harmless here: it can only touch the last chain entry, which sits two indices past anything the beam search reads). • beam_search raises KeyError: 1 when the driving chain is absent, hit while sweeping a k=3,5 config. • zsh does not word-split unquoted expansions, so for cfg in "1,3 600 40"; do python3 cfgtest.py $cfg passed one argument; needed ${=cfg}.