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.
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.
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
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.
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?
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.
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?
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?
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.
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.
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.
Done something similar for mine as well, although the word of the year that day was blockchain, so implemented the same onto Ethereum. It was a fun project, and Secret Sharing is quite an interesting topic!
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.
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.
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".
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.
"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.
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.
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.
40 comments
[ 3.3 ms ] story [ 49.8 ms ] threadbut 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.
(Actual GPS is a little more complicated than that because the real system needs accurate time information.)
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.
https://blog.apnic.net/2021/10/12/dns-security-and-key-cerem...
By who? My SO is now passably conversant in Malayalam after watching their cinema during the covid lockdowns (~1y to 2y).
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://simon-frey.com/s4/
https://packages.debian.org/trixie/ssss is a nice and rather straightforward implementation.
- 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.
Currently doing a different startup, but certainly an idea for a future one.
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.
"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.
In this way, people could act as backups for one another with plausible deniability of what's being stored.