6 ms·

How Shamir's Secret Sharing Works

397 points by subract 4mo ago

han1 4mo ago
[flagged]
compsciphd 4mo ago
before I learned of shamir secret sharing, I wondered why one couldn't do the same exact thing with a par2 like system (albiet with smaller pieces than a par2 system would traditionally have). i.e. you have X bits of data, you create Y*X/N sized recovery blocks (where Y > N). You hand each recovery block to individual users. and any N users can get together to recover the key and decrypt the contents.
- deleted 4mo ago
  [deleted]
- namibj 4mo ago
  Well in theory the base math is indeed the same; unfortunately though the "randomly chosen" part of shamir's secret sharing is fairly important to the security because information theoretic security of the scheme requires each fragment to be as large as the original secret by way of essentially including a desired count of random data blocks to the original before applying the reed-solomon-like erasure coding to it where now enough fragments to reconstruct the secret plus all random blocks have to be combined. Also the way of usage of the erasure code has to be selected to not be leaking information but that's more of an issue of not picking a bad way of how to implement the basic concept here. Basically just a case of "do follow the instructions to shamir's secret sharing, don't do something different just because it's a popular way of implementing reed-Solomon". Yes, you can just GF(256), but if you're worried I'd also just use a prime field instead.
teravor 4mo ago
if the secret is large usually it's encrypted and the payload is distributed along with the shares of the key. but you can also just use Reed-Solomon and split the payload, the difference with Shamir is that you lose information-theoretic security (you lose it the moment you use encryption anyway) and the payload also needs to undergo an all-or-nothing-transform (AONT). AONT transforms the entire payload into an encrypted blob which also serves as its own key, a withheld piece is a de facto encryption key. this is required because Reed-Solomon can have pathological cases where pieces leak information.
- colmmacc 4mo ago
  Reed-Solomon is an Erasure code, and I definitely wouldn't look to that for Secret Splitting. Those leakage models are gnarly. But if you want something else that is more general - there are Monotone Span Programs. Seriously underused.
  - teravor 4mo ago
    > Reed-Solomon is an Erasure code which shares the same math as Shamir > Those leakage models are gnarly. AONT solves that by making any leak other than the totality meaningless
Cider9986 4mo ago
Here is Ente's implementation: (https://2of3.ente.com/ https://2of3.ente.com/)
- emmelaich 4mo ago
  There's an implementation packaged up for most Linux distros: http://point-at-infinity.org/ssss http://point-at-infinity.org/ssss
