Critical Implementation Flaw: Non-Uniform Coefficient Generation Breaks Information-Theoretic Security

[adamnoks]

Hello Bitaps Team,

I am submitting a bug report regarding a critical vulnerability in the Shamir Secret Sharing implementation found in the jsbtc library (and potentially affecting the logic in pybtc). This flaw violates the core mathematical assumptions of Shamir's Secret Sharing Scheme (SSSS) over GF(256), leaking information about the secret and reducing the effective entropy.

Vulnerable Code

File: src/functions/shamir_secret_sharing.js
Lines: ~88-100 (inside S.__split_secret)

for(let b = 0; b < secret.length; b++) {
    let q = [secret[b]];
    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)); // <--- CRITICAL BUG HERE
        q.push(w);
    }
    // ...
}

Technical Explanation

In a mathematically secure Shamir Secret Sharing scheme over a finite field (like GF(256)), the polynomial coefficients $a_1, a_2, \dots, a_{t-1}$ must be chosen independently and uniformly at random (sampling with replacement).

However, the implementation uses while(q.includes(w)). This forces all coefficients in the polynomial (including the secret byte itself, which is initialized as q = [secret[b]]) to be strictly unique.

This introduces two massive cryptographic flaws:

1. Information Leakage about the Secret: The random coefficients $a_i$ are explicitly rejected if they equal the secret byte $s$. This means an attacker knowing the structure of the scheme knows that $a_i \neq s$. While this seems minor for a single byte, it breaks the perfect secrecy property of SSS.
2. Reduced Entropy & Statistical Bias: By forcing coefficients to be unique (sampling without replacement), the distribution of the polynomial is no longer uniform. For a threshold $t$, the number of possible polynomials is drastically reduced from $256^{t-1}$ to $P(255, t-1)$. This creates a measurable statistical bias in the generated shares.

Impact

Because the coefficients are not truly independent, the scheme loses its information-theoretic security guarantee. An attacker with fewer shares than the threshold can use this bias to eliminate certain possibilities for the secret bytes, significantly reducing the search space required to brute-force the original mnemonic.

In the context of the ZeroNights X Bug Bounty Challenge (3-of-5 threshold, 12-word mnemonic), this implementation bug means the shares are not mathematically secure, and the search space for the original 128-bit entropy is smaller than claimed.

Recommendation / Fix

Remove the uniqueness check. Coefficients in GF(256) Shamir Secret Sharing must be allowed to repeat.

Change the loop to simply draw random bytes without checking q.includes(w):

for(let b = 0; b < secret.length; b++) {
    let q = [secret[b]];
    for(let i = 0; i < threshold - 1; i++) {
        if(ePointer >= e.length) {
            ePointer = 0;
            e = S.generateEntropy({hex:false});
        }
        let w = e[ePointer++];
        q.push(w); // Simply append, do not check for uniqueness
    }
    // ...
}

Please review this implementation flaw. I believe this qualifies for the significant implementation bug reward tier.

Thank you.