Imagine something like TrueCrypt where user A can decrypt his files, or any 3 of the 10 directors in his organization can decrypt user A's files. As I understand it this is similar to the way the DNSSEC Root Keys are secured. Obligatory wiki entries. Does anyone know of any commercial or open source implementation of file encryption utilizing secret-sharing?
I want to say that the commercial PGP product has had this feature for at least 10 years. It currently has this feature now:
There are at least two free implementations that are part of Ubuntu linux and implement Shamir's secret splitting and combining:
gfshare: Ubuntu Manpage: gfshare - explanation of Shamir Secret Sharing in gf(2**8) provides both tools for secret sharing (gfsplit and gfcombine) which can split an arbitrary file into shares, as well as a library for use by developers.
The "ssss" package provides the ssss-split program which prompts you for a pass phrase which can't be longer than 128 characters, to split up into a set of phrases to share. Then the ssss-combine program prompts for enough of the shared phrases and prints out the secret.
gfshare directly works with files, while ssss would be used to split up a pass phrase which can then be used with gpg or openssl or another encryption utility. So gfshare would seem simpler for your use case.
Here's a Shamir's Secret Sharing library I put together in Python: https://github.com/rxl/secret-sharing.
It's really simple to split secrets:
>>> from secretsharing import SecretSharer >>> shares = SecretSharer.split_secret("c4bbcb1fbec99d65bf59d85c8cb62ee2db963f0fe106f483d9afa73bd4e39a8a", 2, 3) ['1-58cbd30524507e7a198bdfeb69c8d87fd7d2c10e8d5408851404f7d258cbcea7', '2-ecdbdaea89d75f8e73bde77a46db821cd40f430d39a11c864e5a4868dcb403ed', '3-80ebe2cfef5e40a2cdefef0923ee2bb9d04bc50be5ee308788af98ff609c380a']
...and recover secrets:
>>> SecretSharer.recover_secret(shares[0:3]) 'c4bbcb1fbec99d65bf59d85c8cb62ee2db963f0fe106f483d9afa73bd4e39a8a'
And it supports a whole bunch of secret and share formats, like Bitcoin private keys and base32:
>>> from secretsharing import BitcoinToZB32SecretSharer >>> shares = BitcoinToZB32SecretSharer.split_secret("5KJvsngHeMpm884wtkJNzQGaCErckhHJBGFsvd3VyK5qMZXj3hS", 2, 3) ['b-aweuzkm9jmfgd7x4k595bzcm3er3epf4dprfwzpprqa3exbuocs9byn4owfuqbo', 'n-btetgqqu8doacarsbyfdzpyycyj6gfdeaaxrpfx33pdjk4ou1d5owjdmdi1iegm9', 'd-njh33f14q7smucmh8iq8uaewc8mzub3mzptrwsegfiz3hc1fozkkjtguc4trh6sq']
The physical/IT crossover comes with Break Glass scenarios for emergencies - holders of part of the secret retrieve them from their safes and input a passphrase together in order to approve short-term emergency access permissions. This is pretty common in large organisations - especially in financial services.
I haven't seen a real world implementation of the purely technical solution that I think you mean - where the encryption algorithm copes with x out of y keys to unlock.
I wonder what the scenario would be that would require it as a solution over something simple like the break glass scenario I mentioned.
The key sharing is also used in Hardware Security Modules, for example to unlock the administrator account. In the Amazon CloudHSM documentation, the key sharing is explained pretty well: Amazon CloudHSM: About M of N
I work at a company that uses VSS extensively for our encryption product (atakama.com).
This paper sums up the technique pretty well: https://pdfs.semanticscholar.org/d229/92b176286979e53789a994a7547995d1e154.pdf
The keys for Atakama's cloud encryption system are split using "verifiable" secret shares.
Coefficient commitments rely on elliptic curve DLP for security, rather than prime field exponentiation.
The value of VSS (in general, not just in our use case), is that someone can add and remove security devices without exposing secrets - while being assured that the newly constructed shares are derived from the original secret.
This prevents an attacker from tricking a threshold scheme user from applying an invalid key. (Which, in turn, could be used to force leakage of information.)