BIP: XXXX
Layer: Applications
Title: Shamir secret sharing
Author: Bryan Bishop <kanzure@gmail.com>
Mark Friedenbach <mark@friedenbach.org>
Christopher Allen <ChristopherA@lifewithalacrity.com>
Chris Howe <chris@unchained-capital.com>
Yancy Ribbens <yancy.ribbens@gmail.com>
Hank Chiu
ChiaWei Tang
Laurence Chen
Status: Draft
Type: Standards Track
Created: 2019-09-04
Social key recovery allows users to collaborate with each other to securely recover their secrets instead of using centralized account reset procedures. Shamir secret sharing can be used as an implementation of social key recovery, where a secret can be split into a number of shares with various threshold requirements or in the future any arbitrary monotone boolean function describing a recovery policy.
SatoshiLabs' SLIP 39 is one proposed implementation of Shamir secret sharing with mnemonics. SLIP 39 implements simple Shamir secret sharing plus a two-level fixed threshold group, including a mnemonic text encoding scheme and an encryption scheme as well.
This proposal leverages SLIP 39 but allows for some forward-compatible extendibility and it is curve independent. In particular, this new proposal includes a binary format, additional metadata (such as birthdate), and greater flexibility of threshold specification. It also has some optional templates for pre-defined or pre-parameterized threshold requirements. The design is intended to make it possible to audit the independent parts of the proposal and make the proposal more modular. The proposal is intended to be able to support future upgrades like verifiable secret sharing and MuSig.
A reference implementation is included.
Secure storage of secret keys is critically important to bitcoin users. Traditionally, users make at least one backup of their master secret or recovery information. By distributing this backup to multiple other individuals, such as friends and family members, the user is able to increase redundancy and backup integrity at the risk of allowing a coalltion of trusted individuals to abscond with the funds. Instead, Shamir secret sharing provides a mechanism for a user to backup a secret split into shards and distribute those shards to a number of custodians in a manner that can prevent loss even if one or a few of those parties become compromised.
TODO: add text about why SLIP 39 is insufficient
SLIP 39 is optimized for the absolute minimum size because of the inherent limitations of writing down mnemonics. For example, for a 3-of-5 setup using SLIP 39, the SLIP 39 dealer would have to write down 100 words and 60 words to do recovery.
It is also desirable for a Shamir secret sharing proposal to be forwards compatible with future upgrades like verifiable secret sharing and MuSig.
Social key recovery: a user and his family, friends and colleagues collaborate to keep Shamir shards on behalf of the user.
Commercial custodian: a company has various teams of employees that are tasked with managing private keys and signing bitcoin transactions.
Use case: Key holder is a member of small company with 5 people, with Shamir key recovery policies in case of key holder's loss of key.
| policy | me | co-workers | family | friends |
|---|---|---|---|---|
| 1 of 1 | |||
| 4 of 5 | |||
| 3 of 5 | 2 of 3 | ||
| 3 of 5 | 1 of 3 | 2 of 3 | |
| 2 of 5 | 2 of 3 | 2 of 3 |
Legend:
#0 Held by key holder on secure device, or archival in holder's safe deposit or in escrow with lawyer.
#1 Unanimity of co-workers (key holder has lost their share)
#2 Supermajority of co-workers, plus two family members of key holder
#3 Supermajority of co-workers, plus one family members of key holder, and two friends of key holder
#5 Minority of co-workers, pluse two family members of key holder, and two friend of key holder.
Ideally an implementation of social key recovery should balance numerous competing goals:
- Key recovery should require approval of many individuals so as to minimize potential for theft or deliberate key compromise by a small malicious subset of users.
- Key recovery should require the smallest acceptable threshold so as to prevent loss of funds from destroyed/lost/inaccessible shares.
- Key recovery requiring interaction with too many individuals is undesirable, as each interaction must involve re-authentication at the inconvenience of all involved.
- Social trust is not uniformly distributed among different social circles, such as friends, business acquaintances, and family. Individuals may be fungible within a certain circle of trust, but not more broadly. A family member is not the same as a “business partner.”
TODO: rewrite
Shamir secret sharing (SSS) is a cryptographic mechanism describing how to split a secret into *N* unique parts, where any *T* of them are required to reconstruct the secret. First, a polynomial *f* of degree *T* − 1 is constructed and each party is given a corresponding point - an integer input *x* to the polynomial and the corresponding output *f*(*x*).
When any *T* points are provided, they exactly define the polynomial. Usually the value of the polynomial *f*(0) is used as the shared secret. In this specification the shared secret is stored as *f*(255). More details on SSS can be found on [Wikipedia](https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing).
Note that it is important to understand that the secret must be reassembled on a single machine or by a single user. Hence, the scheme always reduces to 1-of-n. Ideally this 1-of-n individual is the original user, which makes this scheme particularly useful for password recovery.
We propose using a simple version of miniscript with only ANDs, ORs, and a Shamir k-of-n threshold primitive parameterized by k and n. TODO: it would be nice if the threshold primative were composable in some way to build up slip39-like nested group structures.
Many use cases have multiple reconstruction policies which trade-off thresholds among the groups involved. With SLIP-39 compatible secret sharing this necessarily involves separate circles for each policy. Additionally, to retain additional metadata information (such as a birthday timestamp), there is a need to store variable-length data alongside each shard. We therefore define an envelope format to hold these shards and an encrypted blob containing the required metadata information.
To provide integrity and authentication, we derive two secret values from the seed entroy using HMAC-SHA256 keyed with "shamir" as the key derivation function. The first secret is interpreted as a secp256k1 private key. The second secret is used to key the encryption of a metadata blob, if present, using the AES-GMAC-CTR encryption with authentication mode.
The secp256k1 secret has an associated public key. This public key serves as the identifier for the entire Shamir secret share deck, and is prefixed to the beginning of the envelope encoding, followed by the encrypted metadata. Each shard is SLIP-39 format, along with a Schnorr signature of the metadata + shard using the secp256k1 key.
Public key 32 bytes (secp256k1-zkp Schnorr public key)
Encrypted metadata X bytes (variable-length string)
Authenticated Shards N structs:
Shard Data
SLIP-39 compatible binary
Signature
64 bytes (secp256k1-zkp Schnorr signature)
The dealer creates all the shards of a deck at the same time. Then for each recipient they construct an envelope which contains only the shard for that recipient, and encrypt the envelope to that user using the encrypted envelope format:
Public key 32 bytes (same as above)
(Same contents as the envelope, but without duplicating the prefixed public key.)
The encryption uses the symmetric secret derived using ECDH with the seed entropy and the recipient's public key. For decryption, the recipient can reconstruct the same secret using their private key and the public key which identifies the shard, and thereby decode the remaining contents of the envelope.
In reconstruction the collector no longer has access to the original seed entropy, so a secure channel must be used to transmit the unencrypted shards back for reconstruction.
One characteristic of Shamir’s secret sharing scheme is that all shards are equal. Thus if the owner of the secret needs to distribute the amount of trust unevenly between shard custodians, then some shard custodians need to be given multiple shards. Furthermore, as discussed by Allen and Friedenbach[1], the owner might want to restrict the combinations of custodians which are able to reconstruct the secret, because some combinations of custodians might be more likely to collude against the owner than others. To facilitate this we propose that the encrypted master secret (EMS) is first split using a GT-of-G scheme to obtain a set of first-level shards, aka circle. The i-th group shard, 1 ≤ i ≤ G, is then split using a Ti-of-Ni scheme to obtain a set of second-level shards, aka custodian shard, which are distributed among the shard custodians. Two levels are assumed to be sufficient to accommodate the majority of use cases while maintaining a comprehensive user interface.
For example, Alice wants to be able to reconstruct her EMS on her own using her 2 shards, which she has stored at different locations. In case these shards get destroyed, she also wants to have a backup with her friends and family in such a way that 3 of her 5 friends together with 2 of her 6 family members are required to reconstruct the EMS. A two level secret sharing scheme can easily accommodate such requirements. In the given example Alice first splits the EMS using a 2-of-4 scheme to obtain the circle A, B, C and D. She keeps A and B for herself and splits C further using a 3-of-5 scheme to obtain custodian shards C1, ... , C5, giving one to each friend. Similarly, Alice splits D among her family members using a 2-of-6 scheme. Thus family members receive a greater amount of trust than friends, without having to give one person multiple shards. However, even if all six family members collude against Alice, they cannot obtain the EMS without the help of at least two of Alice's friends or without stealing one of Alice's shards.
All shards created in accordance with this specification use the two level secret sharing scheme. If the creator of the shards wishes to use only a basic single-level T-of-N scheme, then they SHOULD [2] create a single circle and conduct the splitting at the second level, i.e. GT = 1, G = 1, T1 = T and N1 = N.
If the member threshold Ti of a circle is 1, then the size Ni of the circle SHOULD[3] also be equal to 1. The one shard can then be given to multiple custodians.
We propose the following format of the shards:
| Identifier (id) | Iteration exponent (e) | Circle index (GI) | Circle threshold (Gt) | Circle count (g) | Custodian index (I) | Custodian threshold (t) | Padded shard value (ps) | Checksum (C) |
|---|---|---|---|---|---|---|---|---|
| 15 bits | 5 bits | 4 bits | 4 bits | 4 bits | 4 bits | 4 bits | padding + 8n bits | 30 bits |
- The identifier (id) field is a random 15-bit value which is the same for all shards and is used to verify that the shards belong together; it is also used as salt in the encryption of the master secret.
- The iteration exponent (e) field indicates the total number of iterations to be used in PBKDF2. The number of iterations is calculated as 10000×2e.
- The circle index (GI) field[4] is the x value of the circle shard.
- The circle threshold (Gt) field[5] indicates how many circle shards are needed to reconstruct the master secret. The actual value is encoded as Gt = GT − 1, so a value of 0 indicates that a single circle shard is needed (GT = 1), a value of 1 indicates that two circle shards are needed (GT = 2) etc.
- The circle count (g) indicates the total number of circles. The actual value is encoded as g = G − 1.
- The member index (I) field[6] is the x value of the circle shard in the given group.
- The member threshold (t) field[7] indicates how many circle shards are needed to reconstruct the group shard. The actual value is encoded as t = T − 1.
- The padded shard value (ps) field corresponds to a list of the SSS part's fk(x) values (see the diagram above), 1 ≤ k ≤ n. Each fk(x) value is encoded as a string of eight bits in big-endian order. The concatenation of these bit strings is the shard value. This value is left-padded with "0" bits so that the length of the padded shared value in bits becomes the nearest multiple of 10.
- The checksum (C) field is an RS1024 checksum (see [below](#checksum)) of the data part of the shard (that is id || e || GI || Gt || g || I || t || ps). The customization string (cs) of RS1024 is "shamir".
TODO : insert from SSS groups here
TODO
TODO: insert text about multisig vs SSS, and multisig vs VSS.
Shard dealer: An individual that has a secret that is sharded using this secret sharing scheme. The user makes a number of shards that are dealt out to different users to turn each user into a shard custodian.
Deck: A collection of shards that together can be combined (in at least one way) to reconstruct the sharded secret.
Deck identifier: Derived from the sharded secret. It is the public key derived from the sharded secret unmodified with no derivation and no other modification. The deck identifier is a public key that uniquely identifies the deck. This key can sign each shard.
Script policy: A script that specifies a policy for how the deck's secret (seed entropy) can be reconstructed from some combination of shards.
Quorum: Any set of shards sufficient to meet the script policy for reconstruction.
Shard: A shard includes unencrypted metadata, an unencrypted Y value and checksum, and private encrypted data.
Shard unencrypted metadata (public metadata): Data associated with a shard that describes the shard and the deck among other things. This includes birthdate, deck identifier information, and so on.
Shard value: The mathematical or cryptographic value that can be used in the secret sharing scheme to reconstruct the sharded secret. This is the y value.
Private data (encrypted) (encrypted blob or deck blob): Encrypted data transferred with each shard. The decryption key can be computed by recombining all the shards.
Shard custodian: A user that holds a number of shards, possibly from multiple different decks.
Shard pool: A shard custodian can use software that implements a shard pool that contains their collection of shards they are responsible for. The shard pool allows for querying over the set of shards to find particular shards to respond to a request.
Sharded secret: Used to create the derived secret. This is used both as symmetric key and as a private key. This is a high entropy secret.
Derived secret: The derived secret is used to decrypt the identical private data associated with each shard.
Archive shard: 1-of-1 with metadata that can be used for escrow as an alternative to just storing recovery words. This is binary-encoded data.
https://github.com/satoshilabs/slips/blob/master/slip-0039.md
Shamir, Adi (1979). “How to share a secret”. Communications of the ACM. 22 (11): 612–613. doi:10.1145/359168.359176. https://cs.jhu.edu/~sdoshi/crypto/papers/shamirturing.pdf
Beimel A. (2011) Secret-Sharing Schemes: A Survey. In: Chee Y.M. et al. (eds) Coding and Cryptology. IWCC 2011. Lecture Notes in Computer Science, vol 6639. Springer, Berlin, Heidelberg https://www.cs.bgu.ac.il/~beimel/Papers/Survey.pdf
Rait, Seth (2016). “Shamir Secret Sharing and Threshold Cryptography” https://sethrait.com/Shamir-Secret-Sharing-and-Threshold-Cryptography
Dautrich J.L., Ravishankar C.V. (2012) “Security Limitations of Using Secret Sharing for Data Outsourcing. In: Cuppens-Boulahia” N., Cuppens F., Garcia-Alfaro J. (eds) Data and Applications Security and Privacy XXVI. DBSec 2012. Lecture Notes in Computer Science, vol 7371. Springer, Berlin, Heidelberg http://www.cs.ucr.edu/~ravi/Papers/DBConf/secret_sharing.pdf)
Komargodski I., Naor M., Yogev E. (2016) How to Share a Secret, Infinitely. In: Hirt M., Smith A. (eds) Theory of Cryptography. TCC 2016. Lecture Notes in Computer Science, vol 9986. Springer, Berlin, Heidelberg https://eprint.iacr.org/2016/194.pdf
Coron JS., Prouff E., Roche T. (2013) On the Use of Shamir’s Secret Sharing against Side-Channel Analysis. In: Mangard S. (eds) Smart Card Research and Advanced Applications. CARDIS 2012. Lecture Notes in Computer Science, vol 7771. Springer, Berlin, Heidelberg https://www.ssi.gouv.fr/uploads/IMG/pdf/aesshamir_Coron_Prouff_Roche.pdf
Blakley, G.R. (1979). “Safeguarding Cryptographic Keys”. Managing Requirements Knowledge, International Workshop on (AFIPS). 48: 313–317. doi:10.1109-/AFIPS.1979.98. https://pdfs.semanticscholar.org/32d2/1ccc21a807627fcb21ea829d1acdab23be12.pdf
Feldman, Paul (1987) “A practical scheme for non-interactive Verifiable Secret Sharing” Proceedings of the 28th Annual Symposium on Foundations of Computer Science https://www.cs.umd.edu/~gasarch/TOPICS/secretsharing/feldmanVSS.pdf
Harn, e, Changlu L (2009). “Detection and identification of cheaters in (t, n) secret sharing scheme” Des. Codes Cryptography 52, 1 (July 2009), 15-24. DOI=10.1007/s10623-008-9265-8 http://dx.doi.org/10.1007/s10623-008-9265-8
Schoenmakers, Berry (1999) “A Simple Publicly Verifiable Secret Sharing Scheme and its Application to Electronic Voting” Advances in Cryptology-CRYPTO’99, volume 1666 of Lecture Notes in Computer Science, pages 148-164, Berlin, 1999. Springer-Verlag. https://www.win.tue.nl/~berry/papers/crypto99.pdf
Rusnak, P, et. al (2018) “SLIP-0039 : Shamir’s Secret-Sharing for Mnemonic Codes” Satoshi Labs Github. https://github.com/satoshilabs/slips/blob/master/slip-0039.md
Stack Exchange (2016) “Why is Shamir Secret Sharing not secure against active adversaries out-of-the-box?” Stack Exchange https://crypto.stackexchange.com/questions/41994/why-is-shamir-secret-sharing-not-secure-against-active-adversaries-out-of-the-bo
Beimel, Amos (2011). "Secret-Sharing Schemes: A Survey" http://www.cs.bgu.ac.il/~beimel/Papers/Survey.pdf
Blakley, G.R. (1979). "Safeguarding Cryptographic Keys". Managing Requirements Knowledge, International Workshop on (AFIPS). 48: 313–317. doi:10.1109-/AFIPS.1979.98.
Feldman, Paul (1987) "A practical scheme for non-interactive Verifiable Secret Sharing" Proceedings of the 28th Annual Symposium on Foundations of Computer Science
Harn, L. & Lin, C. Detection and identification of cheaters in (t, n) secret sharing scheme, Des. Codes Cryptogr. (2009) 52: 15. https://link.springer.com/article/10.1007/s10623-008-9265-8
Schneier, Bruce (2010) - DNSSEC Root Key held by 7 parties worldwide https://www.schneier.com/blog/archives/2010/07/dnssec_root_key.html
Schoenmakers, Berry (1999) "A Simple Publicly Verifiable Secret Sharing Scheme and its Application to Electronic Voting" Advances in Cryptology-CRYPTO'99, volume 1666 of Lecture Notes in Computer Science, pages 148-164, Berlin, 1999. Springer-Verlag.
Zenroom, a virtual machine for fast cryptographic operations on elliptic curves, https://zenroom.dyne.org/
HTC EXODUS SKR, a smartphone device with build-in Shamir Secret Sharing into Trusted Execution Environment. Which support the web 3.0 to turn that around by empowering users to own their own data. The EXODUS 1 is the first native web 3.0 mobile device. This same architecture also secures your crypto assets. https://www.htcexodus.com/eu/zion/
https://tools.ietf.org/html/draft-mcgrew-tss-03
It would be good to keep the policy private from all of the shard custodians.