Shamir coefficients are rejection-sampled against the secret byte, breaking uniformity (separate from pybtc#23, still unfixed)

[0xrlawrence]

Submitted for the Shamir Secret Backup Scheme bug bounty.

Summary

In src/functions/shamir_secret_sharing.js, the polynomial coefficients in __split_secret are drawn by rejection sampling that excludes any value already in q — and q is initialised to [secret[b]]. The coefficients are therefore sampled without replacement, conditioned on the secret byte, rather than uniformly and independently.

This breaks the precondition of Shamir's information-theoretic security proof. It is a separate bug from bitaps-com/pybtc#23 (that was (a * i) % 255 in Python, fixed in 77be7d4); the corrected Python code does not have this issue, but the JavaScript does and has been unchanged since 2020-05-19.

This is the implementation the offline mnemonic tool ships to users.

Location

https://github.com/bitaps-com/jsbtc/blob/master/src/functions/shamir_secret_sharing.js#L126-L137

let q = [secret[b]];                       // <-- secret byte seeds the reject 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 == secret byte, and w == any earlier coefficient
    q.push(w);
}

Why it matters

Shamir's scheme is unconditionally secure only if the non-constant coefficients are uniform and independent of the secret. Here neither holds:

• a_j != secret_byte for every j >= 1
• a_j != a_k for every j != k

So the shares are no longer statistically independent of the secret, and an attacker holding t-1 shares can discard candidate secrets that would imply a repeated value.

Concretely

For a t-of-n split, an attacker with t-1 shares can, for each secret byte, solve for the remaining coefficients under each of the 256 guesses of a0 and reject any guess where the implied coefficients collide with a0 or with each other.

Measured for 3-of-5 (two shares known, x = 3 and x = 15), averaged over 2000 random share pairs:

eliminated candidates per byte: 2.99 / 256  (1.17%,  ~0.017 bits/byte)

Small at t = 3, but the constraint set grows with the threshold: at threshold t there are t-1 coefficients required to be mutually distinct and distinct from the secret, so the bias compounds — the same regime analysed in #23 for the Python bug. Independently of the bit count, a cryptographic primitive whose randomness is conditioned on the plaintext should be fixed on principle.

Reproduction

The elimination rate is a property of the GF(256) arithmetic, which is identical
in both libraries. For each byte, solve the two share equations for (a1, a2)
under each guess of a0 and count the guesses that imply a collision:

# x1, x2 = the two known share indexes; y1, y2 = their bytes at this position
for a0 in range(256):
    u1, u2 = y1 ^ a0, y2 ^ a0
    det = gf_mul(x1, gf_mul(x2, x2)) ^ gf_mul(gf_mul(x1, x1), x2)
    a1 = gf_div(gf_mul(u1, gf_mul(x2, x2)) ^ gf_mul(u2, gf_mul(x1, x1)), det)
    a2 = gf_div(gf_mul(x1, u2) ^ gf_mul(x2, u1), det)
    if a1 == a0 or a2 == a0 or a1 == a2:
        continue        # impossible under the rejection sampling above

Averaged over 2000 random share pairs at x = 3, 15 this discards 2.99 of 256
guesses per byte.

Suggested fix

Take coefficients directly from the entropy stream with no distinctness test, matching the corrected Python in 77be7d4:

for (let i = 0; i < threshold - 1; i++) {
    if (ePointer >= e.length) {
        ePointer = 0;
        e = S.generateEntropy({hex:false});
    }
    q.push(e[ePointer++]);
}

Companion issue: bitaps-com/pybtc#88 — a zero leading coefficient silently lowers the threshold. That one affects this file too (w == 0 is only rejected when the secret byte happens to be 0), so both fixes are worth applying here.