- ahazred8ta 4mo ago
  There are several browser-based versions which can be used online or downloaded to use offline. https://bs.parity.io/ https://bs.parity.io/ -- http://passguardian.com/ http://passguardian.com/ -- https://iancoleman.io/shamir/ https://iancoleman.io/shamir/
  - davidcollantes 4mo ago
    I have noticed that not one of them is compatible with the other. I generated shares using `ssss` (https://manpages.ubuntu.com/manpages/trusty/man1/ssss-split.1.html https://manpages.ubuntu.com/manpages/trusty/man1/ssss-split....), and couldn't combine them on any of the three sites linked. That is a downside, isn't it? Do you know of a way to bypass that hurdle, other than packing resources together with the shares?
    - ahazred8ta 4mo ago
      SSSS is not the official canonical file format for SSS. Shamir did not specify an official file format when he described his technique. Each implementation knows how to recombine its own shares. The web apps can be saved and used on any device.
- Ajedi32 4mo ago
  This is my favorite one yet, very user friendly. I only wish it was a bit more configurable. Ideally I'd be able to set up something like: 3 of 4: A B C D - OR - 2 of 3: E F G - AND - 1 of 1: H Or any similar combination. Maybe also with a way to name the cards so it's clear exactly what's needed when restoring. Though there's something to be said for the simplicity of the current design.
_jackdk_ 4mo ago
This is such a cool technique, and you could even teach it in secondary schools as a neat thing computer scientists can do with polynomials.
- naths88 4mo ago
  I am a secondary math teacher and I do exactly this with my students. When working on retrieving the expression of an affine function, I tell them about Shamir'..., they choose a secret pin as the slope, generate two points, give them to two other students who have to pair together to find the pin again. The students are always very engaged.
  - _jackdk_ 4mo ago
    I'm so glad it works. If you handwave at the generalisation to quadratics and higher polynomials, do the students follow it well? I assume you don't get into the finite field stuff, but it seems like it'd be cool to handwave at "there's actually other structures where most of this polynomial stuff works, even in somewhat weird ways".
- sowbug 4mo ago
  It's the same idea as how GPS works. Fun to see someone's eyes light up when they get why that third satellite is needed to fix a 2D position. (Actual GPS is a little more complicated than that because the real system needs accurate time information.)
calvinmorrison 4mo ago
something tangentially i am interested in is computing following the 'two person rule' for things like sudo. Yes I am logged into server X at terinal Y, and so is my co-worker and we both sign off on running command X
- jerry1979 4mo ago
  That sounds like you might want to look into digital signatures.
- coryrc 4mo ago
  Had something like this at Google. There's a service running as root (or equivalent) which receives your desired command to run, and it has to get authorization from another user for the specific command to run, then runs it. That makes sense at Google, because those are production machines and have access to LDAP and who is allowed to run a command on a machine is defined by an LDAP group and you would need two of them (or more?) and there's already existing management website this can be shoe-horned into. Your environment is unlikely to have all of that already, so you'll need to figure out equivalents for all those. But I think you're going to need a local service running as root and it's going to need to be able to tell the difference between distinct human users, if you want secure. Just typos is way easier.
- ahazred8ta 4mo ago
  There's a related 2-man sudo login system here, not sure how finegrained it is. https://github.com/Argonne-National-Laboratory/Pam-2man-Auth https://github.com/Argonne-National-Laboratory/Pam-2man-Auth
- timv 4mo ago
  I wrote something like that about 15 years ago for a financial institution. For what we needed, we intentionally wanted both people to be at the same terminal (it was going to be used to give shell access to a specific unix account that ran a critical system). That mean that we could implement it as a setuid (root) binary that required both users to authenticate. It had a config file that worked like sudoers, and defined a list of commands that could be called, how many people were needed to authenticate, and which unix groups they had to belong to.
3eb7988a1663 4mo ago
Do the people who hold the root DNS keys do anything like this? Or is that too much complexity when a safe in a secure room works as an effective backup?
- davkan 4mo ago
  They do something similar. Basically 5 people are needed in order to access the dns root keys plus some extra administrative/witness people. 3 Crypto Officers with smartcards to unlock the hsm, 2 other officials to unlock the vault that contains the hsm and the vault that contains safety deposit boxes with the smartcards. There are 7 crypto officers, of which any three will do. https://www.cloudflare.com/learning/dns/dnssec/root-signing-ceremony/ https://www.cloudflare.com/learning/dns/dnssec/root-signing-...
- UltraSane 4mo ago
  They go into extreme detail about DNSsec root key security https://blog.apnic.net/2021/10/12/dns-security-and-key-ceremonies/ https://blog.apnic.net/2021/10/12/dns-security-and-key-cerem...
cryptoz 4mo ago
See also a story about an implementation from Max Levchin: https://max.levch.in/post/724289457144070144/shamir-secret-sharing-its-3am-paul-the-head-of https://max.levch.in/post/724289457144070144/shamir-secret-s...
- avicado0o 4mo ago
  this story is wildd
sreekanth850 4mo ago
ente means mine in Malayalam language. it's said to be one of the toughest Indian language to learn. FYI.
- alfirous 4mo ago
  Interesting, in Indonesia Ente means you. Derived from Arabic word Anta. Fascinating how sometimes in different languages one word can have opposite meaning and the other times one word can have similar meaning.
  - aabdelhafez 4mo ago
    Ente also means "duck" in German.
  - thisislife2 4mo ago
    Maybe it's the pronunciation - ente means "mine" and ante means "yours" (in Malayalam) which is what perhaps you may be referring to? (Former South Indian kingdoms and South East Asia have historical cultural ties due to trade and conquest, and thus they share some common words, which I assume is, largely borrowed from Tamil and Malayalam).
    - sreekanth850 4mo ago
      Some people use ante to mean yours in the northern region, but it is not common in the southern region.
- ignoramous 4mo ago
  > it's said to be one of the toughest Indian language to learn. By who? My SO is now passably conversant in Malayalam after watching their cinema during the covid lockdowns (~1y to 2y).
  - sreekanth850 4mo ago
    By other indians. And indian military use malayalam to communicate, so that enemies cannot intercept. There was a report that chinese started learning south indian languages. Most movies use neutral phonetics (written language) where as spoken language is tough to understand and have many regional vriations.
ghostfoxgod 4mo ago
It's an incredible technique, when I came across it, it just changed the way I thought of solving giving out keys without "truly" giving them out. This gave me confidence for eternalvault.app, a project of mine.
- hamburglar 4mo ago
  I’ve been noodling over this exact business idea for a couple years! Part of my value prop was to make ops scale down to as close to zero as possible by having the encrypted data and most of the front end for accessing it live in S3 objects (or some similar mega-cheap object store). Aside from that, all you need is the dead man’s switch mechanism. And the secret fragments would live on QR codes that bring you to the static SPA with one of the fragments already loaded up, prompting you to scan more to complete the decryption. Good work doing it. I guess now I don’t have to. :D You may have gained a customer from this HN thread.
  - ghostfoxgod 4mo ago
    Indeed, that's precisely why I decided to ditch out of the subscription model and went into one time payment method, did the math and it made sense that I don't need a very heavy system apart from supporting the dead man switch trigger Wrote my thoughts about that here: https://eternalvault.app/blog/why-we-are-adding-lifetime-pricing/ https://eternalvault.app/blog/why-we-are-adding-lifetime-pri... And it feels good to know that there are people out thinking about this, makes me happy truly and if you want to try out the platform, welcome aboard, happy to walk through it if needed. :)
    - hamburglar 4mo ago
      That’s great, and exactly what I was thinking. In fact, you have to wrestle with the fact that if it’s too cheap, people won’t trust it. One thing I had been thinking about was that it’s important to be extremely open about the algorithms and infrastructure required, with a very transparent whitepaper on how it works (enthusiast level discussion of the technical details) and how you have designed the company to be extremely sustainable. I think your job is to convince people of two things: 1) this actually respects my privacy in a way I can verify myself (or lean on the technical expertise of other outside observers), 2) this company actually has a chance of surviving until I die. If I can see those two things are true, a $199 lifetime purchase is a no-brainer (and that probably covers a dozen lifetime members’ operational costs). :D
