- Description
- Notation
- Shamir's secret sharing scheme (SSS)
- Generating shares and reconstruction of the secret
- Working with the project
- Basic usage
- Using with Docker build
- Format of a share
- Design rationale
- References
In this project we implement a modified version of Shamir’s secret sharing scheme (SSS) in order to share a secret phrase, called mnemonics, in a secure way. In the following we give the notation that we use, then we give the definition of Shamir's secret sharing scheme and our modified scheme. We describe how we generate shares and reconstruct the secret. Then we give a basic usage information and the format of a share file. Finally, we give a few comments on design rationale.
| Symbol | Descripton |
|---|---|
| n | Number of shares |
| t | Threshold |
| s | Secret |
| D | Digest of the secret |
| nb | Number of bits, e.i. nb = log2 len(dictionary) |
| nw | Number of words in the mnemonic, e.i. nw = len(secret) |
| m | Size of q in bits, e.i. m = nb * nw |
| q | Order of the Galois field, e.i. q = 2m |
| F | Galois field, e.i. F = GF(q) |
| d | Number of bits taken from the hash of the secret, the first part of the digest D. |
| R | Number of bits of the randomness which is the remaining part of the digest D. |
Let F be a finite field with q elements. A (t, n)-threshold secret sharing scheme shares a non-zero secret s among n users such that any t or more shares can reconstruct the secret but t-1 or less cannot. Shamir's secret sharing scheme is an ideal and perfect (t, n)-thresholds scheme and can be defined in two phases as follows:
-
A dealer chooses a secret polynomial f(x) with degree t-1, such that its constant term is the secret to be shared s.
-
The dealer sends the tuple (xi, f(xi)) as the share to i-th user, where xi's are all non-zero and distinct for i = 1, … , n.
- If any t or more users jointly perform a Lagrange interpolation with their shares, they obtain the secret polynomial f(x), and f(0) yields the secret s.
In addition to the above definition, we also encode the digest of the secret as f(q-1) as stated in SLIP-0039: Shamir's Secret-Sharing for Mnemonic Codes. Let s be the secret to be shared and D be it's digest such that, D = HMAC-SHA256(R || s)[:d] || R, where R is the randomness with length m-d in bits, for m = log2 q and some integer d.
In other words the digest share D is composed of two parts; first d-bit part is the first d bits of the output of the hash function and the remaining part is a randomness with m-d bit length.
Our scheme takes a secret mnemonic as string, converts it to binary string and performs padding if needed. Then it is converted to integer. After generating the integer shares, all the shares are converted into string and parsed as distinct n mnemonics. Below we describe Lagrange polynomial interpolation, share generation and secret reconstruction.
Lagrange interpolation formula tells us that constructing a degree t-1 polynomial requires at least t points. Assume that we have t distinct points (x1,y1), (x2, y2), … , (xt, yt). Then we can construct the unique degree t-1 polynomial as follows:
where lj(x) is the Lagrange basis polynomial with respect to the j-th point, i.e.
INPUT: secret s, total number of shares n, threshold t, order of Galois field q, irreducible polynomial of GF(q)
- Encode s = f(0) and the digest D = f(q-1).
- Pick random t-2 more points, i.e. (x1, y1), (x2, y2), … , (xt-2, yt-2).
- Using the shares (0, s), (q-1, D), (x1, y1), (x2, y2), … , (xt-2, yt-2), perform Lagrange interpolation and construct the unique degree t-1 polynomial f(x).
- Generate n-t+2 more shares by evaluating f(x) at the points xt-1, … , xn.
- Output n shares (xi, yi) for i = 1, … , n.
INPUT: list of share id x, list of access shares y, order of Galois field q, irreducible polynomial of GF(q), digest length d.
- Apply Lagrange interpolation for the shares (xj , yj) for j = i1, … , it, and recover the secret polynomial f(x).
- Compute the secret s' = f(0)
- Compute the digest D' = f(-1)
- If HMAC-SHA256(D'[d:] || s')[:d] = D'[:d], then return s'. Otherwise abort.
-
Project uses Pipenv as a tool to manage packages and their versions properly.
-
Make sure you have pipenv installed on your local machine or install it using
python -m pip install pipenv- Install the required packages using
pipenv install- Run the project using (Read Basic usage for detailed Information)
pipenv run python main.py-
One can share his secret by running below command in the terminal.
Python main.py create_shares -n [number of shares] -t [threshold value] -s [path/secret.txt] -v [optional]
-
If the secret file is not defined then the secret is requested to be typed on the terminal.
-
The reconstruct.py takes json files automatically from the same location and outputs the secret s if the number of the shares is enough.
-
You can directly use this app using Docker cli without installing anything. Make sure you have docker cli available on your machine.
-
Create a
sharesdirectory wherever you want to store the files this app will generate. This is necessary for the app to function correctly.
mkdir shares
- Run this command to generate shares (Make sure to replace CURRENT_VERSION with appropriate version numbers)
docker run -v shares:/usr/src/app/shares nethermindeth/research-mnemonic:CURRENT_VERSION main.py create_shares -n 4 -t 4
- Run this to reconstruct words from data in shares directory.
docker run -v shares:/usr/src/app/shares nethermindeth/research-mnemonic:CURRENT_VERSION main.py reconstruct
-
Our shares are stored in json files which are created in the same location with create_shares.py. The shares include the following information:
{ "id": i, "share": [ "word_1", "word_2", "word_3", . . . "word_nw" ] } -
If -v flag is used with create_shares.py then the share (json) files include additional public reconstruction data, e.i. irreducible polynomial and the dictionary.
{ "id": i, "share": [ "word_1", "word_2", "word_3" . . . "word_nw" ], "total_shares": n, "threshold": t, "primitive_poly": <polynomial in string form>, "dictionary": <word list> }
- The digest is encoded as a point in our scheme. It is the evaluation of the polynomial f(x) at q-1, e.i. f(q-1). Using digest provides us an additional check before returning the reconstructed secret with probability 1/d.
- On the other hand it decreases the entropy from 2m to 2m-d (for further information please see security analysis).
- Number of words nw and the number of bits nb determine the size of our Galois field.
- We have the primitive polynomials of degree up to 660. Therefore, for a dictionary of size 2048, e.i. nb = 11, our scheme supports up to 60 word secrets.
- Although Shamir’s secret sharing scheme (SSS) is information theoretically secure, there is a known active adversary attack against it. Assume an adversary who interacts with t-1 shareholders and perform share reconstruction with a faulty share. If she can do this again with another t-1 shareholders (1 different shareholder suffices), she can construct the secret without knowing anything about the secret. In order to avoid such an attack we plan to take some security measures which force the active adversaries to behave passively. We are going to use a composition of authentication schemes and a ZK proofs for the reconstruction process.
- Another security issue for our modified scheme is the decreasing entropy because of the digest check that is used in the reconstruction phase. But ensuring m-d > 128 can defeat this low entropy weakness.
- Finally we have another issue for the security. Assume that an attacker has k shares such that t < k < n, and assume that e shares among k are faulty shares. In this case Lagrange interpolation does not work because of the faulty shares. But if e < t < k/3 then the Berlekamp-Welch algorithm works and the adversary can reconstruct the secret without knowing the true shares.