Number: SLIP-0039
Title: Shamir's Secret-Sharing for Mnemonic Codes
Type: Standard
Status: Draft
Authors: Pavol Rusnak <stick@satoshilabs.com>
Tomas Susanka <tomas.susanka@satoshilabs.com>
Ondrej Vejpustek <ondrej.vejpustek@satoshilabs.com>
Marek Palatinus <slush@satoshilabs.com>
Jochen Hoenicke <hoenicke@gmail.com>
Created: 2017-12-18
This SLIP describes a standard and interoperable implementation of Shamir's secret-sharing (SSS), which is a form of secret sharing, where a secret is divided into parts, giving each participant its own unique part, where some of the parts or all of them are needed in order to reconstruct the secret.
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 a valuable capability, there is a substantial risk of the backup holder absconding with the asset. Shamir's secret-sharing provides a better mechanism for replicating secrets without giving the capability to the backup holder.
However, SSS is not standardized today, making it possible for a future secret recovery to be put in jeopardy if the tools have changed. Therefore, we propose standardizing SSS so that SLIP-0039 compatible implementations will be interoperable.
Shamir's secret-sharing (SSS) is a cryptographic mechanism how to divide a secret into N unique parts, where M of them are required to reconstruct the secret. First, a polynomial of N-1 degree is constructed and each party is given a corresponding point - a non-zero integer input to the polynomial and the corresponding output.
In case sufficient M values are provided the points exactly define the polynomial. The polynomial's value of f(0) = S corresponds to the master secret. You may read more on SSS on Wikipedia.
The value to be encoded as the master secret must be a multiple of 8 bits. This is typically a wallet entropy, but may be another secret value which was uniformly chosen from its (key) space. The master secret is divided into N Shamir parts and M specifies how many of those parts do we need to reconstruct the master secret. We use GF(256) reduced by x^8 + x^4 + x^3 + x + 1 (the Rijndael polynomial) as the underlying field. We consider the master secret in a form which includes its own checksum:
| master secret | 16-bit master secret checksum |
|---|
From this value, every byte is mapped to the specified field in a little-endian fashion (i.e. the first bit maps to a_7, the last bit maps to a_0). For each such field element, N-share field elements are generated and mapped back to bytes. Each participating party receives the following data:
| 5-bit index | 5-bit M threshold | variable-bit SSS part | 16-bit checksum |
|---|
The index corresponds to the SSS part's x value (see the diagram above) and the SSS part is the corresponding y value.
Index and threshold are encoding using the following scheme (convert from bits to decimal and add 1):
| 5-bit value | index/threshold value |
|---|---|
| 00000 | 1 |
| 00001 | 2 |
| 00010 | 3 |
| ... | ... |
| 11101 | 30 |
| 11110 | 31 |
| 11111 | 32 |
The checksum field is a checksum of the whole share (i.e. index, threshold, SSS part).
This structure is then converted into a mnemonic passphrase by splitting it up by 10 bits which correspond as an index to the a word list containing exactly 1024 words (see below).
| master secret | SSS part | share length |
|---|---|---|
| 128 bits | 144 bits | 170 bits = 17 words |
| 256 bits | 272 bits | 298 bits = 30 words |
The selection of 5-bit sizes for index/threshold values and 10-bit for wordlist index has a nice property that the first word of the mnemonic encodes exactly these two values. And, vice versa, only these two values determine the first word.
For the checksums we use the leftmost 16 bits of a SHA-256 hash digest of the relevant payload.
When enough M secrets are provided the master secret is reconstructed. To allow an additional protection of the final seed using a passphrase we will use a key derivation function to compute the seed. If no passphrase is provided an empty string should be used as a passphrase.
Passphrase should contain only ASCII characters to achieve the best interoperability among various operating systems and wallet implementations.
We will use PBKDF2(PRF = HMAC-SHA256, Password = master_secret, Salt = "SLIP0039" + passphrase, iterations = 20000, dkLen = 256 bits) as the key derivation function.
We suggest to use the obtained seed as a master seed S for Hierarchical Deterministic Wallets described in BIP-0032.
Our scheme doesn't support versioning. This is intentional to avoid unclear claims such as SLIP-0039 compatibility without a clear understanding, which version of the scheme is actually meant.
No localization is supported. This standard deals with a set of English words only. Previous attempts with arbitrary wordlists caused lots of confusion among users and decreased interoperability across various implementations.
Wordlist mandated by this SLIP is available here. Several criteria were applied where creating the list:
- wordlist is alphabetically sorted
- wordlist contains only common English words
- no word is shorter than 4 letters and longer than 8 letters
- all words have unique 4-letter prefix
TBD