ndr_ 4mo ago
Bruce Schneier described this in his seminal book Applied Cryptography, and HashiCorp Vault used to have an implementation in Go. On the practical side, I always wondered how large - in bits - the shares should be. One answer I got on a news group was "1 bit more than the actual key length". Nowadays, I wonder how the quantum computing threat would inform 1) share size choice and 2) pro/con Secret Sharing in general. Does anyone know?
- andreareina 4mo ago
  Do you remember why 1 bit more?
  - asksomeoneelse 4mo ago
    Just spitballing; I have seen prefixing integers of arbitrary length with a bit 1 as the most significant bit as a way to avoid loosing the leading 0s when serializing the integers if the size is important. Also, IIRC, it's possible to implement shamir using arbitrary length integers instead of a common finite field. Not sure why someone would recommend doing either in that context though.
  - ndr_ 4mo ago
    It was phrased as "to distinguish all possible secrets": https://groups.google.com/g/sci.crypt/c/siuibXhcUGc/m/wTpAEObAtQkJ https://groups.google.com/g/sci.crypt/c/siuibXhcUGc/m/wTpAEO...
- proxysna 4mo ago
  I think hashicorp still have an implementation for vaults seal/unseal process. Unless something changed ofc
  - bigfatkitten 4mo ago
    They still do indeed.
- plopilop 4mo ago
  You usually do secret sharing in a finite field because computers don't like real numbers. The size of your share is a point (x, y), x can be small (typically log n in case of n participants), y is a random point in the field. Since Shamir Secret Sharing is information-theoretically secure (if you do not know k points from the k-out-of-n secret then all secrets are equally plausible even when bruteforcing), the bitsize of your field can be whatever you want (but obviously bigger than the bitsize of your secret, you can't hide 100 bits in a finite field of 5 elements). Usually, you don't want an attacker to be able to bruteforce your secret (while the scheme is ITS, your secret typically isn't, e.g. the seed of your wallet), hence randomness can be added to your secret and the bitsize of the field is taken big enough to thwart these attacks. Depending on your attack model, an 80-bits or 128-bits field is more than secure enough, hence a share bitsize slightly above 80 or 128 bits. And regarding quantum computer, since the scheme is ITS no attacks can exist.
craintes 4mo ago
I also had written an article on the subject a while ago if you want to dig a bit deeper: https://petal.cafe/posts/shamir/ https://petal.cafe/posts/shamir/
freakynit 4mo ago
This is such a cool neat trick. Vibe-coded a little playground where you can generate secrets, see the polynomial, combine the secrets, and in general, play around: https://shamirs-secret-sharing.pagey.site https://shamirs-secret-sharing.pagey.site
l1am0 4mo ago
Years ago I build a little tool to run shamir secret sharing in the browser (can be used full offline, just download the page) https://simon-frey.com/s4/ https://simon-frey.com/s4/
- xtracto 4mo ago
  Ha! Years ago i downloaded your page and stored it in some usb disks along with my kdb keepass database and a share of my password. I gave that to some members of my family and instruct them to give them to my wife in case I die. Thanks a lot Sir.
Tepix 4mo ago
Instead of going from two lines to curves, parabolas etc, couldn't you also add another dimension instead?
- nitnelave 4mo ago
  Two points make a line in any number of dimensions.
  - cynicalkane 4mo ago
    Think GP is suggesting an N-dimensional plane in K>N dimensions.
  - Levitz 4mo ago
    Yes, but without a specific plane to intersect with, that still doesn't define a third point, if you want to check intersection with an axis, you'd need a third point in tridimensional space, for example.
- nyeah 4mo ago
  Yes? If I use 3 shares and require all three to recover, then I think I could let the 3 points define a plane. Then the plane would intersect the axis at a unique point. If I want 4 or more shares, I can make them by just generating more points on that same plane. Then I think any three of those should recover the secret. So it seems like that would all work about the same as with the polynomials? Then I can go to still more dimensions when I want to require more shares to reveal the secret.
- HWR_14 4mo ago
  Probably, but the nice thing about polynomials is the secret is the value when x is 0. What is the point on the hyper geometry where I look up the secret?
