Shamir's Secret Sharing shortcomings

In bitcoin the smallest error has the potential to be catastrophic; as such, those focused on private key security strive to eliminate any single point of failure in the systems they build.

Naturally, this makes the concept of splitting up a secret into multiple pieces and later performing a ritual to recombine them sound somewhat appealing.

It's so appealing that variations of Shamir's Secret Sharing (SSS) have been implemented several times in the cryptocurrency space, only for developers to later realize that the additional complexity ended up reducing the security of the system.

Shamir's method enables the secure sharing of a secret where k out of n shares can reconstruct the secret, yet an attacker who possesses up to k-1 shares can not discover any information about the original secret. Private key sharing is achieved for bitcoin by splitting a key (either an individual key or a seed to many deterministic keys) into multiple pieces such that some subset of the pieces can be recombined to recover and use the key to sign a transaction.

"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. This kind of "perfect security" adds to the mysterious appeal but this property 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. Like the one-time-pad and most other cryptosystems, the security of SSS is fairly brittle."
- Gregory Maxwell

Key splitting can function as an alternative to multisig, but after researching its practical application at Casa, we rejected implementing Shamir's Secret Sharing Scheme because it exposes clients to many more risks.

The rest of this post will explain those risks in greater detail, such as:

• Single points of failure
• Share revocation
• Implementation complexity
• Lack of implementation standards
• Social recovery issues
• Auditability
• Share integrity
• Side channel attacks

Single point of failure

In order to split a private key via SSS it must exist on a single device at the time of splitting and it is later reconstructed onto a single device in order to sign transactions. If the device is compromised at either of these points, a user's funds can be stolen. Most threat models that could be defended using SSS are much better defended by multisig because recombining shares of a private key on a device leave the key exposed to malware or a malicious user of the device, which are some of the most important threats to protect against. With multisig you can use geographically distributed hardware and software to eliminate any such single points of failure.

No share revocation

If any structural change to the shares needs to be made after splitting a key with SSS, a threshold of shares must be brought together to reconstruct the secret, then all the shares must be replaced via a new split operation. This makes rapid recovery from an attack or even a simple system update difficult. Alternatively, the share dealer (secret owner) may choose to generate many sets of key splits up front and keep the extra sets in reserve in order to rapidly re-issue shares, but this once again recreates a single point of failure with all shares being held by the issuer. It also still requires all shareholders to update their shares any time a change is made, which becomes more onerous as the number of shareholders increases.

On the other hand, with multisig the user can invalidate a single lost key and replace it, effectively "rotating it out" of use. The other keys can be kept and used with the new key to construct a new multisig setup and set of addresses.

Complexity is the enemy of security

"I think Shamir's Secret Sharing (and a number of other things, RNGs for example), suffer from a property where they are just complex enough that people are excited to implement them often for little good reason, and then they are complex enough (or have few enough reasons to invest significant time) they implement them poorly." 
- Gregory Maxwell

Maxwell found a vulnerability in Armory's "Fragmented Backups" feature which used a custom SSS implementation.

The implementation used repeated hashing of data instead of a random number generator and that determinism combined with other errors completely broke the scheme. The result was that regardless of the requested threshold, an attacker with the first share and any other share could recover the secret (or alternatively the Nth share plus any N other shares).

Another SSS implementation that had issues was used by the HTC Exodus phone to back up users' keys by splitting them in a 3 of 5 scheme to the phone's contacts, but it failed to deliver the advertised security model:

"It can be shown that, no matter which shares are retrieved, the system will always have between 2 and 256 solutions. In order to test the returned solutions, we use a previously mentioned property of the used DRBG: the byte representation of the polynomial coefficients of degree 1 must be equal to the SHA-256 of the coefficients of degree 2. Given two shares, solving the system and testing all solutions takes less than a second. The secret is systematically retrieved from two shares."

The problem with HTC's implementation was that the PRNG update operation was linear rather than random. Instead of ending up with a polynomial that they expected, they ended up with one that had a linear dependency between the coefficients. As a result, an attacker only needed to compromise 2 trusted contacts in order to reconstruct the seed from their shares. Thus, one trusted contact could collude with another and retrieve the seed.

Additionally, Ledger DonJon discovered that sss_update_secure_random_buffer, the PRNG initialization function, was never called. As a consequence, the key used to encrypt the seed was always the same and since this key was sent to every trusted contact, any one of them could decrypt the seed and access the funds without need for collusion.

