7 ms·
Shamir Secret Sharing
- ThePowerOfFuet 3y ago>The idea (proposed by Adi Shamir – the A of RSA! – in 1979) is as simple as it is beautiful. Leonard Adleman might have something to say about that sentence.
- codetrotter 3y agoTrue. Adi Shamir is the S. Rivest–Shamir–Adleman
- bschne 3y agoadi shamiR (I'm sorry)
- sangnoir 3y agoAlternative history/facts: all the letters in RSA are from Adi Shamir's unixname (rsa). Because 'asr' (Adi ShamiR) was already taken, he started using the reversed string instead ('rsa'), and used it as the command name for the first unix implementation of the RSA algorithm, which he developed all by himself.
- ketzu 3y agoIf Adleman just had a first name starting with S, it would still work!
- richardwhiuk 3y agoleona*R*d adleman, ron rive*S*t, and *A*di shamir, clearly.
- eru 3y agoWouldn't that be Adi Shamir?
- seanhunter 3y agoAdleman is the S in RSA
- firesteelrain 3y agoNow we have HashiCorp Vault that serves this purpose and uses shamir.
- nightpool 3y agoYes, I agree, HashiCorp Vault definitely serves the purpose of having a single point of failure that can go down and take your entire company down with it, just like in the story :P (c.f. Roblox)
- xtracto 3y agoAaah, we had something like this happen to a k8s cluster that had secrets stored in a HC Vault. The vault got sealed and the keys lost. That was it...
- snowstormsun 3y agoHow did you recover?
- xtracto 3y agoWe didn't. We had to create a new vault with new secrets and properly safeguard the key shares this time.
- firesteelrain 3y agoI mean you could have a Vault and Consul cluster with auto unsealing.
- tzs 3y agoFor those who would like to play around with Shamir secret sharing, here is a Python implementation I wrote to check out something I was curious about [1]. Note: requires at least Python 3.8. The function make_sss(secret, num_shares, p=0) makes a polynomial for sharing the given secret that requires num_shares shares to recover. P is the prime. If p is 0 then make_sss will pick a random prime large enough for the secret. Make_sss returns the prime and the polynomial. The polynomial is represented by an array of coefficients. The function make_share(sss, i) takes a secret sharing scheme sss of the form [p, polynomial] and returns share i. The function recover_secret(share_list, p) takes an array of num_shares shares and the prime, and return the polynomial. Each share in the share list is represented by an array that contains the share number and the share. If you run this from the command line it will run a demo. The demo will make a random 128 bit secret, use make_sss to make a sharing system for that secret that requires 3 shares for recover, print the prime and the polynomial, then generate 3 shares (shares 1, 2, and 5), use those shares to recover the polynomial and print the recovered polynomial, and finally print the 3 shares. This implementation is a bit different from most others I've seen. Most use Lagrange interpolating polynomials to recover the polynomial fro a set of shares. I was curious about whether it would work reasonably to instead just solve the system of linear equations for recovery the way I would have done it by hand in high school--good old fashioned straightforward Gaussian elimination. [1] https://pastebin.com/zePiXVUj https://pastebin.com/zePiXVUj
- computerfriend 3y agoNice! When I first heard of SSS, but before I looked it up, this was my assumption for how it worked. Seems just as good as polynomial interpolation.
- l1am0 3y agoBuild an online tool to use shamir secret sharing :) https://simon-frey.com/s4/ https://simon-frey.com/s4/
- kirushik 3y agoOK, since we're pitching our SSS implementations here in comments, I welcome everyone to check out BananaSplit, https://bs.parity.io https://bs.parity.io Not sure about year 2023, but at the time I wrote it for my previous employer there was nothing remotely usable for regular user. Thus, BananaSplit. It doesn't allow you to specify many parameters (just the number of shards, and then requires 50%+1 to recover); aimed at printed backups (generates printable full-page QR codes, while asking to copy a decryption phrase to the pages by hand to avoid an "evil printer" attack); and takes the concept of _portable web app_ to its extreme, being a self-contained single html file which requires you to save it locally and open via file:// protocol for it to work. Disclaimer: while being in use for years, the code had never seen a proper independent code review; there might be bugs, despite me trying to minimize their impact by design, and using only reputable (and pretty minimalistic) JS primitives. If you want to check out the sources yourself before using, of course those are available under GPL at https://github.com/paritytech/banana_split/ https://github.com/paritytech/banana_split/
- franky47 3y agoI like how it pushes you towards safety by requiring the code to run offline and off the disk. The resulting UX is not that great (though the explanation of what to do is clear), but it's a good step towards a little bit more security.
- stavros 3y agoOn the contrary, I hated it. I just want to see the UI, I don't want to go offline! Give me an "I'm just playing around, I promise!" button I can click on to test it.
- cornstalks 3y agoInteresting idea, but the restore function doesn't work for me. Access to fetch at 'file://redacted/Banana%20split.html#/combine' from origin 'null' has been blocked by CORS policy: Cross origin requests are only supported for protocol schemes: http, data, isolated-app, chrome-extension, chrome, https, chrome-untrusted.
- c7b 3y agoDoes this count as an instance of 'don't roll your own crypto'?
- HWR_14 3y agoNot at all. The problem was that the crypto for the same library on two different OSes was implemented differently, which lead to an error encrypting on Linux and decrypting on Solaris. Ironically, this would have been avoided if they had rolled their own. It is an instance of "make sure you have backups when deploying to production"
- devit 3y agoNot the crypto, but rather the getpass() function, which simply reads a password from standard input without echoing it. Since the function uses a static buffer, there is a limit on the password length, which apparently on Solaris was set to the absurdly low value of 8 (glibc uses a more reasonable value: 8192).
- HWR_14 3y agoThanks for the correction. I assumed getpass() did some crypto work in addition to just getting raw keyboard input.
- sangnoir 3y agoI think it's more of an instance of "it works on my computer"; not testing on an environment sufficiently similar to production, and applying a change that cannot be rolled back.
- kevincox 3y agoThis is the key. The rollback mechanisms were broken. Re-encrypting data is incredibly scary because if you lose the new key you have effectively lost your data. It is important to ensure that you have up-to-date backups of the previously encrypted data and key before you start. A better solution may have been multi-key support. Some test records could be encrypted with the new key and the system let run for a week or so. Then all new records could start being encrypted with the new key and run for another week. Once everything looks good a background job could be started to convert all data to the new key. Then the old key can be retired (other than as needed for backups). Although they did have the key printed in an envelope, so it sounds like that would have been an effective recovery solution once they remembered.
- franky47 3y agoAdding on to the pile of "Show HN your SSS playground", here's mine: https://francoisbest.com/horcrux https://francoisbest.com/horcrux
- fullwaza 3y agoha! Great name for it
- humblepie 3y agoIs there an alternative scheme that allows the different parties to enter their own password?
- Tomte 3y agoSymmetrically encrypt their share with the chosen password.
- ecesena 3y agoNot with passwords of their choice. You could use SSS in combination with BIP to derive a set of 12 or 24-word passphrases, this might be a bit more user friendly.
- opendomain 3y agocan you give more information please?
- pests 3y agoBIP39 is the Bitcoin standard which defines the process to generate the human readable "recovery phrase" for a Bitcoin wallet based on the private key. It's a list of 2048 pre-defiend words. Your private key is chunked into 11bit groups (with a few bits for a checksum) and then assigned the corresponding word.
- dcow 3y agoIt already exists: https://github.com/satoshilabs/slips/blob/master/slip-0039.md https://github.com/satoshilabs/slips/blob/master/slip-0039.m...
- cosmojg 3y agoYou could just take the result of running their chosen passwords through the algorithm and use that as the decryption key.
- h2odragon 3y ago`killall` was different on Solaris than Linux; too. Learning those differences by coming to Linux from Solaris was liberating; there were less limits generally. The other way around was less fun: as in this example, code that had run fine before was now subject to weird behaviors that were caused by underlying system assumptions being different. At least Solaris usually had decent documentation.
- nullc 3y agoI took down the production environment once with killall. The conversation explaining to management about why I ran something called "killall" and didn't expect it to kill all was very tense.
- valleyer 3y agoFor the uninitiated (like me), killall in Solaris kills "all active processes not directly related to the shutdown procedure" (not those with a certain name as the Linux/psmisc killall does). https://docs.oracle.com/cd/E86824_01/html/E54764/killall-1m.html https://docs.oracle.com/cd/E86824_01/html/E54764/killall-1m....
- evanfarrar 3y agoWow, he shredded the only copy of the key his database backups were encrypted with.
- rawling 3y agoNot deliberately? Old key used for the backups was accidentally erased halfway through the story, shredded key was just the last cleartext copy of the new key.
- karl_gluck 3y agoAnother implementation: https://github.com/karlgluck/ThresholdJS https://github.com/karlgluck/ThresholdJS This is a very straightforward encoding of a single 256-bit number.
- hackan 3y agoGreat story! It made me super nervous all the way. I also built a pure python lib a whole ago to use w/ an app, check it out: https://github.com/HacKanCuBa/secretshare-py https://github.com/HacKanCuBa/secretshare-py It uses prime arithmetic, which limits severally the input size, but it works pretty well and fast. Not production ready BC I haven't tested it enough, but it is a good starting point.
- dcow 3y agoFor anybody new or returning to SSS, check out SLIP-0039: https://github.com/satoshilabs/slips/blob/master/slip-0039.md https://github.com/satoshilabs/slips/blob/master/slip-0039.m... One of the big downsides of SSS is that it’s very raw and you have to do a lot of legwork to make it actually useable. For instance, you can sss_combine any arbitrary polynomial coefficients and get a result, you don’t know if the reconstituted data is correct until you try to use it. Implementations can vary in the finite field chosen because SSS doesn't specify one, and not all are equal and they are not interchangeable (coefficients from one don’t work in another). Another issue is that it’s susceptible to collusion. It’s rightfully criticized for its shortcomings and the argument follows the don’t roll your own crypto vein. SSS is like handing a dev XOR and telling them “now go encrypt things”. SLIP39 solves this by formalizing a protocol for handling SSS splits built atop standards for crypto key serialization (BIP-39). SLIP defines a standard finite field (used when interpreting the polynomial coefficients), SLIP shards are unique on each generation so parties with the same underlying SSS shard can’t compare mnemonics, they’re mnemonically serialized for humans, and they have a checksum and group index metadata which makes a more sane UX possible when combining. SLIP also describes a two layer setup so you can manage trust by cordoning people off into groups to help litigate collusion.
- rssoconnor 3y agoSLIP-0039 was pretty inspirational in the development of codex32 for doing SSS by hand on paper computers: https://secretcodex32.com/ https://secretcodex32.com/ and https://secretcodex32.com/docs/2023-03-07--color.pdf https://secretcodex32.com/docs/2023-03-07--color.pdf
- olah_1 3y agoHas this been implemented in stuff yet?
- baby 3y agoFun story. I know understand why Levchin was so involved with the real world crypto conference :) Here’s my own explanation of SSS: https://livebook.manning.com/book/real-world-cryptography/chapter-8/ https://livebook.manning.com/book/real-world-cryptography/ch...
- richman66 3y ago[flagged]
- tzs 3y agoMost descriptions of and implementations of Shamir secret sharing are a bit intimidating. If however you just need a system where any two people with shares can reconstruct the secret then SSS can be very short and simple. Let a0 = the secret p = a prime number > a0 a1 = a random integer in [1, p-1] Assign each person who is to receive a share of the secret an ID in [1, p-1]. It is OK to simply assign IDs sequentially starting at 1. Here is how to generate the share for the person with ID i: Si = (a0 + i*a1) % p Tell each person their ID and given them their share. When each person has received their ID and share you can delete a0 and a1. To recover the secret given Si from person with ID i and Sj from person with ID j, do this in Python 3.8 or later: a0 = ((j*Si - i*Sj) * pow(j-i, -1, p)) % p Pow(x, -1, m) for integers x and m in Python >= 3.8 computes the modular inverse of x mod m. If you need to generate a share for a new person or regenerate a share for an existing person get shares from two people and recover a0 as described above. Recover a1 like this: a1 = ((Sj - Si) * pow(j-i, -1, p)) % p You can then use a0 and a1 to issue or reissue shares as described earlier.
- linhvn 3y agoI'm not sure if this is intimidating. A draft implementation could be done without too much difficulty: https://gist.github.com/ll931110/985a4ec711c6711b120846be05ee25e5 https://gist.github.com/ll931110/985a4ec711c6711b120846be05e...
- nullc 3y agohttps://en.bitcoin.it/wiki/Shamir_Secret_Snakeoil https://en.bitcoin.it/wiki/Shamir_Secret_Snakeoil More on the subject of the post, this is now the third near-miss company destruction I've heard about due to SSS. Hopefully some of the others will make their stories public. The snakeoil page linked above doesn't really get into "when it's secure against you". One of the other stories I heard that was most similar to the paypal one failed for a different reason than password truncation: Since they needed the key very infrequently and most participants never (since the threshold was met by other parties) too many people forgot their passwords. A better way to use it would be to always enter all the people who were not outright unavailable and consider it a serous failure for any party to be unavailable too often.
- knallfrosch 3y agoOne guy had it on a post-it note and the other chose a$$word...
- aabdelhafez 3y agoBuilt a CLI¹ a couple of years back that uses HashiCorp Vault's implementation of the Shamir Secret Sharing algorithm and exposes its functionality to the command-line. ¹ https://github.com/incipher/shamir https://github.com/incipher/shamir
- wslh 3y agoShameless plug: ported MPC/TSS Rust implementation to WebAssembly: https://github.com/CoinFabrik/wasm-multi-party-ecdsa https://github.com/CoinFabrik/wasm-multi-party-ecdsa