Group member check seems too restrictive when combining mnemonics

[jfburdet]

If I understand things well the "not equal" check here https://github.com/trezor/python-shamir-mnemonic/blob/c919df7217d0f268e5830ec845c043f0a63b172c/shamir_mnemonic/shamir.py#L425 should be change into a "less than" check (and raised error message changed)

This would allow the following code to work :

mnemonics = shamir.generate_mnemonics(1, [(3, 5)], b"012345678901234567")
recovered = shamir.combine_mnemonics(mnemonics[0])

If I understand spec well and sss, the threshold is the mimimum share count needed to decode the secret, so it should be allowed to pass more shares.

[prusnak]

I think you are right.

Workaround: If you have more shares than threshold, just pass the threshold shares to the library.

@andrewkozlik what do you think? Should we update the code in the library? It's reference implementation, so I think it makes sense.

[andrewkozlik]

should be change into a "less than" check

That's what I initially implemented. I recall that there was then a team discussion where it was decided to be strict about the number of shares provided. I can't remember the rationale for this change, since as I recall I didn't really agree with it.

I also previously had code which would automatically discard groups that are smaller than the group threshold, which I also removed in the same commit. The best that I can recall about the rationale is that the team came to a stance that the code shouldn't be too smart about processing the inputs, i.e. removing redundant information.

The commit message reads:

Update code, tests and vectors in accordance with the new requirement that the number of shares provided is equal to the threshold.

https://github.com/trezor/python-shamir-mnemonic/commit/06536e07c5810ffbd7337fe946558f5d11b16c6e#diff-bf3a7a9b0eedc233dfb28dd6bc7a662ae215fdf226b45f007628a7cdb6bead2fL678

Fun fact. On this pair of lines I had as a unit test exactly the code that @jfburdet is proposing: https://github.com/trezor/python-shamir-mnemonic/commit/06536e07c5810ffbd7337fe946558f5d11b16c6e#diff-4c8758012944fc05228df26dd8616d92c721fa8ff87a521b8dd42f1493c27a88L19-L20

[andrewkozlik]

Functionally, changing the threshold check to a "less than" check is perfectly OK if all entered shares are correct.

The only issue that I can think of when the user enters shares above the threshold is if one or more of the shares is invalid. Say the threshold is 3 and the user enters 4 shares, 3 of them are correct and 1 is invalid. The code will try to interpolate all 4 and fail with Invalid digest of the shared secret.. The current solution forces the user to pick exactly 3 shares. If the user had tried entering different subsets of 3 shares instead of all 4, then they would eventually pick the 3 correct ones and recover their wallet correctly.

Of course this process of trying to pick subsets of size threshold when extra shares are provided can be automated. In the worst case scenario (threshold = 8, share_count = 16) this means going through 12870 combinations, which is not a big deal. I think I also proposed this in 2019, but we decided against it, probably on the grounds that brute-forcing the correct subset doesn't belong into the reference implementation. It's something that shouldn't be happening automatically behind the user's back. It's more appropriate as a higher-level feature, possibly of the CLI.

@matejcik any thoughts?

[matejcik]

The only issue that I can think of when the user enters shares above the threshold is if one or more of the shares is invalid

I'm pretty sure that this is it.

OTOH this seems to be before the 0.2 API rework, in particular, before ShareGroup was a thing. With the current API this is neatly solvable: introduce a "group validity" concept and change this whole loop into:

for group in groups.values():
    group.validate()

(and then later, if desired, we can call get_minimal_group(), which already exists, for passing into the _recover_secret() call)

one more thought: is the validity a property of a single share, or of the whole group? (or both?) as in, there is an individual per-share checksum, but can a share with a valid checksum still be "invalid" with relation to the group, and if so, can we detect that?

[andrewkozlik]

is the validity a property of a single share, or of the whole group? (or both?)

I'd say both.

The shares are protected against accidental errors by a very strong per-share checksum. However, a malicious shareholder or attacker could supply the user with a malformed share that satisfies the per-share checksum but breaks the group checksum. There is no easy way to detect which share is the bad one. We can only detect that a bad share is present in the subset. So if we get threshold good shares and some bad ones, then we can determine the good ones by combining different subsets of size threshold until we succeed. If we have less than threshold good shares in the set, then there is no computationally feasible way to tell which ones are the good ones.

[matejcik]

Reviewing the code, ShareGroup.add() takes a Share instance, which can't be created from a share with invalid checksum, so this part of the code is sound. And the _recover_secret() will accept all shares -- possibly more than threshold -- but raise if the group checksum does not match. If there is an attacker handing out malicious shares, there is no guarantee that we can do anything about it even if we do the subset thing.

This makes me think it's safe to implement the original suggestion of changing != to <, and possibly doing something about the group checksum error message.