Shamir's Secret Sharing | Hacker News Reader

Shamir's Secret Sharing

en.wikipedia.org

177 pointsfisian45 comments

Vault(https://www.vaultproject.io/) and Phaistos KMS (https://github.com/phaistos-networks/KMS) both use SSD for sealing/unsealing, where a master key is created, 'divided' into multiple keys and a minimum number of such keys are required to unseal the service.

SSSS?

I'm not a mathematician but here is my ELI5 understanding of it based on linked wikipedia article.

If you know the coordinates of any 2 points on a line you can recover the equation for that line. The same is true for 3 points on a quadratic curve and 4 points on cubic curve, etc.

So if our secret is the number c we can put it in the equation for, say, a quadratic: ax^2 + bx + c = 0 We can then give any number of people the coordinates for different single points on this curve.

None of these people know the equation but if any 3 of them share their coordinates they can work out the equation and thus the value of c.

Just remember the caveat with the ELI5 explanation is that if I tell you the first two points on a parabola are (0,0) and (1,0) you will figure that the third point is more likely to be around (2,0) than, say, (2,2^30).

I could understand the integer arithmetic example they gave and I think you are pointing out how this is flawed security-wise (its use lies in explaining the method). This flaw is addressed by using finite field arithmetic but I did't understand that part too well.

The modulo reduction used in finite fields essentially "scrambles" the structure of many objects.

Finite field arithmetic is basically what you would get if you were to reduce the integers to a set of finite size, but keep the arithmetic rules similar to what they were before. Using an infinite set like the integers is a bad idea because you can't have a uniform distribution over all the integers, and hence some members will be more likely than others, which leaks information. The special case of finite-field arithmetic we usually care about is GF(p), which is when the integers start at 0 and wrap around at p, where p is a prime number. We care about this because when p is prime, then we can ensure numbers are uniformly random in the range 0..p-1, which is something we need in order to guarantee information-theoretic security.

If you take it one step further and show how it still works modulo p, the algorithm serves as a great introduction to how and why finite fields are used in cryptography.

A good ELI5 analogy is the Pythagoras' theorem [1]. Its taught here (NL) at school at around age 12, so its not quite ELI5 but closest I can think of.

[1] https://en.wikipedia.org/wiki/Pythagorean_theorem

Shamir’s Secret Sharing is one of my favorite algorithm names. It sounds straight out of a D&D wizard spell list. Especially when you interpret it as ”sharing in secret” instead of ”sharing a secret”.

It helps that Shamir as well as making the name alliterative also sounds like the stage name for some early 20th century magician

I think it's possible that his family name derives from https://en.wikipedia.org/wiki/Solomon%27s_shamir.

Thank you. Explains why I like the name so much!

Not to mention that it abbreviates to "SSS". I quickly looked up the D&D player's handbook and sure enough: Mordenkainen's Magnificent Mansion[0]

[0] http://forgottenrealms.wikia.com/wiki/Mordenkainen%27s_magni...

Greg Maxwell has suggested that quite a few implementations of SSS are broken: "FWIW, virtually every SSS thing I've seen out there is just wrong in at least some less serious way. In general I've found secret sharing to be part of a pretextual security practice that seldom helps users against realistic threats, and the thoughtlessness of using it is usually reflected in the implementation." - https://np.reddit.com/r/Bitcoin/comments/72dfy1/armory_walle...

Here is one seriously broken implementation he discovered: https://bitcointalk.org/index.php?topic=2199659.0

Suppose I asked if there's a practical example of merkle trees in the wild. Someone answers, "of course: git." Then 7 troglodyte friends and I jump on github/gitlab/whatever (which is super easy because everyone already uses one of these user-friendly services that wrap around git) and immediately see how git helps us develop by leveraging merkle trees. We realize that the merkle trees are leveraged so that we can ensure (most of the time) data integrity in the history of our source code. Thanks, git!

Now suppose I asked if there's a practical example of SSS in the wild. Someone answers, "of course: ___." Then 7 troglodyte friends and I jump on ___ (which is super easy because everyone already uses one of these user-friendly services that wrap around ___)and immediately see how ___ helps us develop by leveraging SSS. We realize that SSS is leveraged so that we can ensure ___. Thanks, ___!

Fill in the blanks.

Fill in: DNSSEC.

"Paul Kane -- who lives in the Bradford-on-Avon area -- has been chosen to look after one of seven keys, which will 'restart the world wide web' in the event of a catastrophic event."

https://www.schneier.com/blog/archives/2010/07/dnssec_root_k...

So in the event of a catastrophe, the key holders will restart the hierarchy by using a system no one else has seen but Bruce Schneier guesses is most likely SSS.

I was looking for an example a bit more concrete and inspectable than that.

I won't follow your script, but here's a nodejs implementation of SSS https://github.com/grempe/secrets.js

I've seen SSS used in Ethereum smart-contracts before. Grid+ https://blog.gridplus.io/simple-security-with-shamir-secret-... and Blockstack: https://github.com/blockstack/secret-sharing and uPort: https://github.com/uport-project/sss-wasm come to mind.

`poly_utils.py` in https://github.com/ethereum/research/tree/master/mimc_stark is a fairly simple one-file general-purpose library for arithmetic over prime fields, including multi-point evaluation and Lagrange interpolation; secret sharing and erasure coding are quite easy to implement with these primitives.

Thanks for the link, I'll have a look!

Hashicorp Vault: https://www.vaultproject.io/

It uses SSS for its startup process.

If you trust your seven friends, then you can use SSS to pass on digital assets after you die.

Decide on a policy. For example, 4 of your 7 friends need to agree that you've been dead/incapacitated for 90 days, and that once that happens they should give your digital assets to Recipient R (probably your next of kin). Pick a master passphrase that decrypts something interesting like a passphrase manager database file. Split the master passphrase using a 4-of-7 scheme. Distribute the seven shares to your seven friends (one to each friend). Now you know the passphrase manager won't be compromised before your death unless you are careless with the master passphrase, or four of your seven friends either collude, get hacked, or honor a legal demand to produce the shares.

This gets interesting when the digital-asset ownership is determined exclusively by cryptography. The money in your bank account is not such a thing (a suitably official-looking piece of paper will release your money to anyone), but Bitcoin or Ethereum definitely are (no court order or lead pipe can solve the discrete logarithm problem).

Such classes of assets are very new. So there are not yet any "practical examples in the wild" that an ordinary person would be likely to recognize.

Hashicorp Vault uses SSS as part of its security model for unsealing the data.

https://www.vaultproject.io/docs/internals/security.html

It's amazing how this is a practical piece of math that can be understood with little more than a basic familiarity with polynomials. This is the kind of stuff I'd loved to have learned in middle school!

It was used in my college Discrete Math class (a version specifically aimed at Computer Science students) as an exercise in formally proving the properties of a real-life system. That was a fun lecture :-D

One of my favorite Shamir implementations:

https://github.com/codahale/shamir

Reminds me a lot of my usenet newsgroup file sharing days and the PAR parity format. A file is split into say 200 pieces to fit within the limitations of a newsgroup post. Those 200 posts may or may not all make it to your usenet server, but an additional 10-20 parity files are also created such that you need to only find 200 total unique pieces to recreate the data.

It's different in that the data is totally readable other than the missing pieces (although practically unusable). The thing that blew my mind was just how a single parity file can fill a single gap regardless of where in the sequence of original files.

Many storage media formats and network protocols use closely related schemes to transparently handle minor defects and disruptions [1].

The more general theoretical category is the erasure code [2].

[1] https://www.cs.cmu.edu/~guyb/realworld/reedsolomon/reed_solo...

[2] https://en.wikipedia.org/wiki/Erasure_code

Also the HDCP master key and how it was cracked:

https://en.wikipedia.org/wiki/High-bandwidth_Digital_Content...

https://en.wikipedia.org/wiki/Key_selection_vector

This is one of the most elegant things, ever.

Polynomials are special

Ever since learning about this I've wanted to use it for something, but I've never had the opportunity.

Consider you want to share the passwords to your bank accounts with your family after you die.

You take a list of those passwords, and encrypt it using SSSS with 4 of 7 keys needed to decrypt.

You then share these 7 keys with your 7 relatives.

After your death, they get together and unlock your passwords.

They can access the bank accounts, but can they legally perform any meaningful transaction with the data/money they access?

For example-- suppose that person dies and these 7 relatives access the account and wire themselves some money. With no other arrangements made, doesn't that constitute bank fraud?

On the flip side-- if the relatives also have to go through the time-consuming processes of meetings with an estate lawyer and bank managers in order to fulfill the wishes of the deceased, what function does the cryptography perform in this case?

Maybe your bank accounts are held in nominee officer shelf corps in offshore companies. I used an arbitrary example as a vehicle to show how the m of n could access info.

Yeah, I know of plenty of use-cases for it but I have never worked on a project that required a secret sharing capability. I'm too lazy to make a product just because I want to use a cool algorithm.

However, during the data retention debate in Norway I repeatedly pointed out that the only responsible way to implement the act would be to use secret sharing to ensure that a sufficient number of parties were involved when unlocking someone's private data.

Exactly. Consider the case where you require one and only one security officer that has one and only one key. In that scenario the security officer can escrow with encryption the key file using SSSS . You could then distribute the SSSS keys to various executives who could use quorum to retrieve the escrowed key.

I came across Shamir's Secret Sharing recently when thinking about how a partial password scheme might best be implemented. I even went as far as writing up an implementation of the cryptographic aspects.

https://jonathanstreet.com/blog/partial-passwords/

Somewhat interesting article on secret sharing being used to store Hardware private keys https://medium.com/@markstar/backup-your-trezor-ledger-using...

http://web.archive.org/web/20031002050746/http://atrey.karli...

NuCypher uses this on our proxy re-encryption scheme. You don't want a re-encryption key to be all together in one place, so we split it up using SSS and distribute the fragments. For cryptography beginners, this scheme is relatively easy to understand, describe, and prove.

Popular implementations:

http://point-at-infinity.org/ssss/

https://git.gitano.org.uk/libgfshare.git/

In my undergraduate final year project, we used a "variation" of SSS called Thien-Lin Secret Sharing to enable bank locker security! Glad to see SSS being shared here!

secret sharing for javascript, https://github.com/grempe/secrets.js

DNS root server keys?

Wonder if this has been used in any commercial transaction escrow systems.

Reply on news.ycombinator.com