Ssss: Shamir's Secret Sharing Scheme (2006) | Hacker News Reader

Ssss: Shamir's Secret Sharing Scheme (2006)

point-at-infinity.org

133 pointsTomte43 comments

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?

Plenty. Look into publicly verifiable secret sharing. https://en.wikipedia.org/wiki/Publicly_Verifiable_Secret_Sha...

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?

See my other comment in this thread which details a solution to this.

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.

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

A similar scheme we use in drand is this: https://www.researchgate.net/publication/225722958_Secure_Di...

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 :)

Sure.

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.

Refer: https://github.com/dedis/kyber/blob/master/share/vss/rabin/v... and https://github.com/dedis/kyber/blob/master/share/vss/pederse...

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.

Well, now you've just turned your locked box into a key distribution machine, and there's a big difference in the security profile of each.

What is the point of generating a cryptographic key that you can never safely use?

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.

If anyone is interested in understanding Shamir's scheme a bit more, this blog post visualises it well! :)

https://evervault.com/blog/shamir-secret-sharing

Backup your BIP-39 Mnemonic phrase using SLIP-39 [0]

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!

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.

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.

Here is a great talk on new SSS library from Daan Sprenkels at 34C3: https://www.youtube.com/watch?v=ojMFCpUt7OU

Implementation: https://github.com/dsprenkels/sss

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!

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:

- keyxn https://github.com/elcritch/keyxn

- keyx https://github.com/elcritch/keyx

> GF(255).

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.

Ah thanks, I’ll fix the GF(256) bit.

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!

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....

Use MPC instead? Sadly there are not enough mature open source projects around: https://github.com/ZenGo-X/multi-party-ecdsa and you can always take a look at https://github.com/rdragos/awesome-mpc

Sadly companies like Unbound were acquired by Coinbase and the OSS codebase is not longer maintained: https://github.com/unboundsecurity/blockchain-crypto-mpc

Argent’s “guardians” are the only consumer implementation of SSS that I have found and I love it.

I wish more apps used this tech.

https://support.argent.xyz/hc/en-us/articles/360022631992-Ab...

Post dates from 2018, code from 2006. Description of Shamir's secret sharing is still current.

There are implementations of the algorithm in other languages on github[0].

[0]https://github.com/topics/shamir-secret-sharing

Shamir's scheme is related to Reed-Solomon error correction.

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.

I'd recommend using libgfshare over ssss, if you're looking for a command-line application.

https://github.com/jcushman/libgfshare/blob/master/src/libgf...

this has obvious timing and cache sidechannels on the secret data.

(IIRC SSSS is even worse, however.)

https://en.bitcoin.it/wiki/Shamir_Secret_Snakeoil

Reply on news.ycombinator.com