c0l0 4mo ago
We use this technique in our team to distribute passphrases for our secondary secret stores (that contain instructions on how to access our primary secret stores) in a "democratically secure and safe" manner. https://packages.debian.org/trixie/ssss https://packages.debian.org/trixie/ssss is a nice and rather straightforward implementation.
946789987649 4mo ago
My masters thesis was on this! I created an app where you can store your data across all the common data storage providers (dropbox, google drive, onedrive, etc.) and used the secret sharing to aid with the encryption. The benefit was that: - They could no longer read your data - Additional redundancy (as you only need 2 to be available) - Compared to other secure storage apps which rely on a master password, which if you forget, you are screwed, you could still use all the usual account recovery methods.
- luxcem 4mo ago
  It seems like a cool idea, did you follow up with a product or an open source app?
  - 946789987649 4mo ago
    Unfortunately no, as most uni students my code was utterly terrible and the app itself was more of a PoC. This was 10 years ago though and it's been on my mind since then, so i'll surely pick it up some point, perhaps after my current start up.
- trelane 4mo ago
  Where is your thesis available?
  - 946789987649 4mo ago
    I'm afraid it's not available as it wasn't published. To be honest there wasn't much more than what I posted there, it was quite a practical thesis and really more of a market analysis and practical implementation of a potential consumer product. Currently doing a different startup, but certainly an idea for a future one.
    - trelane 4mo ago
      Ah, dang. Thanks for responding anyway!
- 4mo ago
DesiLurker 4mo ago
SSS works pretty well. IIRC somebody in bitcoin community started using this for storing private keys using 3/5 schema. they basically divide the secret keys into 5 parts out of which you only need 3 to recover original private key. IDK if there are any hardware wallets that actually support it yet though.
- jan_k_ 4mo ago
  Trezor supports it.
saidnooneever 4mo ago
this is very nice explanation which needs no maths. really cool. I read about this a few times in articles without images etc and its hard to digest if you dont have a good background but this was wonderfully easy to understand. Thanks a lot.
Hypomixolydian 4mo ago
Shamir saved my bottom once, by helping me reconstruct random password used for almost forgotten backup, suddenly needed to be restored at once. Thank God I distributed shares in my family, "just in case".
cryptocod3 4mo ago
SSS is amazing, though managing shares over a long period (people come and go) and dealing with collusion risk can be rough.
- sowbug 4mo ago
  You can never be sure that duplicated information is destroyed, but if you combine SSS with a dead-man's switch protecting an asymmetric private key, you can periodically invalidate a set of shares. As a bonus, when you refresh the shares, you'll discover that at least a couple of your trusted parties have absolutely no memory of receiving that mysterious piece of paper from you back in 2022.
phkahler 4mo ago
This part: "The useful part is not that the secret is hard to compute from too few shares. It is that too few shares contain no information about the secret. With one share missing, every possible secret is still possible." Reminds me of factoring numbers with the Quadratic Sieve or its variants. You find a system of congruences mod n that eventually allow you to compute prime factors, but until you have enough of them that isn't possible. I've often wondered... Each congruence must contain some information right? What space are we reducing degrees of freedom in? Same thing here, each piece restricts the space of polynomials, but does not restrict it enough to tell where the key crosses the axis.
lormayna 4mo ago
My master thesis was about an application of SSS to mesh networks: even if one of the node of the mesh was captured by an attacker and the secret retrieved from the node, it was impossible to crack the whole encryption.
arcbyte 4mo ago
I'm curious if there's a way to merge multiple key/value pairs into a single cryptext (without just appending or exploding the size of the result) such that everyone securing their information into this scheme stores a copy of the same encrypted blob, but their key decrypts a different value from the blob. In this way, people could act as backups for one another with plausible deniability of what's being stored.
AIFSOfficial 4mo ago
[flagged]
danborn26 4mo ago
Nice breakdown. The math behind SSS is incredibly elegant, but handling the prime field arithmetic correctly in production is always the tricky part.
kristianc 4mo ago
Reminds me of this classic war story: https://medium.com/@amanat361/shamir-secret-sharing-the-story-of-a-catastrophic-bug-and-the-resilience-of-paypal-2d6104778b77 https://medium.com/@amanat361/shamir-secret-sharing-the-stor...
- Piraty 4mo ago
  which is in fact by Max Levchin: https://max.levch.in/post/724289457144070144/shamir-secret-sharing-its-3am-paul-the-head-of https://max.levch.in/post/724289457144070144/shamir-secret-s...
  - kristianc 4mo ago
    That's the one, I couldn't find the original
dimiprasakis 4mo ago
To be honest, I always wondered why variations of SSS haven't been seen commercial adoption more. For example, instead of storing API Keys in GitHub repos, the keys could be constructed on the fly by approvers signing their shares. I guess the UX of coordinating share-holders is what kills most implementations... SSS does suffer though for some serious weaknesses, i.e. it trusts the shareholders. A cheating party can submit a fake share during reconstruction, corrupting the recovered secret, and honest parties have no way to detect this something that verifiable secret sharing fixes. Anyway threshold crypto is a very elegant field and the math is there is really beautiful.

