Shamir recovery: corrupted/insufficient shares silently return a wrong secret (no integrity check)

[pk009900]

pybtc Shamir Secret Sharing — Share-Integrity / Recovery-Path Bug Report

Bounty: Shamir Secret Backup Scheme (bitaps)
Category: Loss of access / inability to recover the original mnemonic (0.1 BTC tier)
Primary target: bitaps-com/pybtc — pybtc/functions/shamir.py
Also affects (same code, inherited): pybgl, pyltc, pybch (all pybtc-derived)

---

TL;DR

restore_secret() performs Lagrange interpolation over whatever shares it is
given and returns the result unconditionally. No checksum or digest binds
the shares to the secret. Consequently a single corrupted or mis-paired share
silently yields a wrong secret with no error and no way to identify the
faulty share — the exact loss-of-access failure mode this bounty names for a
mnemonic-backup tool. This report does not claim a threshold break; below-
threshold recovery is information-theoretically secure (demonstrated as a
control). It is a correctness/integrity bug in the recovery path.

---

Scope note (what this is NOT)

• This is not a sub-threshold compromise. With 2 of 3 required shares the
  secret remains uniform over all 2^128 values; verified in negative_proof.py
  (conditional entropy = 8.000 bits/byte). The 1 BTC challenge (3-of-5, 2 shares
  published) is unaffected by any finding here.
• This is not the coefficient-generation bias of issue Generation of polynomial coefficients in Sharmir's secret sharing #23 — that is fixed in
  pybtc (CSPRNG + NIST SP 800-22 tests in entropy.py). See "Prior art" below.

---

Findings

Issue 1 (significant) — single corrupted/mis-paired share → silent wrong secret

restore_secret() has no integrity check binding shares to the secret. Flip one
byte of one otherwise-valid share and recovery returns a different value with no
error raised.

clean recovery   : 102030   (== secret)
one byte flipped : c92030   <-- WRONG, no error

For a seed-backup tool this means a user holding the correct number of shares
can still permanently lose their wallet if one share has a single-character
transcription error — and gets no signal that anything is wrong, nor which share
is at fault.

Severity nuance (honest): if the caller re-encodes the recovered 16 bytes to
a BIP-39 mnemonic, the 4-bit BIP-39 checksum catches a wrong reconstruction
~93.75% of the time (1 - 1/16). So the silent-failure window is roughly 1-in-16
when mnemonic re-encoding is used, but 100% silent when restore_secret() is
consumed raw (which the API permits). The fix below closes the window entirely
and identifies which share is bad, which the BIP-39 checksum cannot do.

Issue 2 (minor) — too-few shares returns a wrong value silently

No threshold metadata is stored with shares, so recovering a 3-of-5 secret with
only 2 shares does not raise — it returns a confident, wrong value. The library
cannot warn that recovery was under-determined.

Issue 3 (robustness) — duplicate x-coordinates raise an uncaught ZeroDivisionError

Passing colliding share indices hits the (x_j - x_m) = 0 denominator in
interpolation and raises a raw ZeroDivisionError rather than a clean
"duplicate share index" validation error.

---

Reproduction

Note on installation: pybtc 2.3.11 does not build on Python 3.11+. Its
C extension pybtc/bitarray/_bitarray.c assigns to Py_SIZE() / Py_TYPE(),
which became non-assignable macros in CPython 3.11 (must use Py_SET_SIZE /
Py_SET_TYPE). So pip install pybtc fails to compile on any current Python.
The Shamir functions are pure Python with no dependency on that extension,
so the finding was verified against shamir.py reproduced verbatim.

python3 repro_standalone.py     # no install, no C build required

Expected output (reproduced on a clean machine):

=== Issue 1: corrupted share -> silent wrong secret ===
  clean recovery  : 102030 (expected 102030)
  one byte flipped: c92030 <-- WRONG, no error
=== Issue 2: too few shares -> silent wrong value ===
  recover 2 of 3  : 7bdfd5 <-- WRONG, no error
=== Issue 3: duplicate x -> uncaught ZeroDivisionError ===
  ZeroDivisionError raised instead of clean validation error

repro_standalone.py vendors pybtc's shamir.py logic verbatim (GF(256),
_interpolation, restore_secret); only generate_entropy() is replaced by a
seeded RNG for determinism (the entropy source is irrelevant to these bugs).
Diff it against the upstream file to confirm the logic is identical. Scripts
restore_audit.py and negative_proof.py contain the full recovery-path audit
and the sub-threshold-security control, respectively.

---

Verification caveat

pybtc 2.3.11 cannot be pip-installed on Python 3.11+ (C extension build failure,
see Reproduction). Behaviour was therefore confirmed against shamir.py
reproduced verbatim in repro_standalone.py, run on a clean machine with the
output shown above. To verify on the shipped source, diff the vendored functions
against the upstream shamir.py, or install pybtc under Python <= 3.10 where the
C extension still builds.

---

Suggested fix

Adopt SLIP-0039-style integrity:

1. Bind shares to the secret with a digest/checksum so restore_secret()
   detects a corrupted or mismatched share set and refuses rather than
   returning a wrong secret. This is the core fix for Issue 1.
2. Store threshold metadata with the share set so supplying too few shares
   is a detectable error (Issue 2).
3. Validate that share indices are distinct before interpolating, with a
   clear error message (Issue 3).

---

Prior art checked (due diligence)

To avoid filing duplicates, the following were reviewed:

• pybtc Generation of polynomial coefficients in Sharmir's secret sharing #23 (onvej-sl, coefficient-generation bias (a*i)%255): fixed.
  Replaced with CSPRNG + NIST SP 800-22 tests. Not re-reported here.
• jsbtc Critical Vulnerability in SSSS Implementation: Missing Prime Modulus and Use of Non-Prime Modulus (2²⁵⁶)** --- #43, Potential Key Recovery and Integrity Risks in Shamir Secret Sharing Code #47 (non-uniform / rejection-sampling coefficient bias) and
  Shamir's secret sharing and security vulnerabilities #42 ("never 255" defect): these cover the coefficient-generation family
  in the JS library. The jsbtc __split_secret distinctness leak
  (while (q.includes(w))) was independently reproduced and confirmed to match
  Potential Key Recovery and Integrity Risks in Shamir Secret Sharing Code #47 — it is therefore not re-reported here. (It is also a low-yield,
  high-threshold-only leak: ~0.27 bits over 128 at the challenge's 3-of-5.)
• The present integrity finding is in the recovery path, a different class
  from all of the above, and was not observed among the open pybtc/jsbtc issues
  at time of writing. Please confirm against the pybtc tracker before triage.

Affected library family

The vulnerable restore_secret() ships in pybtc and is inherited by its forks
pybgl, pyltc, and pybch (all "based on pybtc"). A single fix in the shared
shamir.py propagates to all four. This breadth is noted not to inflate the
finding but because a recovery bug replicated across four shipped wallet
libraries is materially more impactful than one confined to a single repo.

---

Reward

If accepted, I will provide a payout address privately on request (e.g. via
GPG-signed email, as was done for issue #23). No address is included in this
public report, to prevent spoofing or interception of the reward.

pybtc_shamir_bug_report_1.zip

[pk009900]

[pk009900]

@4tochka @C0ffe1n have a look