Shamir Secret Snakeoil

Shamir Secret Sharing seems to be mysteriously attractive to programmers: The idea of splitting up a secret into multiple parts and having a ritual to recombine them seems to trigger and instinctive appeal to many.

Shamir's scheme is clever enough that people feel smart for being able to understand and implement it but it is not so clever that people have a difficult time actually doing so. Unfortunately, the difference between implementing it and implementing it correctly is substantial. Like all cryptographic techniques small errors can have devastating consequences. As a result many, perhaps the vast majority, of SSS implementations are flawed. In some cases the flaws are merely theoretical, compromising properties of SSS that don't matter in practice, but others have been flawed in ways that completely destroy the security. The user's reliance on false security then goes on to cause them to do things that can make them actually lose their funds.

As a generalization of the one time pad SSS, if implemented perfectly, has the unusual property of achieving information theoretic security: it's strong against attackers with unbounded computational power. But this fact itself is of essentially no practical use and seems to distract people from the fact that many attempts at SSS have been so weak a child's speak-n-spell could crack them.

In Bitcoin, Shamir Secret Sharing by itself has almost no valid use: Most threat models that could be defended using SSS are _much_ better defended by multisig particularly because recombining shares of a private on a device leave the key exposed to malware or a malicious user of the device which are usually the most important threats to protect against. If you have a device which is guaranteed to be free of malware operated by a user guarenteed to be uncorrupt, you could just leave the private key there and dispense with the SSS ritual-security-theatre. Bitcoin products that advertise SSS are often snake-oil and the same thoughtlessness that caused the marketing of SSS probably signals poor security.

Most the time safe bitcoin key material can be backed up more safely by simply making multiple copies. Vulnerability of any one backup to theft can be protected against using multisig.

Examples of Shamir Secret Snakeoil

Errors in SSS implementations are not usually the fault of an unusual incompetence in their developers. Correctly implementing cryptographic functions is *hard* but SSS is in a particular sweet spot where-- like most crypto functions-- it is hard to implement correctly that it's interesting to try but also easy enough to implement at all.

Simply avoiding the mistakes listed here will not make an implementation secure. A secure implementation of any cryptosystem starts with a careful analysis of the costs and benefits and often SSS does not make the cut.

Armory

Bitcoin Armory, a previously popular Bitcoin wallet used a N of M secret sharing for backing up users private keys. The implementation used repeated hashing of data instead of a random number generator and that combined with other errors completely breaks the scheme. The result is that regardless of the requested threshold an attacker with the first share and any other share could recover the secret (or alternatively the N-th share plus any N additional ones).

HTC Exodus phone

HTC exodus phone backs up users keys by splitting them 3 of 5 to your phone contacts but totally failed to deliver the advertised security:

They implemented Shamir secret sharing by sharing the 256 bit seed (32 bytes) with 32 different polynomials of degree 2, and then it evaluates it in 5 points and sends the shares. The coefficient a,b are randomly generated with a PRNG and must be kept secret.

The problem with HTC's implementation is that the PRNG update operation is linear and not updated well. Both a and b are linearly dependent. Instead of ending up with a polynomial that they expected, they end up with a different one which has a linear dependency between the coefficients. [...] You only need to compromise 2 different trusted contacts, then you get their shares and you're able to get the seed. So one trusted contact can collude with another and retrieve the value of the seed. This is really bad.

In firmware v1.54.2401.6, the PRNG is seeded with a fixed value. By reverse engineering the application, we know the value, so it's easy for us to calculate a and b polynomials. So only one share is enough to compute the seed. This means a malicious application can extract YOUR seed from the phone of *any* of your trusted contacts.

Sidechannels

Virtual all (all?) existing SSS implementations are completely unhardened against EMI/DPA side-channels, many are unhardened against simple timing sidechannels. Competent key generation and signing software goes through significant efforts to avoid leaking private keys to observers who can monitor your timing or RF emissions, but SSS software will just go ahead and leak this information. In particular, any scheme that implements sharing with a general bignum library will end up with timing side-channels.

Unique benefits against fantasy threat models

SSS's unusual information theoretic properties also makes it possible to "deny shares". Imagine you have a N of M split secret and some attacker finds N-1 of the shares and using a $5 wrench they demand that you provide an additional share so they could get the secret. In theory, with SSS you could compute another share to forge any outcome, so instead of the real secret they get a fake one of your choice! However you can only compute a specific forgery if you know the shares they already possess. It would be difficult for even Hollywood scriptwriters to come up with a situation where you'd have both access to those shares and an opportunity to compute something. Without the shares the best you could do would be to give them a fake value which would decode to something random, and almost all SSS implementations add some kind of error detection to detect false decodes which would reveal your games. Moreover, many SSS implementations don't use actual randomness which would allow detection of this kind of forgery. And finally, these tools never actually provide a usable forging tool and so using forgery or even an argument that someone could have plausibly forged a share as a defence is simply fantasy.

What could SSS sensibly be used for?

SSS sometimes shows up as an internal building block inside other cryptographic protocols for multiparty computation. In these cases the user isn't directly exposed to the SSS and it's much more likely to have been implemented correctly because the complexity of the overall protocol set a higher bar for implementations. In these cases it's a perfectly fine construct, but also in these cases the user will almost certainly never hear the words shamir secret sharing.