397 points by subract 4mo ago

han1 4mo ago

[flagged]

before I learned of shamir secret sharing, I wondered why one couldn't do the same exact thing with a par2 like system (albiet with smaller pieces than a par2 system would traditionally have). i.e. you have X bits of data, you create Y*X/N sized recovery blocks (where Y > N). You hand each recovery block to individual users. and any N users can get together to recover the key and decrypt the contents.

deleted 4mo ago
[deleted]
namibj 4mo ago
Well in theory the base math is indeed the same; unfortunately though the "randomly chosen" part of shamir's secret sharing is fairly important to the security because information theoretic security of the scheme requires each fragment to be as large as the original secret by way of essentially including a desired count of random data blocks to the original before applying the reed-solomon-like erasure coding to it where now enough fragments to reconstruct the secret plus all random blocks have to be combined. Also the way of usage of the erasure code has to be selected to not be leaking information but that's more of an issue of not picking a bad way of how to implement the basic concept here. Basically just a case of "do follow the instructions to shamir's secret sharing, don't do something different just because it's a popular way of implementing reed-Solomon". Yes, you can just GF(256), but if you're worried I'd also just use a prime field instead.

teravor 4mo ago

if the secret is large usually it's encrypted and the payload is distributed along with the shares of the key. but you can also just use Reed-Solomon and split the payload, the difference with Shamir is that you lose information-theoretic security (you lose it the moment you use encryption anyway) and the payload also needs to undergo an all-or-nothing-transform (AONT). AONT transforms the entire payload into an encrypted blob which also serves as its own key, a withheld piece is a de facto encryption key. this is required because Reed-Solomon can have pathological cases where pieces leak information.

colmmacc 4mo ago
Reed-Solomon is an Erasure code, and I definitely wouldn't look to that for Secret Splitting. Those leakage models are gnarly. But if you want something else that is more general - there are Monotone Span Programs. Seriously underused.
- teravor 4mo ago
  > Reed-Solomon is an Erasure code which shares the same math as Shamir > Those leakage models are gnarly. AONT solves that by making any leak other than the totality meaningless

Cider9986 4mo ago

Here is Ente's implementation: (https://2of3.ente.com/ https://2of3.ente.com/)

