Shamir's Secret-Sharing for Mnemonic Codes

Table of contents

• Abstract
• Notation
• Motivation
• Shamir's secret-sharing
• Two-level scheme
• Format of the share mnemonic
• Generating and combining the shares
  • Polynomial interpolation
  • Sharing a secret
  • Generating the shares
  • Combining the shares
• Checksum
• Passphrase
• Encryption of the master secret
• Decryption of the master secret
• Versioning
• Localization
• Wordlist
• Specification for backing up BIP-0032 Hierarchical Deterministic Wallets
• Test vectors
• Reference implementation
• Design rationale
• References

Abstract

This SLIP describes a standard and interoperable implementation of Shamir's secret-sharing (SSS) and a specification for its use in backing up Hierarchical Deterministic Wallets described in BIP-0032. SSS splits a master secret into unique parts which can be distributed among participants. A specified minimum number of parts is required to be supplied in order to reconstruct the original secret. Knowledge of fewer than the required number of parts does not leak information about the master secret. This SLIP is mainly intended as a replacement for BIP-0039 and for the most part, the two are not compatible.

Notation

Notation | Meaning ----------------|--------------------------------------------------------------- G | total number of groups, a positive integer, 1 ≤ G ≤ 16 N_i | total number of members in group i, a positive integer, 1 ≤ N_i ≤ 16 GT | group threshold, a positive integer, 1 ≤ GT ≤ G T_i | member threshold for group i, a positive integer, 1 ≤ T_i ≤ N_i id | random identifier, a 15-bit unsigned integer ext | extendable backup flag e | iteration exponent, a 4-bit unsigned integer MS | master secret, an octet string n | length of the master secret in bytes EMS | encrypted master secret, an octet string || | concatenation operator xor | bit-wise exclusive-or of two octet strings

Motivation

Preservation of digital assets is generally important and it is especially important in the case of decentralized payments systems such as Bitcoin, where there is no recourse in the case of loss of an asset. The usual approach to protecting digital assets is redundant backups, but when the asset itself is of significant and liquidable value, there is a substantial risk of the backup holder absconding with the asset. Shamir's secret-sharing provides a better mechanism for backing up secrets by distributing custodianship among a number of trusted parties in a manner that can prevent loss even if one or a few of those parties become compromised.

However, the lack of SSS standardization to date presents a risk of being unable to perform secret recovery in the future should the tooling change. Therefore, we propose standardizing SSS so that SLIP-0039 compatible implementations will be interoperable.

Shamir's secret-sharing

Shamir's 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.

We propose that given a secret, T − 2 shares be generated randomly and the remaining shares be computed in such a way that f(255) encodes the shared secret and f(254) encodes the digest⁴ of the shared secret. Encoding the digest makes it possible to verify that the shared secret has been correctly recovered. The diagram below illustrates the splitting of a secret into five shares such that any three are required to recover the shared secret (N = 5 and T = 3).

Shamir's secret sharing scheme is applied separately to each byte of the shared secret and GF(256) is used as the underlying finite field¹. Bytes are interpreted as elements of GF(256) using polynomial representation with operations modulo the Rijndael irreducible polynomial x⁸ + x⁴ + x³ + x + 1, see AES sections 3.2, 4.1 and 4.2.

Two-level scheme

One characteristic of Shamir’s secret sharing scheme is that all shares are equal. Thus if the owner of the secret needs to distribute the amount of trust unevenly between shareholders, then some shareholders need to be given multiple shares. Furthermore, as discussed by Allen and Friedenbach, the owner might want to restrict the combinations of shareholders which are able to reconstruct the secret, because some combinations of shareholders 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 shares, aka group shares. The i-th group share, 1 ≤ i ≤ G, is then split using a T_i-of-N_i scheme to obtain a set of second-level shares, aka member shares, which are distributed among the shareholders. 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 shares, which she has stored at different locations. In case these shares 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 group shares A, B, C and D. She keeps A and B for herself and splits C further using a 3-of-5 scheme to obtain member shares 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 shares. However, even if all six family members collude against Alice, they cannot obtain the EMS without the help of at least three of Alice's friends or without stealing one of Alice's own shares.

All shares created in accordance with this specification use the two-level secret sharing scheme. If the creator of the shares wishes to use only a basic single-level T-of-N scheme, then they SHOULD² create a single group and conduct the splitting at the second level, i.e. GT = 1, G = 1, T₁ = T and N₁ = N.

If the member threshold T_i of a group is 1, then the size N_i of the group SHOULD² also be equal to 1. The one share can then be given to multiple members.

Format of the share mnemonic

We propose the following format of the shares:

