Shamir's Secret Challenge Scenario — HackTheBox

Description

No organizer description was included in the local challenge files.

The service returns 64 share-looking pairs for each encryption, but only 32 are genuine evaluations of a secret-sharing polynomial. The remaining 32 pairs are uniformly random noise, and the flag can be requested only once, so the whole problem is to separate real shares from fake ones and then recover the constant term modulo 2^1024.

Challenge Overview

The core server logic is:

N = 2**1024
poly = [msg] + [getrandbits(1024) for _ in range(31)]

if key & 1 << bitpos != 0:
    out += ((x, doeval(poly, x)),)
else:
    out += ((x, y_random),)

So each encryption produces:

• 64 total pairs,
• exactly 32 real shares,
• exactly 32 fake pairs,
• a degree-31 polynomial,
• arithmetic modulo 2^1024.

This looks like Shamir secret sharing at first glance, but the modulus is not prime, so the usual interpolation formulas over a field are not automatically valid.

Analysis

1. Why zero plaintext reveals the real-share positions

For a chosen message m = 0, the polynomial becomes:

f(x) = a1*x + a2*x^2 + ... + a31*x^31 = x*g(x)

Therefore every real share satisfies:

y = f(x) = x*g(x) mod 2^1024

Over a power-of-two modulus, that implies the 2-adic valuation of y is at least the 2-adic valuation of x unless wraparound destroys only higher powers of two, which still preserves the low-bit divisibility condition used here. In practical terms, if x is divisible by 2^t, then every real y must also be divisible by 2^t.

The solver uses this distinguisher:

def v2(x):
    return 1024 if x == 0 else (x & -x).bit_length() - 1

for i, (x, y) in enumerate(shares):
    t = v2(x)
    if t and (y & ((1 << t) - 1)):
        possible.discard(i)

Random fake pairs do not preserve that divisibility relation, so repeated encryptions of the zero message quickly eliminate fake positions. After enough rounds, exactly 32 indices remain, and those indices are the real-share mask for the session.

2. Why normal Lagrange interpolation is the wrong tool

In standard Shamir secret sharing, interpolation is done over a field, usually GF(p). Here the ring is Z / 2^1024 Z, which has many zero divisors. Differences like (x_i - x_j) are frequently even and therefore non-invertible, so the usual Lagrange denominators cannot be inverted reliably.

That means the problem is better viewed as a modular linear system:

V * c = y  (mod 2^1024)

where V is the Vandermonde matrix built from the 32 real x values and c is the coefficient vector. The flag is the constant coefficient c0.

3. HNF reconstruction over Z/(2^1024)

The solve script constructs the augmented integer matrix:

[ V | N * I ]

with N = 2^1024, computes a column Hermite normal form and the associated unimodular transform, solves on the pivot block, and maps the solution back to a valid coefficient vector modulo N.

The important code is:

augmented = flint.fmpz_mat([
    row + [N if i == r else 0 for i in range(32)]
    for r, row in enumerate(rows)
])
hnf_t, transform = augmented.transpose().hnf(transform=True)
column_hnf = hnf_t.transpose()
unimod = transform.transpose()

This avoids illegal field assumptions and gives one valid solution vector in the ring. The first entry of that vector is the plaintext integer.

Solution

1. Connect to the service and repeatedly request encryptions of the zero byte.
2. For each of the 64 positions, test whether v2(y) >= v2(x) holds in the low bits.
3. Eliminate positions that violate the condition on any round.
4. Once 32 stable positions remain, request the flag encryption once.
5. Keep only the 32 pairs from those real positions.
6. Build the Vandermonde system modulo 2^1024.
7. Solve it with the HNF-based method from python-flint.
8. Convert the recovered 1024-bit integer to bytes and extract the HTB{...} substring.

The final remote exploit command was:

python3 "tasks/hackthebox/Shamir's Secret Challenge Scenario/crypto_shamirs_secret/solve.py" 154.57.164.74 31107

The local solver was also self-tested before the remote run:

python3 "tasks/hackthebox/Shamir's Secret Challenge Scenario/crypto_shamirs_secret/solve.py" --self-test

Implementation Notes

• The real/fake mask is session-specific, so the zero-message probes and the single flag request must happen on the same connection.
• The server returns exactly 32 real shares for a degree-31 polynomial, so recovering the correct mask gives just enough equations.
• The recovered plaintext is a 1024-bit integer, not a short string directly, so the script converts it to 128 bytes and searches for the flag pattern inside the byte string.