emmelaich 4mo ago
There's an implementation packaged up for most Linux distros: http://point-at-infinity.org/ssss http://point-at-infinity.org/ssss
ahazred8ta 4mo ago
There are several browser-based versions which can be used online or downloaded to use offline. https://bs.parity.io/ https://bs.parity.io/ -- http://passguardian.com/ http://passguardian.com/ -- https://iancoleman.io/shamir/ https://iancoleman.io/shamir/
- davidcollantes 4mo ago
  I have noticed that not one of them is compatible with the other. I generated shares using `ssss` (https://manpages.ubuntu.com/manpages/trusty/man1/ssss-split.1.html https://manpages.ubuntu.com/manpages/trusty/man1/ssss-split....), and couldn't combine them on any of the three sites linked. That is a downside, isn't it? Do you know of a way to bypass that hurdle, other than packing resources together with the shares?
  - ahazred8ta 4mo ago
    SSSS is not the official canonical file format for SSS. Shamir did not specify an official file format when he described his technique. Each implementation knows how to recombine its own shares. The web apps can be saved and used on any device.
Ajedi32 4mo ago
This is my favorite one yet, very user friendly. I only wish it was a bit more configurable. Ideally I'd be able to set up something like: 3 of 4: A B C D - OR - 2 of 3: E F G - AND - 1 of 1: H Or any similar combination. Maybe also with a way to name the cards so it's clear exactly what's needed when restoring. Though there's something to be said for the simplicity of the current design.

_jackdk_ 4mo ago

This is such a cool technique, and you could even teach it in secondary schools as a neat thing computer scientists can do with polynomials.

naths88 4mo ago
I am a secondary math teacher and I do exactly this with my students. When working on retrieving the expression of an affine function, I tell them about Shamir'..., they choose a secret pin as the slope, generate two points, give them to two other students who have to pair together to find the pin again. The students are always very engaged.
- _jackdk_ 4mo ago
  I'm so glad it works. If you handwave at the generalisation to quadratics and higher polynomials, do the students follow it well? I assume you don't get into the finite field stuff, but it seems like it'd be cool to handwave at "there's actually other structures where most of this polynomial stuff works, even in somewhat weird ways".
sowbug 4mo ago
It's the same idea as how GPS works. Fun to see someone's eyes light up when they get why that third satellite is needed to fix a 2D position. (Actual GPS is a little more complicated than that because the real system needs accurate time information.)

calvinmorrison 4mo ago

something tangentially i am interested in is computing following the 'two person rule' for things like sudo. Yes I am logged into server X at terinal Y, and so is my co-worker and we both sign off on running command X

jerry1979 4mo ago
That sounds like you might want to look into digital signatures.
coryrc 4mo ago
Had something like this at Google. There's a service running as root (or equivalent) which receives your desired command to run, and it has to get authorization from another user for the specific command to run, then runs it. That makes sense at Google, because those are production machines and have access to LDAP and who is allowed to run a command on a machine is defined by an LDAP group and you would need two of them (or more?) and there's already existing management website this can be shoe-horned into. Your environment is unlikely to have all of that already, so you'll need to figure out equivalents for all those. But I think you're going to need a local service running as root and it's going to need to be able to tell the difference between distinct human users, if you want secure. Just typos is way easier.
ahazred8ta 4mo ago
There's a related 2-man sudo login system here, not sure how finegrained it is. https://github.com/Argonne-National-Laboratory/Pam-2man-Auth https://github.com/Argonne-National-Laboratory/Pam-2man-Auth
timv 4mo ago
I wrote something like that about 15 years ago for a financial institution. For what we needed, we intentionally wanted both people to be at the same terminal (it was going to be used to give shell access to a specific unix account that ran a critical system). That mean that we could implement it as a setuid (root) binary that required both users to authenticate. It had a config file that worked like sudoers, and defined a list of commands that could be called, how many people were needed to authenticate, and which unix groups they had to belong to.

3eb7988a1663 4mo ago

Do the people who hold the root DNS keys do anything like this? Or is that too much complexity when a safe in a secure room works as an effective backup?

davkan 4mo ago
They do something similar. Basically 5 people are needed in order to access the dns root keys plus some extra administrative/witness people. 3 Crypto Officers with smartcards to unlock the hsm, 2 other officials to unlock the vault that contains the hsm and the vault that contains safety deposit boxes with the smartcards. There are 7 crypto officers, of which any three will do. https://www.cloudflare.com/learning/dns/dnssec/root-signing-ceremony/ https://www.cloudflare.com/learning/dns/dnssec/root-signing-...
UltraSane 4mo ago
They go into extreme detail about DNSsec root key security https://blog.apnic.net/2021/10/12/dns-security-and-key-ceremonies/ https://blog.apnic.net/2021/10/12/dns-security-and-key-cerem...

cryptoz 4mo ago

See also a story about an implementation from Max Levchin: https://max.levch.in/post/724289457144070144/shamir-secret-sharing-its-3am-paul-the-head-of https://max.levch.in/post/724289457144070144/shamir-secret-s...

avicado0o 4mo ago
this story is wildd

sreekanth850 4mo ago

ente means mine in Malayalam language. it's said to be one of the toughest Indian language to learn. FYI.

alfirous 4mo ago
Interesting, in Indonesia Ente means you. Derived from Arabic word Anta. Fascinating how sometimes in different languages one word can have opposite meaning and the other times one word can have similar meaning.
- aabdelhafez 4mo ago
  Ente also means "duck" in German.
- thisislife2 4mo ago
  Maybe it's the pronunciation - ente means "mine" and ante means "yours" (in Malayalam) which is what perhaps you may be referring to? (Former South Indian kingdoms and South East Asia have historical cultural ties due to trade and conquest, and thus they share some common words, which I assume is, largely borrowed from Tamil and Malayalam).
  - sreekanth850 4mo ago
    Some people use ante to mean yours in the northern region, but it is not common in the southern region.
ignoramous 4mo ago
> it's said to be one of the toughest Indian language to learn. By who? My SO is now passably conversant in Malayalam after watching their cinema during the covid lockdowns (~1y to 2y).
- sreekanth850 4mo ago
  By other indians. And indian military use malayalam to communicate, so that enemies cannot intercept. There was a report that chinese started learning south indian languages. Most movies use neutral phonetics (written language) where as spoken language is tough to understand and have many regional vriations.

ghostfoxgod 4mo ago

It's an incredible technique, when I came across it, it just changed the way I thought of solving giving out keys without "truly" giving them out. This gave me confidence for eternalvault.app, a project of mine.

hamburglar 4mo ago
I’ve been noodling over this exact business idea for a couple years! Part of my value prop was to make ops scale down to as close to zero as possible by having the encrypted data and most of the front end for accessing it live in S3 objects (or some similar mega-cheap object store). Aside from that, all you need is the dead man’s switch mechanism. And the secret fragments would live on QR codes that bring you to the static SPA with one of the fragments already loaded up, prompting you to scan more to complete the decryption. Good work doing it. I guess now I don’t have to. :D You may have gained a customer from this HN thread.
- ghostfoxgod 4mo ago
  Indeed, that's precisely why I decided to ditch out of the subscription model and went into one time payment method, did the math and it made sense that I don't need a very heavy system apart from supporting the dead man switch trigger Wrote my thoughts about that here: https://eternalvault.app/blog/why-we-are-adding-lifetime-pricing/ https://eternalvault.app/blog/why-we-are-adding-lifetime-pri... And it feels good to know that there are people out thinking about this, makes me happy truly and if you want to try out the platform, welcome aboard, happy to walk through it if needed. :)
  - hamburglar 4mo ago
    That’s great, and exactly what I was thinking. In fact, you have to wrestle with the fact that if it’s too cheap, people won’t trust it. One thing I had been thinking about was that it’s important to be extremely open about the algorithms and infrastructure required, with a very transparent whitepaper on how it works (enthusiast level discussion of the technical details) and how you have designed the company to be extremely sustainable. I think your job is to convince people of two things: 1) this actually respects my privacy in a way I can verify myself (or lean on the technical expertise of other outside observers), 2) this company actually has a chance of surviving until I die. If I can see those two things are true, a $199 lifetime purchase is a no-brainer (and that probably covers a dozen lifetime members’ operational costs). :D