The construction of a multisig script in bitcoin, on the other hand, is straightforward:

M <Public Key 1> <Public Key 2> … <Public Key N> N CHECKMULTISIG

Being far more simple than secret sharing, it is highly unlikely an implementer would create a flaw that would compromise the security of the system. There are no random number generators or other sensitive cryptographic operations involved; this is a native operation in the bitcoin protocol that is highly standardized and implemented by many libraries.

No standard implementation

On the other hand, there is no standard for Shamir's Secret Sharing. This means that shares made with one piece of software might not be usable with a different piece of software. This can lock users into one implementation which compromises user sovereignty. It additionally increases the risk of loss due to user error or implementation bugs. In general, it's an obstacle to the use of heterogeneous hardware and software, creating another single point of failure.

It is worth noting that there now exists a proposed standard for splitting bitcoin seed phrases via SatoshiLabs Improvement Proposal 39. It was under development for nearly 2 years, appears to be well designed, and has been implemented in at least 4 programming languages.

Social recovery complexities

We're often seeing SSS implemented to create "social recovery" mechanisms for private keys. However, the construction of SSS necessitates that all shares are of equal weight. But in reality, social trust is not uniformly distributed among different social circles, such as friends, business acquaintances, and family. Individuals may be fungible within a certain circle of trust, but not more broadly. A "family member" is not the same as a "business partner." The only way to implement these kinds of scenarios is by giving a shareholder multiple shares.

For example, imagine a situation where we want the shares distributed among 2 family members and 4 friends. We want the following combinations to recover the secret:

• 2 family members, 0 friends
• 1 family member, 2 friends
• No threshold of only friends

We would need to generate 12 different shares, with a recombination threshold of 6.

Each family member receives 4 shares.

Each friend receives 1 share.

Is it more burdensome to require a single person to keep track of multiple shares? It's debatable. To be fair, multisig has the same weighting complexity problem, but when combined with the next several issues SSS becomes exceptionally unpalatable.

Poor auditability

If a key is reconstituted from secret shares, it’s not possible to tell which shares were used to recreate the key. Whereas with on-chain multisig, the “identity” of each signing key is stored on the blockchain and can be useful for forensic analysis in the case of compromised keys.

Inability to verify share integrity

If you have a share that supposedly belongs to some split secret, there is no way to verify that the data has not been corrupted. Neither can you verify the correctness of the retrieved shares during the reconstruction process—either reconstruction succeeds or it fails.

This means that individuals are free to submit fake shares and prevent the correct secret from being reconstructed. An adversarial shareholder with enough information can even produce a different share such that the secret is reconstructed to a value of their choice. In order to verify share correctness you have to use a technique known as verifiable secret sharing, which enables you to verify that shareholders are honest and not submitting fake shares.

If an adversarial cosigner on a multisig wallet provided an invalid signature, it would immediately be obvious. It's also worth noting that SLIP-0039 solves the individual share integrity issue by adding checksums to each share.

Side channel attacks

For real world cryptography applications, there is often the threat of side channel attacks, in which an attacker attempts to extract useful information from application timing, caching, fault, and more. Many existing SSS implementations are completely unhardened against EMI/DPA side channels and many are unhardened against simple timing side channels. Well designed 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 often leak this information. In particular, any scheme that implements sharing with a general bignum library will end up being vulnerable to timing side-channels.

The ability to use heterogeneous hardware and software to generate and manage geographically distributed keys in a multisig setup aids in mitigating these attacks.

Is everything terrible?

There may yet still be some practical application of SSS for securing bitcoin keys where the SSS portion is playing a small role in a more complete system.

For example, social sharing of 1 key of a multisig setup may be sufficiently low-risk to implement, such that a catastrophic issue with the SSS implementation would not result in catastrophic loss of funds.

Schnorr threshold signatures also have the potential to work with split keys plus:

1. You can construct signatures without recombining the keys
2. You can generate the keys on separate devices

However, the SSS portion is still hard to implement well—there are open questions about the best way to implement the above scheme.

Another interesting avenue to explore might be hierarchical SSS, but this still needs much more testing.

We'll continue to experiment with the possibilities as there are continuing developments in this space. But for now we strongly recommend against using Shamir's Secret Sharing for the reasons outlined above.

Follow the future of private keys

Our weekly Casa Security Briefing helps you stay in the know with stories, analysis, and tips. Sign up below.