[HN Gopher] Ssss: Shamir's Secret Sharing Scheme (2006)
___________________________________________________________________
Ssss: Shamir's Secret Sharing Scheme (2006)
Author : Tomte
Score : 122 points
Date : 2022-10-25 06:08 UTC (2 days ago)
(HTM) web link (point-at-infinity.org)
(TXT) w3m dump (point-at-infinity.org)
| computerfriend wrote:
| I'd recommend using libgfshare over ssss, if you're looking for a
| command-line application.
| nullc wrote:
| 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.)
| pjkundert wrote:
| 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!
| jron wrote:
| 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
| nullc wrote:
| 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!
| [deleted]
| wslh wrote:
| 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
| yodon wrote:
| 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
| nullc wrote:
| https://en.bitcoin.it/wiki/Shamir_Secret_Snakeoil
| nuggimane wrote:
| 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
| aliqot wrote:
| why is this your only comment and no green name?
|
| edit: ah nvm, you submit only links to the site you just
| linked.
| pkage wrote:
| iiuc HN flags new accounts by creation time and not activity
| (e.g. less than N days old)
| aliqot wrote:
| 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.
| dcow wrote:
| This discussion seems valuable, no? How would we be
| having it if not for this user's contribution? Who's
| using whom, now?
|
| In any event, the only person detracting from this
| interesting thread on SSS, is you.
| nuggimane wrote:
| Yeah I don't really comment but knew it was relevant to this
| thread so figured I would for once
| aliqot wrote:
| why do you only post that one domain though, you don't want
| to diversify or is that your site or what?
| animuchan wrote:
| It's their only comment, how many different domains would
| you put in one comment and why.
| aliqot wrote:
| comment =/= submission.
| animuchan wrote:
| Fair, sorry, I missed that.
| robbiemitchell wrote:
| Yes, because he works at Evervault
|
| https://www.linkedin.com/in/david-nugent-1a615b178/
| dijit wrote:
| 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.
| humanistbot wrote:
| 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....
| dennis-tra wrote:
| 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.
| olah_1 wrote:
| 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...
| [deleted]
| elcritch wrote:
| 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
| nullc wrote:
| > 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.
| [deleted]
| KboPAacDA3 wrote:
| Shamir's scheme is related to Reed-Solomon error correction.
| ms512 wrote:
| 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.
| aliljet wrote:
| 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?
| gnarula wrote:
| Refer:
| https://github.com/dedis/kyber/blob/master/share/vss/rabin/v...
| and
| https://github.com/dedis/kyber/blob/master/share/vss/pederse...
| thehumanmeat wrote:
| Plenty. Look into publicly verifiable secret sharing.
| https://en.wikipedia.org/wiki/Publicly_Verifiable_Secret_Sha...
| anonymousDan wrote:
| 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?
| lrvick wrote:
| See my other comment in this thread which details a
| solution to this.
| jbergknoff wrote:
| 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
| h0h0h0h0111 wrote:
| A similar scheme we use in drand is this: https://www.researc
| hgate.net/publication/225722958_Secure_Di...
| lrvick wrote:
| 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.
| generalizations wrote:
| > 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.
| lrvick wrote:
| 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.
| generalizations wrote:
| 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.
| anonymousDan wrote:
| 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.
| chinchilla2020 wrote:
| 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.
| jesper_br wrote:
| 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 :)
| plopilop wrote:
| 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.
___________________________________________________________________
(page generated 2022-10-27 23:01 UTC)