tl;dr: “Vanilla” Shamir Secret Sharing has a race condition, but it can be fixed. I outline the problem with some practical solutions.
Lately I’ve being doing some research into the various methods for securing cryptocurrency wealth. I’ve explored the use of of hardware wallets as well as airgapped devices. Using the best cryptographic tools is important, but having a good process is more important. Two useful resources have been a blog by Jameson Lopp and the Glacier Protocol. I’m hoping I can type up more on that in later blogs. It was while thinking about what my own process should be that I discovered a problem in using the ‘vanilla’ Shamir Secret Sharing Scheme.
After further research, plus some discussion with a colleague, it looks like the problem is well known about and there are mitigations. The problem has been known about probably since the inception of the idea and proposed mathematical solutions since the mid-80s. Wikipedia has a reasonable article on this topic: Verifiable Secret Sharing. The biggest remaining problem is lack of implementations inside cryptocurrency wallets. Perhaps this is due to a lack of awareness.
In this is past week Trezor announced that they now support the Shamir Secret Sharing Scheme. I haven’t dug into the details, but there is a chance that it is still vulnerable. I’m not saying the attack is necessarily easy, but when the stakes are high it is something that would be best to avoid. Pushing the industry to go this direction I think is overall a good thing, but more has to be done.
Quick explainer: Shamir Secret Sharing
The scheme let’s you ‘scramble’ a sensitive string of characters (e.g. a password) and then represent those by multiple long numbers. It has a nice property that it is a threshold scheme that let’s you define how many pieces long numbers you want and how many pieces are required to recalculate the original sensitive string of characters. Revealing one long number doesn’t break confidentiality. This makes each individual long number robust against being stolen. The scheme is also agnostic to the input you give it.
This makes the scheme attractive for splitting up:
- the master password of a password manager,
- private keys,
- the recovery phrases / mnemonics of private keys.
There is no single point of failure once the shares are split.
Here’s the problem
If the scheme is used to split up a single private key (e.g. a Bitcoin private key), then the first person to recombine enough of the pieces will be able to spend the tokens. This is a race condition since the first person to recover all pieces may not be the true beneficiary. How come? Well, the main problem being that cryptocurrencies can be spent from any computer anywhere in world, all you need is the private key. I also think there is a reasonable chance that someone could be cheated into revealing their share. Perhaps this can be done by presenting a fake share and encouraging the other legitimate holders to reveal their shares. This really isn’t the ideal security posture for securing large amounts of value.
Let me outline some possible solutions. Each has their own drawbacks.
Current multisignature schemes
Here I’m thinking about current multisignature schemes, e.g. as in Bitcoin and Ethereum. These schemes don’t require holding all the secret values on one device: they can be used to sign messages from different devices at different times and should yield a better chance of rewarding the true beneficiary.
For example: a Bitcoin multsig requires multiple keys to sign a message to make a transaction happen. It is expected that these keys are not held by the same person. I hope that it is apparent why this is useful: e.g. preventing a single person from running away with company funds, and likewise a custody provider can hold a key without putting the stash at risk. In the latter case, this also reduces the risk on the funds being stolen should the beneficiary come under attack.
Security here relies upon the security management processes of each key holder. If enough keys of the threshold amount are poorly managed then the tokens might as well be deemed as insecure. Trail of Bits wrote a nice blog that mentions some of the basics of securing tokens with hardware wallets, the blog also mentions the use of multisignature schemes at the end. Specifically, they note that the security of the host devices is important.
Split a password, not a mnemonic or a key
The suggestion here is that you can use hardware wallets to secure the tokens, which is sensible, but this leaves the problem of securing the mnemonic. The mnemonic phrase that you write down when you buy a hardware wallet can be used to recover the token should the device fail. I may refer to either the recovery phrase or the mnemonic, but I mean the same thing here.
The device itself is a single point of failure, as whoever controls the device can spend the tokens. For a single person securing their tokens that isn’t necessarily wrong! In most of my analysis I had been assuming that there is a single person who owns the tokens. As a point of good practise you must be strict in your management of the recovery phrase. Having access to this phrase is as good as having control over the tokens, which means that managing this phrase is as difficult as managing a private key.
One method to secure the phrase would be to save it in a password manager. This would require saving the phrase in an offline password manager that only saves files to the local computer. Moreover, you should only use the password management software on a fully airgapped computer. I won’t lie: this is a pain. Assuming you can do this, then you can also use the airgapped computer to perform the necessary calculations of Shamir Sharing. The trick now is to split the master password of the password vault and not the recovery phrase. The shares of this split password can now be shared with people of trust.
Why is this different? Well, the first person to recover all of the password shares can not immediately spend the tokens. That is surely a win. In order to spend the tokens you need both the password vault (a file) and enough of the secret shares. The file should be copied and stored across a number of drives, but perhaps should not be so widely distributed.
This technique can also be used with one of the common multisignature schemes.
Require signing from participants
The real fix to the problem would be to require signing the shares, but to the best of my knowledge no wallet supports this yet. Below I will outline where code exists and roughly how it is applied.
The HOPR network is a mixnet for anonymous communication where the nodes are incentivised to route the messages. Payments to the nodes are conducted via state channels, but there is some difficulty in making sure that nodes are only paid for the message they route and are not able to bluff or otherwise steal payment due to other nodes. For payment, each node discloses the shares they received but the shares need to be summed and then multiplied (elliptic curve multiplication) by a signing value (which is also secret).
This particular use of a signature works in this use case since there is a smart contract to enforce it. For the use case I outlined above things will be different.
For more details, see their relevant design document.
After describing the race condition problem to my colleague Jeff he said that it was a solved problem and he pointed me towards his Schnorrkel library. In this library it is a Schnorr multisignature, but it is currently implemented as an aggregate signature (m-of-m) rather than a threshold signature (m-of-n). The mathematics certainly allows for the latter but it hasn’t been coded yet. The main problem here is that this library doesn’t exist in any wallet software yet (AFAIK). While the Polkadot Network includes the library, I don’t believe any of the wallets use the multisignature capabilities yet. Parity Signer should included this capability in a future version.
Parity Signer is an app that you can use on your phone for protecting Ether and in the future DOTs too. If the app is used on a phone that’s kept offline then you can essentially keep the private key airgapped. The signing of transactions happens via QR codes.
The mathematics is compatible with Bitcoin too. As I understand it, there is no modification required to Bitcoin all that is required are the wallet builders to implement it. Interestingly, Schnorrkel builds upon the work outlined in a paper written by some of Bitcoin core’s contributors: “Simple Schnorr Multi-Signatures with Applications to Bitcoin”
- Build us wallets that support verified secret sharing!
This will enable better custody management and should make your cryptocurrencies more resilient to being stolen.
Hopefully, I will be able to share some more of my thoughts on securing private keys. A process rather than yet another piece of technology. We need good apps (vis-a-vis this blog) but we also require good processes otherwise the good apps mean nothing.
Currently, I work at the Web3 Foundation, covering numerous responsibilities (such as grants, communications, and collaboration). This blog is of a personal nature. It just so happens that my hobby aligns with work.
One of the main projects of the foundation is the Polkadot network. A next generation blockchain platform. To read more about the innovation that Polkadot is bringing to the blockchain industry I invite you to read the following blog post: link.
Questions / Comments?
You can create a reply to me here on Medium, or reach out to me on Twitter: @EAThomson.