| Identifier (id) | Extendable (ext) | Iteration exponent (e) | Group index (GI) | Group threshold (Gt) | Group count (g) | Member index (I) | Member threshold (t) | Padded share value (ps) | Checksum (C) | |---------|-------|--------|--------|--------|--------|--------|--------|---------------------|---------| | 15 bits | 1 bit | 4 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 shares and is used to verify that the shares belong together.
• The extendable backup flag (ext) field¹⁰ indicates that the id is used as salt in the encryption of the master secret when ext = 0.
• The iteration exponent (e) field indicates the total number of iterations to be used in PBKDF2. The number of iterations is calculated as 10000×2^e.
• The group index (GI) field³ is the x value of the group share.
• The group threshold (Gt) field³ indicates how many group shares 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 group share is needed (GT = 1), a value of 1 indicates that two group shares are needed (GT = 2) etc.
• The group count (g) indicates the total number of groups. The actual value is encoded as g = G − 1.
• The member index (I) field³ is the x value of the member share in the given group.
• The member threshold (t) field³ indicates how many member shares are needed to reconstruct the group share. The actual value is encoded as t = T − 1.
• The padded share value (ps) field corresponds to a list of the SSS part's f_k(x) values (see the diagram above), 1 ≤ k ≤ n. Each f_k(x) value is encoded as a string of eight bits in big-endian order. The concatenation of these bit strings is the share value. This value is left-padded with "0" bits so that the length of the padded share value in bits becomes the nearest multiple of 10.
• The checksum (C) field is an RS1024 checksum (see below) of the data part of the share (that is id || ext || e || GI || Gt || g || I || t || ps). The customization string (cs) of RS1024 is "shamir" if ext = 0 and "shamir_extendable" if ext = 1.

This structure is then converted into a mnemonic code by splitting it up into 10-bit segments with each becoming an index into a word list containing exactly 1024 words (see below). Big-endian bit order is used in all conversions. The entropy⁴ of the master secret MUST be at least 128 bits and its length MUST be a multiple of 16 bits. All implementations MUST support master secrets of length 128 bits and 256 bits:

| Security | Padded share value length | Total share length | |----------|---------------------------|---------------------| | 128 bits | 130 bits | 200 bits = 20 words | | 256 bits | 260 bits | 330 bits = 33 words |

This construction yields a beneficial property where the random identifier and the iteration exponent transform into the first two words of the mnemonic code, so the user can immediately tell whether the correct shares are being combined, i.e. they have to have the same first two words. Moreover, the third word encodes the group index, group threshold and part of the group count. Since the group threshold and group count are constant, all shares belonging to the same group start with the same three words.

Generating and combining the shares

Polynomial interpolation

Given a set of m points (x_i, y_i), 1 ≤ i ≤ m, such that no two x_i values equal, there exists a polynomial that assumes the value y_i at each point x_i. The polynomial of the lowest degree that satisfies these conditions is uniquely determined and can be obtained using the Lagrange interpolation formula given below.

Since Shamir's secret sharing scheme is applied separately to each of the n bytes of the shared secret, we work with y_i as a vector of n values, where y_i[k] = f_k(x_i), 1 ≤ k ≤ n, and f_k is the polynomial in the k-th instance of the scheme.

Interpolate(x, {(x_i, y_i), 1 ≤ i ≤ m})

Input: the desired index x, a set of index/value-vector pairs {(x_i, y_i), 1 ≤ i ≤ m} ⊆ GF(256) × GF(256)ⁿ

Output: the value-vector (f₁(x), ... , f_n(x))

Sharing a secret

SplitSecret(T, N, S)

Input: threshold T, number of shares N, secret S

Output: shares y₁, ... , y_N for share indices 0, ... , N − 1

1. Check the following conditions:

   • 0 < T ≤ N ≤ 16
   • The length of S in bits is at least 128 and a multiple of 16.

   If any of these conditions is not satisfied, then abort.

2. If T is 1, then let y_i = S for all i, 1 ≤ i ≤ N, and return.

3. Let n be the length of S in bytes. Generate R ∈ GF(256)ⁿ⁻⁴ randomly with uniform distribution and let D be the concatenation of the first 4 bytes of HMAC-SHA256(key=R, msg=S) with the n − 4 bytes of R.

4. Let y₁, ... , y_T−2 ∈ GF(256)ⁿ be generated randomly, independently with uniform distribution.

5. For i such that T − 2 < i ≤ N compute y_i = Interpolation(i − 1, {(0, y₁), ... , (T − 3, y_T−2), (254, D), (255, S)}).

The source of randomness used to generate the values in steps 3 and 4 above MUST be suitable for generating cryptographic keys.

RecoverSecret(T, [(x₁, y₁), ... , (x_m, y_m)])

Input: threshold T, a list of m share-index/share-value pairs [(x₁, y₁), ... , (x_m, y_m)]

Output: the shared secret S

1. If T is 1, then let S = y₁ and return.
2. Compute S =

[Content truncated — view full spec at source]