Ha! We used this concept over a decade ago to stop our servers containing credit card information from our customers from being rebooted unexpectedly and unsealing themselves/permitting traffic.
What a fun memory, other tricks we employed was to disable the TTY and any form of remote login; and heavily auditing and restricting the information coming in via a WAF.
It was very frustrating for them to have a fault because in order to reboot the system (which is basically all you can do): you need the CIO and one of the trusted product managers and one of the trusted sysadmins. The issue with that final one was that the trusted sysadmins could not be the same trusted sysadmins who could access the remote logging infrastructure. — also the CIO was a large bus factor, but I was told the CEO also had that key.
If you work on payment systems at Facebook/meta or Oracle Netsuite then likely some of that code still exist there. Maybe someone can confirm.
Written in 2006, and this doesn't give me much confidence:
> Some people reported compilation probems with ssss-0.5. This will be fixed in the upcoming release. If the code isn't processed correctly on your machine, replace line 351 of ssss.c by
> int restore_secret(int n, void *A, mpz_t b[])
Edit: We've come a long way in open source software development....
EDIT: The SLIP-39 standard is probably the most accessible (and only?) usage of SSSS by "normals". As people find out how fragile and risky BIP-39 is, they'll want to secure their existing BIP-39 accounts, and they can do it using SLIP-39, which uses SSSS. You're welcome!
iiuc it's by activity. The user isn't green because they've posted the link several times, just never stuck around to comment.
This is a one-way relationship, users like these detract from the conversation, they have one thing to say only and every time it only benefits them. Downvote me for being a jerk, I don't care, I'm not wrong. They probably don't mean any harm, and maybe aren't free to speak in a job context on unrelated things, but surely they have to understand how it would make some of us feel a bit used.
A few months ago I built a CLI frontend for Hashicorps shamir secret sharing implementation in Go. You can find it here: https://github.com/dennis-tra/shamir
It combines the two separate commands in the article into one.
Some more context here is that Reed Solomon and Shamir's Secret Sharing both take some data and produce N pieces (commonly called shards or horocruxes), any K of which can reconstruct the original data (K <= N).
The difference is that Shamir's makes it so that having up to K-1 pieces reveals _no_ information about the original data. You may be able to infer certain data from less than K shards in Reed Solomon.
It's extremely common for SSS implementations to contain grave weaknesses. The readme at the github there is good news because it clearly shows that the author is aware of these problems, making it much more likely to be secure.
I have not reviewed it (beyond a glance), but based on the readme I'm confident that this one has a good chance of being secure, which is a vast improvement over most.
I still think in general SSS has very limited real use (except embedded into a larger cryptosystem), but if you're going to use it at least use a version that doesn't introduce vulnerabilities!
This is a wonderfully simple scheme to split up keys between parties, but this still involves a party (the one that made the key) at some point knowing the key. This scheme implies you trust this distributor not to make copies of the key for himself (queue sauron references...). I've wondered if there's a scheme that does NOT trust the distributor of the key. What if the only time they key was known was when the parties reached quorum after the fact?
That doesn't seem to answer the question - the schemes on your link still have a dealer with access to the original secret I think? Is it possible to have each participant contribute an input that forms part of the original secret, such that they get combined to form the secret and then split into shares in a way that doesn't require a dealer?
Interesting question. Are there any restrictions on the relationship between t and n, i.e. can I have 1 <= t <= n? I had a thought for solving your problem but it might not work for arbitrary t.
Yes, there are threshold cryptography schemes with "distributed key generation" [1] in which the parties end up holding shares but the full secret is never known to any party. Then, to your point about "the only time they key was known was when the parties reached quorum after the fact": in these schemes, some threshold of the parties can cooperate to compute a function of the secret (e.g. a signature, or a ciphertext) without any of them ever knowing the secret.
You can do that using Multi Party Computation. There are a bunch of MPC protocols for generating Eliptic Curve private keys and doing DSA where the whole private key is never assembled. It uses Shamir Sharings as part of the magic, it's quite neat :)
I build systems designed to distrust any single individual with cryptographic key material and SSSS needs a lot of careful handling and automation to accomplish this.
Splitting the key safely is only part of the problem though, because you will then need a system that only -uses- the key in a way all parties consent to.
Threshold signing is a much easier alternative for many use cases but sometimes a cryptosystem requires just one key and SSSS is all we can do.
To avoid any single party accessing a complete SSSS split key you can:
1. Write an application that takes N public keys as input, and returns a newly generated key as SSSS shares encrypted to each respective public key as output.
2. Compile application deterministically as an immutable unikernel or firmware image targeting hardware that supports remote attestation (Nitro Enclave, Confidential VM, HSM, etc).
3. Publish source code such that all participants can access and review it, or confirm review was done by multiple parties they trust.
4. Have multiple parties trusted by all participants, or the participants themselves, build the application bundle and confirm they get the same hash
5. Any party deploys the bundle to a live remotely attestable system.
6. All parties use the remote attestation interface to confirm the target system is running the multi-party deterministically compiled application they expect.
7. All parties submit their public keys to the remote system.
8. The remote system generates new key, splits it, and returns SSSS shares to each party encrypted to their respective public key.
> This scheme implies you trust this distributor not to make copies of the key for himself (queue sauron references...). I've wondered if there's a scheme that does NOT trust the distributor of the key.
What you describe still trusts the distributor - you just found a way to make the distributor easy to trust. I'd be more interested in a mechanism that is mathematically correct, like some of the papers referenced elsewhere in this thread.
Even if you avoid trusting the distributor, the quorum of share holders still will end up having to reconstitute the shared key into the memory of a computer somewhere at some point to do cryptographic operations with it.
There is no avoiding standing up computers all parties trust and if you are going to do that anyway then you might as well use them for key generation and distribution too.
I mean that the security profile of a simple 'locked box' that only knows the keys when all parties agree to unlock it is a very different from the security profile of a 'key distribution machine' like you described.
I mean, if we all agreed to perform the decryption, the secret's out anyway. But not before then.
Depends on use case I suppose. I can not think of many practical applications for one-time-use keys other than disaster recovery flows.
The real world use cases I most commonly support are things like CAs, TLS keys, financial transaction signing keys, and sensitive document decryption keys. All of these require single keys to exist that needs to perform automated operations, and needs to be on systems that can be backed up, restored, upgraded, and maintained, while able to prove no single person can access or control the keys.
The scheme I described can allow one key to be created, split, restored, used, and split again many times without full trust in any individual.
I have done this with other parties by brute force for crypto.
You usually have a ring of people and need 3 out of the 7 to open the box. You simply encrypt the box in whatever combinations you want, and people run their keys against each layer of the box. You end up with a few different files but in the case of keys, and a small number of sharers this is not going to be a big data issue.
Implementing SSS is fun. It’s short and covers using modulo integer arithmetic to compute invertible integer functions. It also overlaps with error correction methods a bit.
I’ve written ones based off Vault’s Go version in both Nim and Elixir:
Should be GF(256). 255 isn't a prime power and can't be a field.
I dunno anything about nim but the GF arithmetic code appears to contain branching on values, so this implementation isn't sidechannel resistant and could reduce the users security if otherwise their use of cryptography would be sidechannel resistant.
I didn't look further, it's common for SSS implementations to contain cryptographic flaws that degrade or destroy their security entirely for the same reason people are advised to not home-roll their own constructions of other cryptosystems.
Yes they’re not side channel resistant —- I should add a note for that. The Nim one could be made so, but the Elixir one would be difficult due to its VM so I didn’t port the original constant time parts.
I certainly wouldn’t recommend these libraries for very high security needs as is. That being said, side channel resistance isn’t a necessity for many use cases.
SSS can be used for cases like making a scavenger hunt by splitting up a set of files among N USB keys. Perhaps even to give N family members Your Bitcoin wallet key in case you die or loose your key. Having a little GUI program run and present the combined data really wouldn’t benefit from side channel resistance, IMHO.
So while caution is advisable with any security related code, I think the “never write crypto” prevents a lot of valid and useful applications.
In bitcoin you can use multisig instead of secret sharing. Lots of good and well audited code for that. If you want some one key or threshold policy there isn't any transaction size overhead in the one key case anymore.
I think my contention for SSS implementations has mostly been that the need/benefit seldom justifies the extra effort required to be confident you got it right. Obviously for a treasure hunt the bar is pretty low. :)
It's hard to be sure when sidechannel resistance is really needed. Right now you could have some JS running in silently in a browser thats conducting a sidechannel attack to steal data. Probably not, but these attacks have been witnessed.
Common issues aren't limited to sidechannels, e.g. it's pretty common for there to be "random" number generation problems that make it possible to recover the secret with fewer shares than the threshold. (the bitcoin wiki page I linked to gives two examples of that)
I'd also agree that the "abstinence only" approach to cryptography doesn't work. But the underlying issue that drives that advice is real.
The best alternative to overkilling the implementation is documenting the intended uses and known weaknesses, I guess!
50 comments
[ 2.8 ms ] story [ 107 ms ] threadWhat a fun memory, other tricks we employed was to disable the TTY and any form of remote login; and heavily auditing and restricting the information coming in via a WAF.
It was very frustrating for them to have a fault because in order to reboot the system (which is basically all you can do): you need the CIO and one of the trusted product managers and one of the trusted sysadmins. The issue with that final one was that the trusted sysadmins could not be the same trusted sysadmins who could access the remote logging infrastructure. — also the CIO was a large bus factor, but I was told the CEO also had that key.
If you work on payment systems at Facebook/meta or Oracle Netsuite then likely some of that code still exist there. Maybe someone can confirm.
> Some people reported compilation probems with ssss-0.5. This will be fixed in the upcoming release. If the code isn't processed correctly on your machine, replace line 351 of ssss.c by
> int restore_secret(int n, void *A, mpz_t b[])
Edit: We've come a long way in open source software development....
This saves the original entropy from which your BIP-39 phrase was generated, over several groups of multiple SLIP-39 mnemonics cards.
Later, recover enough cards from a few groups, recover your BIP-39, and recover your hardware wallet.
Much more reliable, and safer because an attacker must collect many independent mnemonics from groups they probably don’t know the members of.
[0] https://slip39.com
EDIT: The SLIP-39 standard is probably the most accessible (and only?) usage of SSSS by "normals". As people find out how fragile and risky BIP-39 is, they'll want to secure their existing BIP-39 accounts, and they can do it using SLIP-39, which uses SSSS. You're welcome!
https://evervault.com/blog/shamir-secret-sharing
This is a one-way relationship, users like these detract from the conversation, they have one thing to say only and every time it only benefits them. Downvote me for being a jerk, I don't care, I'm not wrong. They probably don't mean any harm, and maybe aren't free to speak in a job context on unrelated things, but surely they have to understand how it would make some of us feel a bit used.
In any event, the only person detracting from this interesting thread on SSS, is you.
There are implementations of the algorithm in other languages on github[0].
[0]https://github.com/topics/shamir-secret-sharing
It combines the two separate commands in the article into one.
The difference is that Shamir's makes it so that having up to K-1 pieces reveals _no_ information about the original data. You may be able to infer certain data from less than K shards in Reed Solomon.
Implementation: https://github.com/dsprenkels/sss
I have not reviewed it (beyond a glance), but based on the readme I'm confident that this one has a good chance of being secure, which is a vast improvement over most.
I still think in general SSS has very limited real use (except embedded into a larger cryptosystem), but if you're going to use it at least use a version that doesn't introduce vulnerabilities!
FROST is one example of such a threshold scheme, for computing Schnorr signatures: https://eprint.iacr.org/2020/852.pdf
[1] https://en.wikipedia.org/wiki/Distributed_key_generation
One example is as follows: each party i generates a random polynomial P_i, and n secret shares of that polynomial (j, P_i(j)) for j in 1..n
Then, party i sends (j, P_i(j)) to party j. Party i similarly receives shares (i, P_j(i)) for j=1..n. Party i stores the share (i, sum(P_j(i))).
Then, parties reveal their shares as usual, the secret is then the sum_i P_i(0).
Of course, if the parties are dishonest, you might want some additional safety mechanisms, which can be dealt with with Kate commitments.
This papers https://eprint.iacr.org/2020/504.pdf goes into details, and much more.
Splitting the key safely is only part of the problem though, because you will then need a system that only -uses- the key in a way all parties consent to.
Threshold signing is a much easier alternative for many use cases but sometimes a cryptosystem requires just one key and SSSS is all we can do.
To avoid any single party accessing a complete SSSS split key you can:
1. Write an application that takes N public keys as input, and returns a newly generated key as SSSS shares encrypted to each respective public key as output.
2. Compile application deterministically as an immutable unikernel or firmware image targeting hardware that supports remote attestation (Nitro Enclave, Confidential VM, HSM, etc).
3. Publish source code such that all participants can access and review it, or confirm review was done by multiple parties they trust.
4. Have multiple parties trusted by all participants, or the participants themselves, build the application bundle and confirm they get the same hash
5. Any party deploys the bundle to a live remotely attestable system.
6. All parties use the remote attestation interface to confirm the target system is running the multi-party deterministically compiled application they expect.
7. All parties submit their public keys to the remote system.
8. The remote system generates new key, splits it, and returns SSSS shares to each party encrypted to their respective public key.
What you describe still trusts the distributor - you just found a way to make the distributor easy to trust. I'd be more interested in a mechanism that is mathematically correct, like some of the papers referenced elsewhere in this thread.
There is no avoiding standing up computers all parties trust and if you are going to do that anyway then you might as well use them for key generation and distribution too.
I mean, if we all agreed to perform the decryption, the secret's out anyway. But not before then.
The real world use cases I most commonly support are things like CAs, TLS keys, financial transaction signing keys, and sensitive document decryption keys. All of these require single keys to exist that needs to perform automated operations, and needs to be on systems that can be backed up, restored, upgraded, and maintained, while able to prove no single person can access or control the keys.
The scheme I described can allow one key to be created, split, restored, used, and split again many times without full trust in any individual.
You usually have a ring of people and need 3 out of the 7 to open the box. You simply encrypt the box in whatever combinations you want, and people run their keys against each layer of the box. You end up with a few different files but in the case of keys, and a small number of sharers this is not going to be a big data issue.
Sadly companies like Unbound were acquired by Coinbase and the OSS codebase is not longer maintained: https://github.com/unboundsecurity/blockchain-crypto-mpc
this has obvious timing and cache sidechannels on the secret data.
(IIRC SSSS is even worse, however.)
I wish more apps used this tech.
https://support.argent.xyz/hc/en-us/articles/360022631992-Ab...
I’ve written ones based off Vault’s Go version in both Nim and Elixir:
- keyxn https://github.com/elcritch/keyxn
- keyx https://github.com/elcritch/keyx
Should be GF(256). 255 isn't a prime power and can't be a field.
I dunno anything about nim but the GF arithmetic code appears to contain branching on values, so this implementation isn't sidechannel resistant and could reduce the users security if otherwise their use of cryptography would be sidechannel resistant.
I didn't look further, it's common for SSS implementations to contain cryptographic flaws that degrade or destroy their security entirely for the same reason people are advised to not home-roll their own constructions of other cryptosystems.
Yes they’re not side channel resistant —- I should add a note for that. The Nim one could be made so, but the Elixir one would be difficult due to its VM so I didn’t port the original constant time parts.
I certainly wouldn’t recommend these libraries for very high security needs as is. That being said, side channel resistance isn’t a necessity for many use cases.
SSS can be used for cases like making a scavenger hunt by splitting up a set of files among N USB keys. Perhaps even to give N family members Your Bitcoin wallet key in case you die or loose your key. Having a little GUI program run and present the combined data really wouldn’t benefit from side channel resistance, IMHO.
So while caution is advisable with any security related code, I think the “never write crypto” prevents a lot of valid and useful applications.
I think my contention for SSS implementations has mostly been that the need/benefit seldom justifies the extra effort required to be confident you got it right. Obviously for a treasure hunt the bar is pretty low. :)
It's hard to be sure when sidechannel resistance is really needed. Right now you could have some JS running in silently in a browser thats conducting a sidechannel attack to steal data. Probably not, but these attacks have been witnessed.
Common issues aren't limited to sidechannels, e.g. it's pretty common for there to be "random" number generation problems that make it possible to recover the secret with fewer shares than the threshold. (the bitcoin wiki page I linked to gives two examples of that)
I'd also agree that the "abstinence only" approach to cryptography doesn't work. But the underlying issue that drives that advice is real.
The best alternative to overkilling the implementation is documenting the intended uses and known weaknesses, I guess!