Usama Arshad. Résumé

Challenge 1 of 15 Crypto Full writeup

BlackHat MEA 2026 · Qualifiers

Hokan.

...Wait, 8 queries?

Crypto· 4 November 2026

TL;DR

Reconstruct a secret 11-variable degree-11 polynomial over an unknown 256-bit prime field from only 8 evaluations, two fewer than Prony interpolation nominally requires, by choosing query points whose structure makes the integer kernel depend only on the exponents.

Captured

01Recon

The whole service is five lines of Sage:

python
R = PolynomialRing(Zmod(random_prime(2^256)), 11, "x")
f = R.random_element(degree=11)
for _ in range(8):
    v = list(map(int, input("> ").split(",")))
    print(f(*v))
if str(f) == input("> "):
    print(flag)

You must print str(f) exactly, Sage's degrevlex string form, coefficients and all, after only 8 evaluations, and the modulus p is never revealed.

MPolynomialRing_base.random_element(degree=11) with terms=None sets terms = 5. Because 5 < total/2 it draws exactly 5 distinct exponent tuples uniformly from the C(22,11) = 705,432 monomials of total degree at most 11 in 11 variables, each with a uniform coefficient in [0,p).

Counting unknowns: p (256 bits) + 5 monomials (~87 bits) + 5 coefficients (1280 bits) ≈ 1633 bits, against 8 x 256 = 2048 bits of oracle output. Information-theoretically feasible, but the textbook Prony / Ben-Or–Tiwari route needs 2T = 10 queries for T = 5 terms, so it does not fit. The attack has to be near information-optimal.

02The bug

The bug is a budget bug rather than a memory bug: the author assumed 8 evaluations of a 5-term polynomial over a secret modulus is under the interpolation threshold. It is not, provided the query points are chosen with structure instead of at random.

The structural fact that breaks it: if every query point is a scalar power-family of one weight vector, the integer left kernel of the evaluation matrix depends only on the multiset of exponent inner products, not on the coefficients and not on p. That kernel is spanned by the coefficient vectors of the locator polynomial, so a correct guess at the node set produces a relation that is an exact integer multiple of p. The unknown modulus stops being an obstacle and becomes the thing you extract.

03Exploitation

  1. Queries 1–7, a Prony family with a small node set. Send v_k = (2^(k*w_1)..., 2^(k*w_11)) for k = 0..6, with w = (1,2...,11). Then
snippet
f(v_k) = SUM_i c_i * X_i^k   (mod p),   X_i = 2^(E_i),    E_i = <a_i, w> in [0,121]
  1. Extract p. For the true node multiset, the locator L(z) = PROD (z - X_i) and z*L(z) both annihilate the responses over the integers modulo p:
snippet
SUM_k L_k * r_k = 0,  SUM_k L_k * r_{k+1} = 0       (mod p)
     => gcd(., .) = small * p

E_i lives in [0,121], so enumerate all C(122,5) = 2.2e8 node sets (enum.c, GMP + OpenMP, ~20 s windowed / ~100 s full on 8 cores). The correct set yields a ~256-bit gcd; every wrong set yields a tiny one. No false positives were observed.

  1. Recover the individual coefficients. With p and the nodes known, a Vandermonde solve on the same 7 responses gives each c_i separately. This is the step that makes the last query affordable, and it is why the weight vector must separate the monomials.
  2. Query 8, one prime point gives the exponent vectors. Send v = (2,3,5,7,11,13,17,19,23,29,31):
snippet
r_8 = SUM_i c_i * m_i     (mod p),   m_i = PROD_j q_j^(a_ij)

Each m_i < 31^11 ~ 2^54.5 and is typically ~2^36, so SUM log2(m_i) ~ 180 << 256. With c_i and p already known this is a low-density modular knapsack, solved by LLL in dimension 7. Factor each recovered m_i over the 11 primes and the entire exponent vector falls out at once.

  1. Cross-check and format. Validate against <a_i, w> = E_i, total degree ≤ 11, and a replay of all 8 responses; then rebuild str(f) in Sage's degrevlex order (fmt.py, validated byte-for-byte against 300 real Sage polynomials) and send it.

04Dead ends

  • The single failure mode is an exponent collision: two monomials sharing the same <a, w>. Exact probability 16.9% by dynamic programming over the monomial set. It is detected cleanly, a collision makes every 5-subset containing the 4 true nodes annihilate, so you get many gcd hits and a zero coefficient, so the correct response is simply to reconnect.
  • Wider weight vectors cut collisions to ~6% but cost 200x more enumeration, so w = (1..11) minimises total expected work.
  • Measured success: 91/100 against the simulator, 4/4 first-shot against real Sage.

THE AUTHOR BUDGETED 8 QUERIES FOR A 10-QUERY ATTACK

6 HOURS 4 HOURS THE ONE THAT WORKED

SO WE STOPPED QUERYING AT RANDOM