Usama Arshad. Résumé

Challenge 2 of 15 Crypto Full writeup

BlackHat MEA 2026 · Qualifiers

Popcnt Oracle.

Poping Shower!

Crypto· 4 November 2026

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.

Captured

01Recon

The archive contained a single 510-byte prob.py (local copy at /home/kali/Desktop/CTF/Crpto/ popcnt_oracle.tar.gz/prob.py):

python
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:

snippet
e = 65537
n = 13865772848690584914911522440805572816742770820957440571 ... [621 chars]

c = 10642851944200752564572311993873177781358910079411299649 ... [621 chars]
x>

02The bug

Two composed flaws.

  1. 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
snippet
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,

snippet
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

EXPLOIT RELIABILITY 99% LOCALLY. REMOTE IS A DIFFERENT STORY.

2,051 QUERIES LATER, ALL 2,048 BITS OF IT

03Exploitation

  1. 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).
  2. 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:
python
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 out

Answer j is popcount(k·2^j·m mod n).

  1. 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.
  2. Convert popcounts to wrap bits.
snippet
measured[j] = 1 if pc[j+1] != pc[j] else 0

A 1 is proof of a wrap; a 0 is "no wrap" with ~0.84 % error, always in the direction of a missed 1.

  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:
snippet
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.

  1. 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.
  2. 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

python
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) == c

04Dead 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}.