8 ms·

Shamir's Secret Sharing

177 points by fisian 8y ago

mirimir 8y ago
This is one of the most elegant things, ever.
- yyzhero 8y ago
  Polynomials are special
markpapadakis 8y ago
Vault(https://www.vaultproject.io/ https://www.vaultproject.io/) and Phaistos KMS (https://github.com/phaistos-networks/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.
- pmarreck 8y ago
  SSSS?
textmode 8y ago
http://web.archive.org/web/20031002050746/http://atrey.karlin.mff.cuni.cz:80/~clock/twibright/schizzors/index.html http://web.archive.org/web/20031002050746/http://atrey.karli...
nanimo 8y ago
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!
- azernik 8y ago
  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
Cieplak 8y ago
One of my favorite Shamir implementations: https://github.com/codahale/shamir https://github.com/codahale/shamir
bborud 8y ago
Ever since learning about this I've wanted to use it for something, but I've never had the opportunity.
- late2part 8y ago
  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.
  - jancsika 8y ago
    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?
    - late2part 8y ago
      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.
  - bborud 8y ago
    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.
jwilk 8y ago
Popular implementations: http://point-at-infinity.org/ssss/ http://point-at-infinity.org/ssss/ https://git.gitano.org.uk/libgfshare.git/ https://git.gitano.org.uk/libgfshare.git/
streety 8y ago
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/ https://jonathanstreet.com/blog/partial-passwords/
Sharlin 8y ago
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”.
- barking 8y ago
  It helps that Shamir as well as making the name alliterative also sounds like the stage name for some early 20th century magician
  - schoen 8y ago
    I think it's possible that his family name derives from https://en.wikipedia.org/wiki/Solomon%27s_shamir https://en.wikipedia.org/wiki/Solomon%27s_shamir.
- deleted 8y ago
  [deleted]
- vagab0nd 8y ago
  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_magnificent_mansion http://forgottenrealms.wikia.com/wiki/Mordenkainen%27s_magni...
barking 8y ago
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.
- mehrdadn 8y ago
  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).
  - barking 8y ago
    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.
    - blattimwind 8y ago
      The modulo reduction used in finite fields essentially "scrambles" the structure of many objects.
    - mehrdadn 8y ago
      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.
ballenf 8y ago
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.
- 0xcde4c3db 8y ago
  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_solomon_codes.html https://www.cs.cmu.edu/~guyb/realworld/reedsolomon/reed_solo... [2] https://en.wikipedia.org/wiki/Erasure_code https://en.wikipedia.org/wiki/Erasure_code
- userbinator 8y ago
  Also the HDCP master key and how it was cracked: https://en.wikipedia.org/wiki/High-bandwidth_Digital_Content_Protection#Cryptanalysis https://en.wikipedia.org/wiki/High-bandwidth_Digital_Content... https://en.wikipedia.org/wiki/Key_selection_vector https://en.wikipedia.org/wiki/Key_selection_vector
discobean 8y ago
Somewhat interesting article on secret sharing being used to store Hardware private keys https://medium.com/@markstar/backup-your-trezor-ledger-using-shamirs-secret-sharing-972e98101839 https://medium.com/@markstar/backup-your-trezor-ledger-using...
brianzelip 8y ago
secret sharing for javascript, https://github.com/grempe/secrets.js https://github.com/grempe/secrets.js
jancsika 8y ago
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.
- petra 8y ago
  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_key.html https://www.schneier.com/blog/archives/2010/07/dnssec_root_k...
  - jancsika 8y ago
    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.
- decentralised 8y ago
  I won't follow your script, but here's a nodejs implementation of SSS https://github.com/grempe/secrets.js 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-sharing-15704166b8be https://blog.gridplus.io/simple-security-with-shamir-secret-... and Blockstack: https://github.com/blockstack/secret-sharing https://github.com/blockstack/secret-sharing and uPort: https://github.com/uport-project/sss-wasm https://github.com/uport-project/sss-wasm come to mind.
