cryptofreehard

Shamir's Secret Challenge Scenario

hackthebox

Task: recover a secret hidden as the constant term of a degree-31 polynomial modulo 2^1024, mixed with 32 random fake shares. Solution: distinguish real shares with a 2-adic valuation test on zero encryptions, then reconstruct the secret with an HNF-based solver over Z/(2^1024).

$ ls tags/ techniques/
chosen_plaintextpolynomial_interpolationshamir_secret_sharingpower_of_two_modulusfake_shares2_adic_valuationmodular_linear_algebra
real_share_distinguishingchosen_plaintext_zero_probehnf_based_modular_reconstructioninterpolation_over_zmod_2k

$ cat /etc/rate-limit

Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.

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

...