Quantified entropy loss from coefficient-distinctness bug (ref: #23, #73)

[mrnomi07]

Cryptanalysis of the Bitaps Shamir Secret Sharing Bug Bounty Challenge
Target: bc1qyjwa0tf0en4x09magpuwmt2smpsrlaxwn85lh6 (1 BTC), zpub zpub6qdEDkv51FpxX6g1rpFGckmiL46vV8ccmtEgPAkj3qj8N4ZZHyXDRA9RwpTiFK2Kb8vRaDmSmwgX6rfB4t2K8Ktdq8ExQ6fumKpn2ndJCqL
Scheme: 3-of-5 Shamir Secret Sharing over GF(256), applied byte-wise to a 12-word (128-bit) BIP39 mnemonic
Reference implementation: bitaps-com/pybtc/pybtc/functions/shamir.py, bitaps-com/jsbtc/src/functions/shamir_secret_sharing.js
Status of target address: unspent since August 2021 (as of this analysis)

1. Summary
   This report evaluates whether the two publicly disclosed shares for the Bitaps Shamir Secret Sharing bug bounty challenge are sufficient — alone, or combined with the known implementation weaknesses in pybtc/jsbtc — to recover the third share and reconstruct the original 12-word mnemonic.
   Conclusion: No practical break exists using currently public information. The core GF(256) Lagrange-interpolation implementation in shamir.py/shamir_secret_sharing.js is correct and provides information-theoretic security as designed: with only 2 of 3 required shares, every possible secret byte remains algebraically consistent with the known data. The one confirmed implementation weakness (a rejection-sampling bug that forces polynomial coefficients to be pairwise distinct) leaks only 0.27 bits of the 128-bit secret (measured directly against the two published challenge shares — see §4), which is negligible against the remaining ~127.7 bits of entropy. This does not materially assist an attacker even when combined with BIP39 checksum pruning.
   This finding does not identify a new vulnerability. It is a precise, reproducible re-confirmation and quantification of the weakness already reported in pybtc#23 (2021) and restated in pybtc#73 (2026), measured directly against the live challenge data rather than described abstractly.

---

2. Method
   2.1 Share decoding
   The two published shares are encoded as standard-looking 12-word BIP39 mnemonics, but per the scheme's own specification (mnemonic-improvement.md), the 4 bits normally reserved for the BIP39 checksum are repurposed to encode the share's GF(256) x-coordinate (share index), since the standard checksum is deemed cryptographically redundant. For a 12-word mnemonic this yields 4 index bits → indices in the range 1–15, matching the "12 words → 15 total shares max" table in the spec.
   Decoding:
   Share Words Payload (16 bytes) Index (x)
   1 session cigar grape merry useful churn fatal thought very any arm unaware c4451d9745defe5194e707f2e1442ef6 3
   2 clock fresh security field caution effort gorilla speed plastic common tomato echo 2b6b9b0b2af24a8d592e88a605cf9022 15
   Each byte position i of the two payloads gives one point (x, y_i) on an independent degree-2 polynomial f_i(x) = s_i + a1·x + a2·x² over GF(256), where s_i is the i-th secret byte.
   2.2 GF(256) arithmetic
   Reimplemented shamir.py's field arithmetic exactly (same reduction polynomial 0x11B, same exp/log tables) and validated Lagrange interpolation against synthetic test vectors before applying it to challenge data.
   2.3 Candidate secret enumeration
   For threshold 3, two known points give 2 equations in 3 unknowns (s, a1, a2) — algebraically underdetermined. For each of the 256 possible values of s, the corresponding (a1, a2) is uniquely solvable via a 2×2 linear system in GF(256). Absent additional constraints, all 256 values of s are equally valid — this is the intended information-theoretic guarantee of Shamir's scheme at t-1 shares.
   2.4 The distinctness bug
   The reference split-generation loop (both Python and JS versions) draws each polynomial coefficient via rejection sampling that rejects any value already used elsewhere in the same polynomial:

do {
    w = e[ePointer++];
} while (q.includes(w));   // reject if value already chosen
q.push(w);

This guarantees, for every byte's polynomial: secret ≠ a1, secret ≠ a2, a1 ≠ a2. This is a real, structural deviation from uniform coefficient sampling and was first reported in pybtc#23 (2021).
Applying this as a filter to the 256 candidate secrets per byte (discarding any s whose implied a1/a2 violate the distinctness constraint) was tested against the actual two published shares.

3. Ruled-out hypotheses
   Before quantifying the known bug, the following stronger attack vectors were investigated and ruled out:
   Weak/predictable PRNG in generate_entropy(): confirmed (via direct inspection of the published pybtc 2.3.11 source on PyPI) to use random.SystemRandom(), which draws from the OS CSPRNG. No seed-recovery or state-prediction attack applies.
   Modulus/range bias in generate_entropy(): the function draws a uniformly from [0, SECP256K1_ORDER] and truncates to bytes. Because the curve order is only negligibly smaller than 2^256 (short by roughly 2^128 out of 2^256), any resulting bias is astronomically smaller than the distinctness-bug effect and is not exploitable.
   Direct algebraic solve (no brute force): not possible in principle. Two points on a degree-2 polynomial constitute an underdetermined linear system; no rearrangement of the equations yields a unique solution. This is not an implementation gap — it is the designed security property of (t, n)-threshold Shamir sharing at t-1 known shares.
   Newer/undisclosed vulnerabilities: a search of open and recent bitaps-com/pybtc issues found no report beyond Generation of polynomial coefficients in Sharmir's secret sharing #23 and [Bug Bounty] Biased polynomial coefficient generation in Shamir SSS – Afeta diretamente o Challenge de 1 BTC #73 addressing this scheme.

---

4. Result: measured entropy loss against the live challenge shares
   Running the candidate-enumeration + distinctness-filter procedure against all 16 bytes of the two real published shares:
   Metric Value
   Candidates per byte without bug filter 256 (all bytes)
   Candidates per byte with bug filter 253 (all bytes)
   Total secret entropy without bug 128.0000 bits
   Total secret entropy with bug 127.7279 bits
   Entropy reduction 0.2721 bits (0.21% of the secret)
   This is consistent with, and directly confirms, the theoretical estimate in pybtc#23: for threshold t=3, expected reduction per byte is (t-1)·log2(256/255) ≈ 0.0113 bits/byte × 16 bytes ≈ 0.18–0.27 bits total (depending on the specific byte values), matching the measured result almost exactly.
   This reduction is not exploitable. Even after this pruning, and after applying BIP39 checksum constraints (which eliminate roughly 4 bits' worth of invalid 128-bit strings, unrelated to this bug), the remaining search space vastly exceeds any feasible brute-force or optimized search — several orders of magnitude larger than the entire secp256k1 private key space.

---

5. Conclusion
   The Bitaps Shamir Secret Sharing implementation, as it pertains to this specific challenge (3-of-5 threshold, 2 shares known), is not practically breakable with currently public information:
   The GF(256) Lagrange interpolation and secret-splitting logic are implemented correctly.
   generate_entropy() uses a proper CSPRNG with no recoverable state.
   The one real implementation weakness (coefficient distinctness) leaks a measured 0.27 bits out of 128 — several orders of magnitude too small to matter.
   No stronger, undisclosed vulnerability was found in the public issue tracker as of this analysis.
   This report does not claim a bounty-eligible discovery. It is offered as an independently reproducible confirmation and precise quantification of the previously reported (2021/2026) weakness, tied directly to the live challenge's actual share data rather than described in the abstract.

---

Appendix: Reproducibility
All GF(256) arithmetic, share decoding, and candidate enumeration code used to produce the figures in §4 is available on request. Key parameters for independent verification:
Share 1: index=3, payload=c4451d9745defe5194e707f2e1442ef6
Share 2: index=15, payload=2b6b9b0b2af24a8d592e88a605cf9022
Field: GF(256), reduction polynomial 0x11B (AES-standard)