tuxxy 8y ago
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.
jron 8y ago
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_wallet_fragmented_backups_may_be/dnho2w6/ 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 https://bitcointalk.org/index.php?topic=2199659.0
badrabbit 8y ago
DNS root server keys? Wonder if this has been used in any commercial transaction escrow systems.
darshitpp 8y ago
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!

177 points by fisian 8y ago

mirimir 8y ago

This is one of the most elegant things, ever.

yyzhero 8y ago
Polynomials are special

markpapadakis 8y ago

Vault(https://www.vaultproject.io/ https://www.vaultproject.io/) and Phaistos KMS (https://github.com/phaistos-networks/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.

pmarreck 8y ago
SSSS?

textmode 8y ago

http://web.archive.org/web/20031002050746/http://atrey.karlin.mff.cuni.cz:80/~clock/twibright/schizzors/index.html http://web.archive.org/web/20031002050746/http://atrey.karli...

nanimo 8y ago

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!

azernik 8y ago
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

Cieplak 8y ago

One of my favorite Shamir implementations: https://github.com/codahale/shamir https://github.com/codahale/shamir

bborud 8y ago

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

late2part 8y ago
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.
- jancsika 8y ago
  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?
  - late2part 8y ago
    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.
- bborud 8y ago
  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.

jwilk 8y ago

Popular implementations: http://point-at-infinity.org/ssss/ http://point-at-infinity.org/ssss/ https://git.gitano.org.uk/libgfshare.git/ https://git.gitano.org.uk/libgfshare.git/

streety 8y ago

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/ https://jonathanstreet.com/blog/partial-passwords/

Sharlin 8y ago

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

barking 8y ago
It helps that Shamir as well as making the name alliterative also sounds like the stage name for some early 20th century magician
- schoen 8y ago
  I think it's possible that his family name derives from https://en.wikipedia.org/wiki/Solomon%27s_shamir https://en.wikipedia.org/wiki/Solomon%27s_shamir.
deleted 8y ago
[deleted]
vagab0nd 8y ago
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_magnificent_mansion http://forgottenrealms.wikia.com/wiki/Mordenkainen%27s_magni...

barking 8y ago

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.

mehrdadn 8y ago
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).
- barking 8y ago
  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.
  - blattimwind 8y ago
    The modulo reduction used in finite fields essentially "scrambles" the structure of many objects.
  - mehrdadn 8y ago
    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.

ballenf 8y ago

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.

0xcde4c3db 8y ago
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_solomon_codes.html https://www.cs.cmu.edu/~guyb/realworld/reedsolomon/reed_solo... [2] https://en.wikipedia.org/wiki/Erasure_code https://en.wikipedia.org/wiki/Erasure_code
userbinator 8y ago
Also the HDCP master key and how it was cracked: https://en.wikipedia.org/wiki/High-bandwidth_Digital_Content_Protection#Cryptanalysis https://en.wikipedia.org/wiki/High-bandwidth_Digital_Content... https://en.wikipedia.org/wiki/Key_selection_vector https://en.wikipedia.org/wiki/Key_selection_vector

discobean 8y ago

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

brianzelip 8y ago

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

jancsika 8y ago

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.

petra 8y ago
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_key.html https://www.schneier.com/blog/archives/2010/07/dnssec_root_k...
- jancsika 8y ago
  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.
decentralised 8y ago
I won't follow your script, but here's a nodejs implementation of SSS https://github.com/grempe/secrets.js 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-sharing-15704166b8be https://blog.gridplus.io/simple-security-with-shamir-secret-... and Blockstack: https://github.com/blockstack/secret-sharing https://github.com/blockstack/secret-sharing and uPort: https://github.com/uport-project/sss-wasm https://github.com/uport-project/sss-wasm come to mind.

tuxxy 8y ago

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.

jron 8y ago

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_wallet_fragmented_backups_may_be/dnho2w6/ 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 https://bitcointalk.org/index.php?topic=2199659.0

badrabbit 8y ago

DNS root server keys? Wonder if this has been used in any commercial transaction escrow systems.

darshitpp 8y ago

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!