Shamirs Secret

Technical Walkthrough

Writeup

Challenge

• Name: Shamirs-Secret
• Category: Crypto
• Difficulty: Medium
• Mode: hybrid

Summary

The service is a custom Shamir-like encryption oracle. It hides each message as the constant term of a degree-31 polynomial modulo 2^1024, then prints 64 shares where only 32 fixed positions are real and the rest are random fakes. The key mistake is that the real/fake selector key is fixed for the whole connection and known plaintexts leak which positions are real through 2-adic divisibility. Once the real flag shares are known, manual power-of-two Lagrange interpolation recovers the flag from the low bytes of the constant term.

Artifact Inventory

Reference analysis/artifact-inventory.json and summarize the relevant files or remote surface.

• Original archive: files/a12c7378-2f66-4268-9c4e-cce9f3af293d.zip
• Extracted source: files/extracted/crypto_shamirs_secret/server.py
• Source copy used for audit: analysis/source/server.py
• Remote service used for final rerun: <TARGET>:30089
• Prior instance also tested: <TARGET>:31869
• Solver: solve/solve.py
• Remote classification evidence: analysis/remote/key-classification-<TARGET>-30089.tsv

Analysis

The source in analysis/source/server.py sets N = 2**1024, generates a 64-bit key with exactly 32 bits set, and keeps that key for the server process. For each encryption it creates a new polynomial:

poly = [msg] + 31 random 1024-bit coefficients

For key-bit positions, the service outputs real evaluations (x, f(x) mod N). For the other positions, it outputs random (x, y) pairs.

The first exploit step is position classification. For a known plaintext msg, any real share has:

y = msg + x*c1 + x^2*c2 + ...

If x has 2-adic valuation t = v2(x), every non-constant term is divisible by 2^t, so a real share always satisfies:

y - msg == 0 mod 2^t

Fake shares are random and fail this check repeatedly. The remote run recorded the final classification in analysis/remote/key-classification.tsv.

After reducing the flag output to the 32 real shares, ordinary Shamir interpolation over a finite field is not valid because 2^1024 is not prime and many Lagrange denominators are even. The solver handles this by using a common denominator over the integers, separating the denominator into an odd part and a power-of-two part. It inverts the odd part modulo a widened modulus, then divides out the remaining power of two. A local self-test for this exact interpolation path is saved in analysis/local-self-test.txt.

The interpolated representative can contain ambiguous high bits, but the low bytes contain the true constant term. The solver therefore prefers a platform flag match that ends at the end of the recovered bytes, falling back to the last match if needed.

Solve

Run:

python3 Crypto/Shamirs-Secret/solve/solve.py --self-test
python3 Crypto/Shamirs-Secret/solve/solve.py --host <TARGET> --port 30089 --samples 96
python3 scripts/challenge_harness.py capture-flag Crypto/Shamirs-Secret --from loot/flag-candidate.txt

The solver:

1. Sends repeated encryptions of 00 to classify real and fake positions.
2. Requests the flag encryption once.
3. Keeps only the real flag shares.
4. Performs widened 2-adic Lagrange interpolation.
5. Extracts the suffix flag bytes and writes them to loot/flag-candidate.txt.

Flag

Raw flag is stored in loot/flag.txt and intentionally not reproduced here.

Lessons

• Shamir-style interpolation assumptions break when the modulus is not a field. For a power-of-two modulus, separate odd and 2-adic denominator factors instead of trying to invert everything.
• A fixed real/fake share selector across chosen plaintext and flag encryption turns fake-share filtering into a statistical known-plaintext problem.
• For polynomial evaluations modulo 2^k, v2(x) gives direct divisibility constraints on the lower bits of the constant term.
• Keep the remote interaction bounded: this solve only needed enough known-message encryptions to classify the fixed positions, followed by one flag encryption.

Source-Backed Dossier

The sections below are merged from companion Markdown notes for the same case. They are rendered after sanitization so the article stays precise without publishing raw flags, credentials, or target-specific secrets.