ndr_ 4mo ago

Bruce Schneier described this in his seminal book Applied Cryptography, and HashiCorp Vault used to have an implementation in Go. On the practical side, I always wondered how large - in bits - the shares should be. One answer I got on a news group was "1 bit more than the actual key length". Nowadays, I wonder how the quantum computing threat would inform 1) share size choice and 2) pro/con Secret Sharing in general. Does anyone know?

andreareina 4mo ago
Do you remember why 1 bit more?
- asksomeoneelse 4mo ago
  Just spitballing; I have seen prefixing integers of arbitrary length with a bit 1 as the most significant bit as a way to avoid loosing the leading 0s when serializing the integers if the size is important. Also, IIRC, it's possible to implement shamir using arbitrary length integers instead of a common finite field. Not sure why someone would recommend doing either in that context though.
- ndr_ 4mo ago
  It was phrased as "to distinguish all possible secrets": https://groups.google.com/g/sci.crypt/c/siuibXhcUGc/m/wTpAEObAtQkJ https://groups.google.com/g/sci.crypt/c/siuibXhcUGc/m/wTpAEO...
proxysna 4mo ago
I think hashicorp still have an implementation for vaults seal/unseal process. Unless something changed ofc
- bigfatkitten 4mo ago
  They still do indeed.
plopilop 4mo ago
You usually do secret sharing in a finite field because computers don't like real numbers. The size of your share is a point (x, y), x can be small (typically log n in case of n participants), y is a random point in the field. Since Shamir Secret Sharing is information-theoretically secure (if you do not know k points from the k-out-of-n secret then all secrets are equally plausible even when bruteforcing), the bitsize of your field can be whatever you want (but obviously bigger than the bitsize of your secret, you can't hide 100 bits in a finite field of 5 elements). Usually, you don't want an attacker to be able to bruteforce your secret (while the scheme is ITS, your secret typically isn't, e.g. the seed of your wallet), hence randomness can be added to your secret and the bitsize of the field is taken big enough to thwart these attacks. Depending on your attack model, an 80-bits or 128-bits field is more than secure enough, hence a share bitsize slightly above 80 or 128 bits. And regarding quantum computer, since the scheme is ITS no attacks can exist.

craintes 4mo ago

I also had written an article on the subject a while ago if you want to dig a bit deeper: https://petal.cafe/posts/shamir/ https://petal.cafe/posts/shamir/

freakynit 4mo ago

This is such a cool neat trick. Vibe-coded a little playground where you can generate secrets, see the polynomial, combine the secrets, and in general, play around: https://shamirs-secret-sharing.pagey.site https://shamirs-secret-sharing.pagey.site

l1am0 4mo ago

Years ago I build a little tool to run shamir secret sharing in the browser (can be used full offline, just download the page) https://simon-frey.com/s4/ https://simon-frey.com/s4/

xtracto 4mo ago
Ha! Years ago i downloaded your page and stored it in some usb disks along with my kdb keepass database and a share of my password. I gave that to some members of my family and instruct them to give them to my wife in case I die. Thanks a lot Sir.

Tepix 4mo ago

Instead of going from two lines to curves, parabolas etc, couldn't you also add another dimension instead?

nitnelave 4mo ago
Two points make a line in any number of dimensions.
- cynicalkane 4mo ago
  Think GP is suggesting an N-dimensional plane in K>N dimensions.
- Levitz 4mo ago
  Yes, but without a specific plane to intersect with, that still doesn't define a third point, if you want to check intersection with an axis, you'd need a third point in tridimensional space, for example.
nyeah 4mo ago
Yes? If I use 3 shares and require all three to recover, then I think I could let the 3 points define a plane. Then the plane would intersect the axis at a unique point. If I want 4 or more shares, I can make them by just generating more points on that same plane. Then I think any three of those should recover the secret. So it seems like that would all work about the same as with the polynomials? Then I can go to still more dimensions when I want to require more shares to reveal the secret.
HWR_14 4mo ago
Probably, but the nice thing about polynomials is the secret is the value when x is 0. What is the point on the hyper geometry where I look up the secret?

c0l0 4mo ago

