5 ms·
Ssss: Shamir's Secret Sharing Scheme (2006)
- dijit 4y agoHa! 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 4y agoWritten 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....
- pjkundert 4y agoBackup 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 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!
- nuggimane 4y agoIf anyone is interested in understanding Shamir's scheme a bit more, this blog post visualises it well! :) https://evervault.com/blog/shamir-secret-sharing https://evervault.com/blog/shamir-secret-sharing
- aliqot 4y ago
- pkage 4y agoiiuc HN flags new accounts by creation time and not activity (e.g. less than N days old)
- aliqot 4y agoiiuc 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 4y agoThis 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 4y agoYeah I don't really comment but knew it was relevant to this thread so figured I would for once
- aliqot 4y ago
- deleted 4y ago[deleted]
- yodon 4y agoPost 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 https://github.com/topics/shamir-secret-sharing
- dennis-tra 4y agoA 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 https://github.com/dennis-tra/shamir It combines the two separate commands in the article into one.
- KboPAacDA3 4y agoShamir's scheme is related to Reed-Solomon error correction.
- ms512 4y agoSome 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.
- jron 4y agoHere is a great talk on new SSS library from Daan Sprenkels at 34C3: https://www.youtube.com/watch?v=ojMFCpUt7OU https://www.youtube.com/watch?v=ojMFCpUt7OU Implementation: https://github.com/dsprenkels/sss https://github.com/dsprenkels/sss
- nullc 4y agoIt'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!
- aliljet 4y agoThis 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?
- thehumanmeat 4y agoPlenty. Look into publicly verifiable secret sharing. https://en.wikipedia.org/wiki/Publicly_Verifiable_Secret_Sharing https://en.wikipedia.org/wiki/Publicly_Verifiable_Secret_Sha...
- anonymousDan 4y agoThat 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 4y agoSee my other comment in this thread which details a solution to this.
- anonymousDan 4y agoInteresting 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.
- jbergknoff 4y agoYes, 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 https://eprint.iacr.org/2020/852.pdf [1] https://en.wikipedia.org/wiki/Distributed_key_generation https://en.wikipedia.org/wiki/Distributed_key_generation
- deleted 4y ago[deleted]
- wslh 4y agoUse MPC instead? Sadly there are not enough mature open source projects around: https://github.com/ZenGo-X/multi-party-ecdsa https://github.com/ZenGo-X/multi-party-ecdsa and you can always take a look at https://github.com/rdragos/awesome-mpc 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 https://github.com/unboundsecurity/blockchain-crypto-mpc
- deleted 4y ago[deleted]
- computerfriend 4y agoI'd recommend using libgfshare over ssss, if you're looking for a command-line application.
- nullc 4y agohttps://github.com/jcushman/libgfshare/blob/master/src/libgfshare.c#L311 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.)
- olah_1 4y agoArgent’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-About-guardians https://support.argent.xyz/hc/en-us/articles/360022631992-Ab...
- elcritch 4y agoImplementing 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 https://github.com/elcritch/keyxn - keyx https://github.com/elcritch/keyx https://github.com/elcritch/keyx
- nullc 4y ago> 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.
- elcritch 4y agoAh 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.
- nullc 4y agoIn 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!
- nullc 4y agohttps://en.bitcoin.it/wiki/Shamir_Secret_Snakeoil https://en.bitcoin.it/wiki/Shamir_Secret_Snakeoil