Notes

Scope

• Challenge: Shamirs-Secret
• Category: Crypto
• Difficulty: Medium
• Mode: hybrid
• Remote instance: latest rerun <TARGET>:30089; prior solved instance <TARGET>:31869
• Start time: 2026-06-13T06:37:42Z
• Operator: harness
• State file: challenge-state.json

Harness Status

• Current phase: see challenge-state.json
• Next allowed actions: see next-action.json
• Raw flags and sensitive material stay in loot/ only. Do not paste them here.

Artifact Inventory

Evidence Ledger

Key Findings

• server.py implements a Shamir-like scheme over N = 2^1024, not a prime field.
• Each encryption emits 64 (x, y) pairs. The fixed process key marks exactly 32 positions as real polynomial evaluations and 32 as fake random pairs.
• For a known plaintext, a real share satisfies y - msg == 0 mod 2^v2(x). Fake shares fail this divisibility check often enough to classify positions after repeated chosen-message encryptions.
• The flag encryption can then be reduced to the 32 real shares. Standard field interpolation does not apply directly because the modulus is a power of two.
• solve/solve.py uses common-denominator Lagrange interpolation, inverts only the odd denominator part, divides the remaining power of two in a widened modulus, and extracts the HTB-format flag from the low bytes of the recovered representative.
• After the target changed, the solver was tightened to prefer a flag pattern that ends at the end of the recovered bytes, then rerun against <TARGET>:30089.

RAG / Advisory Memory

RAG output is advisory only. Record evaluated retrievals with:

scripts/challenge_harness.py rag-record <workspace> --query "..." --tag MATCHED|PARTIAL|MISSING|<secret redacted>|GENERIC --validation "..."

Secrets/Flags

Raw flags and sensitive material stay in loot/ only. Use scripts/challenge_harness.py capture-flag to validate and record flag capture without printing the value.

Memory Summary

Metadata

• Platform: HackTheBox Challenges
• Category: Crypto
• Challenge: Shamirs-Secret
• Difficulty: Medium
• Source workspace: <local workspace>

Validated Solve Chain

Concepts only. Do not include raw flags, reusable credentials, tokens, cookies, private keys, or live secrets.

1. Source showed a custom Shamir-like scheme over 2^1024, with 64 emitted pairs but only 32 fixed key-selected real polynomial evaluations.
2. Known plaintexts identify real positions because real shares satisfy y - msg == 0 mod 2^v2(x) while fake random pairs eventually fail.
3. After classifying the fixed positions, request the flag once and keep only the 32 real flag shares.
4. Recover the constant term with common-denominator Lagrange interpolation adapted to a power-of-two modulus: invert the odd denominator part modulo a widened modulus, then divide the remaining power of two.
5. The representative's low bytes contain the true message; prefer a flag-pattern match at the end of those bytes to avoid accidental high-byte matches.

Reusable Lessons

• For Shamir-like schemes over 2^k, non-field interpolation can still be usable if the denominator is handled as odd part plus 2-adic part.
• Fixed real/fake share positions across encryptions turn chosen plaintexts into a classifier.
• Local self-tests are valuable before remote attempts because interpolation can look mathematically plausible while still mishandling modular division.

Dead Ends

• Ordinary finite-field interpolation modulo 2^1024 was not valid because even denominators are not invertible.
• Private CTF RAG had no matching prior memory for this exact challenge, so it was treated as source-first.

Tool Quirks

• Local macOS lacked Sage, SymPy, and Z3, but the attack did not require them; pure Python integer arithmetic was enough.

Evidence Paths

• analysis/source/server.py
• analysis/local-self-test.txt
• analysis/remote/key-classification.tsv
• solve/solve.py
• loot/flag.txt

Ingestion Decision

• Proposed for LightRAG: yes
• Requires user approval before ingestion: yes

Hypothesis Board

Keep no more than 3 active hypotheses on Easy/Medium and 5 on Hard unless the user explicitly asks for breadth.

Closed Branches