We use this technique in our team to distribute passphrases for our secondary secret stores (that contain instructions on how to access our primary secret stores) in a "democratically secure and safe" manner. https://packages.debian.org/trixie/ssss https://packages.debian.org/trixie/ssss is a nice and rather straightforward implementation.

946789987649 4mo ago

My masters thesis was on this! I created an app where you can store your data across all the common data storage providers (dropbox, google drive, onedrive, etc.) and used the secret sharing to aid with the encryption. The benefit was that: - They could no longer read your data - Additional redundancy (as you only need 2 to be available) - Compared to other secure storage apps which rely on a master password, which if you forget, you are screwed, you could still use all the usual account recovery methods.

luxcem 4mo ago
It seems like a cool idea, did you follow up with a product or an open source app?
- 946789987649 4mo ago
  Unfortunately no, as most uni students my code was utterly terrible and the app itself was more of a PoC. This was 10 years ago though and it's been on my mind since then, so i'll surely pick it up some point, perhaps after my current start up.
trelane 4mo ago
Where is your thesis available?
- 946789987649 4mo ago
  I'm afraid it's not available as it wasn't published. To be honest there wasn't much more than what I posted there, it was quite a practical thesis and really more of a market analysis and practical implementation of a potential consumer product. Currently doing a different startup, but certainly an idea for a future one.
  - trelane 4mo ago
    Ah, dang. Thanks for responding anyway!
4mo ago

DesiLurker 4mo ago

SSS works pretty well. IIRC somebody in bitcoin community started using this for storing private keys using 3/5 schema. they basically divide the secret keys into 5 parts out of which you only need 3 to recover original private key. IDK if there are any hardware wallets that actually support it yet though.

jan_k_ 4mo ago
Trezor supports it.

saidnooneever 4mo ago

this is very nice explanation which needs no maths. really cool. I read about this a few times in articles without images etc and its hard to digest if you dont have a good background but this was wonderfully easy to understand. Thanks a lot.

Hypomixolydian 4mo ago

Shamir saved my bottom once, by helping me reconstruct random password used for almost forgotten backup, suddenly needed to be restored at once. Thank God I distributed shares in my family, "just in case".

cryptocod3 4mo ago

SSS is amazing, though managing shares over a long period (people come and go) and dealing with collusion risk can be rough.

sowbug 4mo ago
You can never be sure that duplicated information is destroyed, but if you combine SSS with a dead-man's switch protecting an asymmetric private key, you can periodically invalidate a set of shares. As a bonus, when you refresh the shares, you'll discover that at least a couple of your trusted parties have absolutely no memory of receiving that mysterious piece of paper from you back in 2022.

phkahler 4mo ago

This part: "The useful part is not that the secret is hard to compute from too few shares. It is that too few shares contain no information about the secret. With one share missing, every possible secret is still possible." Reminds me of factoring numbers with the Quadratic Sieve or its variants. You find a system of congruences mod n that eventually allow you to compute prime factors, but until you have enough of them that isn't possible. I've often wondered... Each congruence must contain some information right? What space are we reducing degrees of freedom in? Same thing here, each piece restricts the space of polynomials, but does not restrict it enough to tell where the key crosses the axis.

lormayna 4mo ago

My master thesis was about an application of SSS to mesh networks: even if one of the node of the mesh was captured by an attacker and the secret retrieved from the node, it was impossible to crack the whole encryption.

arcbyte 4mo ago

I'm curious if there's a way to merge multiple key/value pairs into a single cryptext (without just appending or exploding the size of the result) such that everyone securing their information into this scheme stores a copy of the same encrypted blob, but their key decrypts a different value from the blob. In this way, people could act as backups for one another with plausible deniability of what's being stored.

AIFSOfficial 4mo ago

[flagged]

danborn26 4mo ago

Nice breakdown. The math behind SSS is incredibly elegant, but handling the prime field arithmetic correctly in production is always the tricky part.

kristianc 4mo ago

Reminds me of this classic war story: https://medium.com/@amanat361/shamir-secret-sharing-the-story-of-a-catastrophic-bug-and-the-resilience-of-paypal-2d6104778b77 https://medium.com/@amanat361/shamir-secret-sharing-the-stor...

Piraty 4mo ago
which is in fact by Max Levchin: https://max.levch.in/post/724289457144070144/shamir-secret-sharing-its-3am-paul-the-head-of https://max.levch.in/post/724289457144070144/shamir-secret-s...
- kristianc 4mo ago
  That's the one, I couldn't find the original

dimiprasakis 4mo ago

To be honest, I always wondered why variations of SSS haven't been seen commercial adoption more. For example, instead of storing API Keys in GitHub repos, the keys could be constructed on the fly by approvers signing their shares. I guess the UX of coordinating share-holders is what kills most implementations... SSS does suffer though for some serious weaknesses, i.e. it trusts the shareholders. A cheating party can submit a fake share during reconstruction, corrupting the recovered secret, and honest parties have no way to detect this something that verifiable secret sharing fixes. Anyway threshold crypto is a very elegant field and the math is there is really beautiful.