Biased coefficient generation in Shamir SSS: secret/coefficients forced pairwise-distinct

[nitinkansal30]

Coefficient Non-Distinctness Bias in jsbtc Shamir Secret Sharing

Target: bitaps-com/jsbtc, src/functions/shamir_secret_sharing.js
Referenced by: the live "1 BTC Challenge" at tbtc.bitaps.com/mnemonic/challenge, which explicitly cites this file as its "exact software implementation."
Class: Non-uniform coefficient generation (biased Shamir Secret Sharing), analogous in category to the previously patched and paid pybtc issue #23.

Summary

__split_secret() generates each polynomial's coefficients with rejection sampling that forbids duplicate values within the same coefficient set:

for (let i = 0; i < threshold - 1; i++) {
    do {
        if (ePointer >= e.length) {
            ePointer = 0;
            e = S.generateEntropy({hex:false});
        }
        w = e[ePointer++];
    } while (q.includes(w));   // <-- rejects w if it equals any coefficient already in q
    q.push(w);
}

q starts as [secretByte], so this constraint applies to the secret byte too. The result: for every polynomial generated by this code, the secret byte and all of its random coefficients are guaranteed pairwise distinct. In a correct Shamir Secret Sharing implementation, coefficients (including the constant term) should be free to take any value in GF(256), independently and with replacement — collisions are expected to occur naturally and carry no information.

Exploit

Given t-1 known shares of a threshold-t scheme (exactly the situation of the published challenge: 2 of 3 needed shares are public), an attacker can:

1. Hypothesize a candidate value s for a secret byte.
2. Treat (0, s) as the missing third point alongside the two known points (x₁,y₁), (x₂,y₂).
3. Lagrange-interpolate the unique degree-(t-1) polynomial through all three points to recover its full coefficient vector [q₀, q₁, q₂].
4. If any two coefficients in that vector are equal, s is proven impossible — the real generator could never have produced such a polynomial — and the guess is eliminated with certainty (zero false negatives).

This is structurally the same technique that earned a 0.2 BTC bounty in pybtc issue #23 (there, the impossible condition was "no coefficient equals 255"; here it's "no two coefficients — including the secret — are equal").

Proof of Concept

Full GF(256) arithmetic, the real coefficient-generation logic, and the elimination check were reimplemented and tested against a simulated 16-byte (128-bit) secret with a 3-of-5 split:

Elimination rate:        1.17% of all (byte position × guess) pairs
Avg. surviving guesses:  253.0 / 256 per byte
True secret byte:        survives elimination at every position (0/16 false negatives)

(Verification script available on request — verify_finding.py.)

Impact

• Per byte: entropy drops from 8.000 bits to ≈ log₂(253) ≈ 7.983 bits.
• Across a 16-byte / 128-bit secret: ≈ 0.27 bits of total entropy loss, out of 128.

This is real, reproducible, and provable — but nowhere near sufficient to recover a 128-bit secret from 2 of 3 shares. The remaining ~127.7 bits of search space is exactly as infeasible as brute-forcing a fresh BIP39 seed.

Recommendation

Remove the while (q.includes(w)) rejection loop entirely. Coefficients (including the secret byte) should be drawn independently and allowed to repeat; duplicate values carry no exploitable structure in a correct SSS scheme and rejecting them introduces a provable, if small, statistical bias.
/

jsbtc-shamir-distinctness-bug.md