Zero leading coefficient silently lowers the Shamir threshold (t-1 shares suffice for affected bytes)

[0xrlawrence]

Submitted for the Shamir Secret Backup Scheme bug bounty.

Summary

Neither split_secret nor its JavaScript counterpart rejects a zero leading coefficient. When a_{t-1} == 0 the polynomial for that byte has degree < t-1, so that byte is recoverable from t-1 shares instead of t — the threshold is silently lower than the caller asked for.

This is still present in current master (after the #23 fix), and also in jsbtc.

Location

https://github.com/bitaps-com/pybtc/blob/master/pybtc/functions/shamir.py#L114-L128

for b in secret:
    q = [b]

    for i in range(threshold - 1):
        if e_i < len(e):
            a = e[e_i]
            e_i += 1
        else:
            e = generate_entropy(hex=False)
            a = e[0]
            e_i = 1
        q.append(a)              # <-- nothing rejects a == 0 for the top coefficient

Demonstration

A 3-of-5 split whose top coefficient is zero is fully recoverable from two shares:

from pybtc.functions.shamir import _fn, _interpolation

q = [0xAB, 0x5C, 0x00]                    # a2 == 0  ->  effectively degree 1
points = [(3, _fn(3, q)), (15, _fn(15, q))]
print(hex(_interpolation(points)))        # 0xab  — the secret byte, from only 2 of 3 shares

Impact

With a uniform generator the per-byte probability is 1/256, so for a 16-byte
(12-word) secret roughly 6% of splits leak at least one byte to a sub-threshold
attacker. That is a small but real deviation from the scheme's stated guarantee:
holders of t-1 shares are supposed to learn nothing.

It was substantially worse in the version live during the bounty
(c009218, June 2021 — the #23 code, fixed only in 77be7d4 on 2021-07-10,
a month after the challenge opened), because (a * i) % 255 makes 0 the single
most over-represented coefficient value:

P(coefficient == 0), buggy generator : 0.02227
P(coefficient == 0), uniform         : 0.00391      (5.7x)

Measured over 400 random 3-of-5 splits of 16-byte secrets, reconstructing with
only 2 shares:

bytes correctly recovered from t-1 shares : 140 / 6400  = 2.19%
expected by chance                        :               0.39%

Suggested fix

Resample the leading coefficient until it is non-zero, so the polynomial always
has the intended degree:

for i in range(threshold - 1):
    while True:
        a = next_entropy_byte()
        if i < threshold - 2 or a != 0:   # top coefficient must be non-zero
            break
    q.append(a)

Note on the bounty's main challenge

For completeness: I also quantified the #23 weakness against the two published
challenge shares (x = 3 and x = 15). Scoring each of the 256 candidates per byte
by the exact coefficient PMF reduces the search from 2^128 to 2^119.07
(2^115.07 including the BIP39 checksum) — i.e. 8.93 bits recovered. That is a
real measurable leak but not a break, which is consistent with the prize being
unclaimed. I am reporting the two implementation bugs above, not claiming the
main prize.