privy-io / shamir-secret-sharing

Simple, independently audited, zero-dependency TypeScript implementation of Shamir's Secret Sharing algorithm

shamir-secret-sharing

Simple, independently audited, zero-dependency TypeScript implementation of Shamir's Secret Sharing algorithm.

Uses GF(2^8). Works on Uint8Array objects. Implementation inspired by hashicorp/vault.

Both Node and browser environments are supported.

Made with ❤️ by Privy.

Security considerations

This library has been independently audited by Cure53 (audit report) and Zellic (audit report).

There are a couple of considerations for proper use of this library.

1. Resistance to side channel attacks: JavaScript is a garbage-collected, just-in-time compiled language and it is thus unrealistic to achieve true constant-time guarantees. Where possible, we aim to achieve algorithmic constant-time.
2. This library is not responsible for verifying the result of share reconstruction. Incorrect or corrupted shares will produce an incorrect value. Thus, it is the responsibility of users of this library to verify the integrity of the reconstructed secret.
3. Secrets should ideally be uniformly distributed at random. If this is not the case, it is recommended to first encrypt the value and split the encryption key.

Usage

We can split a secret into shares and later combine the shares to reconstruct the secret.

import {split, combine} from 'shamir-secret-sharing';

const toUint8Array = (data: string) => new TextEncoder().encode(data);

// Example of splitting user input
const input = document.querySelector("input#secret").value.normalize('NFKC');
const secret = toUint8Array(input);
const [share1, share2, share3] = await split(secret, 3, 2);
const reconstructed = await combine([share1, share3]);
console.log(btoa(reconstructed) === btoa(secret)); // true

// Example of splitting random entropy
const randomEntropy = crypto.getRandomValues(new Uint8Array(16));
const [share1, share2, share3] = await split(randomEntropy, 3, 2);
const reconstructed = await combine([share2, share3]);
console.log(btoa(reconstructed) === btoa(randomEntropy)); // true

// Example of splitting symmetric key
const key = await crypto.subtle.generateKey(
  {
    name: "AES-GCM",
    length: 256
  },
  true,
  ["encrypt", "decrypt"]
);
const exportedKeyBuffer = await crypto.subtle.exportKey('raw', key);
const exportedKey = new Uint8Array(exportedKeyBuffer);
const [share1, share2, share3] = await split(exportedKey, 3, 2);
const reconstructed = await combine([share2, share1]);
console.log(btoa(reconstructed) === btoa(exportedKey)); // true

API

This package exposes two functions: split and combine.

split

/**
 * Splits a `secret` into `shares` number of shares, requiring `threshold` of them to reconstruct `secret`.
 *
 * @param secret The secret value to split into shares.
 * @param shares The total number of shares to split `secret` into. Must be at least 2 and at most 255.
 * @param threshold The minimum number of shares required to reconstruct `secret`. Must be at least 2 and at most 255.
 * @returns A list of `shares` shares.
 */
declare function split(secret: Uint8Array, shares: number, threshold: number): Promise<Uint8Array[]>;

combine

/**
 * Combines `shares` to reconstruct the secret.
 *
 * @param shares A list of shares to reconstruct the secret from. Must be at least 2 and at most 255.
 * @returns The reconstructed secret.
 */
declare function combine(shares: Uint8Array[]): Promise<Uint8Array>;

License

Apache-2.0. See the license file.

shamir-secret-sharing's Issues

Introducing a keystore-like format

What

I'm suggesting the introduction of a keystore-like format that can be used to provide meaningful metadata to the share generated, instead of the plain Buffer-like representation. In the same way that a traditional crypto private key benefits from being stored into a keystore, a secret share would benefit of metadata describing the data that it's trying to protect without disclosing the actual data.

Why

Although one can argue that the lack of metadata for the secret to encrypt is a feature and not a bug, the storage, operation and usage of blobs of shares can become cumbersome after some time. In short, 080198161f3f4aa4cc91d5a16d7cdf47db3cb3b1b8640457fa3892701a65b665307c gives you little to no information which can later be used for rotation or maintenance.

From an operational point of view, looking to these sort of strings in isolation will always required an additional piece of information (e.g. a relational table) to be able to piece together the purpose of the secret the share protects. Losing the relational data can be tricky, specially in the context of digital assets, where compliance to AML/KYC laws might require the removal of shares used as backups for restricted individuals.

In other words, if a crypto address is blacklisted by OFAC (or other similar organisations), and a share related to the respective private key controlling this address, it could be argued that the retainer of these backups could be sanctioned by simply storing this share. By adding metadata, we can guarantee plausible deniability and implement checks in place to trigger automatic systems whenever accounts are flagged.

How

I suggest the following schema to be used for the generation of the shares, which could be then integrated during the generation of the shares as an additional parameter. The result would be a JSON-like string, that would have the adequate information.

{
  "$schema": "http://json-schema.org/draft-07/schema#",
  "title": "Sharestore",
  "type": "object",
  "properties": {
    "total": {
      "type": "number",
      "description": "The total number of shares."
    },
    "threshold": {
      "type": "number",
      "description": "The minimum number of shares required to reconstruct the secret."
    },
    "instance": {
      "type": "number",
      "description": "The instance number associated with this share store."
    },
    "encrypted": {
      "type": "boolean",
      "description": "A flag indicating whether the shares are encrypted."
    },
    "share_sha512": {
      "type": "string",
      "description": "The SHA-512 hash of the share data."
    },
    "secret_sha512": {
      "type": "string",
      "description": "The SHA-512 hash of the original secret."
    }
  },
  "required": ["total", "threshold", "instance", "encrypted", "share_sha512", "secret_sha512"]
}

Given the current interface, we could see the following updated requirements:

const [share1, share2, share3] = await split(Buffer.from("secret key"), 3, 2, "sharestore");
console.log(share1)
> {
  total: 3,
  threshold: 2,
  instance: 0,
  encrypted: false,
  share_sha512: "60a74011c9c137da5313e9d1841b55e15e92dceb7ae290ea956718c07506278e4c074e9deed541306d013930dcf8dc721d5483ee65df626e5bbf95759ad91494",
  secret_sha512: "5010c61629c8f7ba65fad18ecb2db472d093d7c820503ac2c238eced7dfcd9414a0f31868f672e85f2032421d7cb3ad7cf8ea604659f39f64dc77981df1ac75a"
}

(where share_sha512 is the SHA-512 value of the hexadecimal representation of the share as a Buffer, and secret_sha512 is the SHA-512 value of the string-like value of the original secret. These could be adapted to also be the hexadecimal representation, but in the example, secret_sha512 is the SHA-512 value of the string "secret key")

For encryption, we could pass an array of strings to bcrypt or pbkdf2 for encryption, or a CryptoKey with encrypt capabilities (e.g. AES-GCM), as follows:

const [encryptedShare1, share2, share3] = await split(Buffer.from("secret key"), 3, 2, "sharestore", ["password", null, null]);

which would flag the content of encrypted to true, but not of share_sha512.

Additional notes

I'm sure within Privy there's some internal processes to decorate the user's shares with enough information, as well as to Key-Encrypt-Key (KEK) the backup share to avoid falling into custodianship of the related digital assets. However, I'm looking to define a standard for storing Shamir Secret share's, to handle the use cases described in the "Why" section. These topics are real concerns in the institutional digital asset ecosystem and a standard like this would heavily benefit the industry. Sadly, I was unable to pin point the origin of the Keystore format, and thus, thought as the current most up-to-date and open-source implementation, this would be the right place.

It's important to mention the current metadata does not solve the issue related to OFAC-sanctioned addresses, as no meaningful information is still included related to crypto. First, I would like to keep these generic, and in a separate step, include an additional flag targeting crypto, perhaps an attribute like account_sha512 which could then be used to verify on sanctioned lists.

As a final note, I'm also looking to have these sort of format to be consumable via physical format, as described in the following diagram:

(I've isolated the checksum data of the shares in case these would want to be stripped for security reasons within any organisation. However, ideally, the QR code would have everything needed, and a tool would suffice to scan and restore them if gathered all in a single place)

Please kindly discuss. If there's enough interest to implement this, I would happily help with the creation of the PR to implement the feature.

Incorrect coefficient restriction

The implementation currently restricts the leading coefficient of a secret polynomial to be nonzero. The stated goal of this appears to be avoiding a reduction in the number of shares required to reconstruct the secret. Unfortunately, this reasoning both breaks the security guarantee of the design and does not achieve the goal in a meaningful way.

As analyzed by Ghodosi et al. (specifically section 3.1), restricting the leading coefficient in this way allows a subthreshold of colluding players to definitively identify a value that the secret cannot be, which breaks the security guarantee otherwise provided by the Shamir design.

The reason that this restriction does not meaningfully achieve its goal of protecting against a reduced-threshold condition is subtle. Suppose the intended threshold is t players. With no coefficient restriction, it is certainly the case that the leading coefficient will be zero with 1/256 probability. If a threshold of t - 1 players collude and interpolate a value, they must verify that it is the correct secret; remember, they do not know in advance if the zero-coefficient case is at play. However, if the players were able to verify that the secret is correct, each player alone (without colluding) could simply try all 256 possible secrets! Therefore there is no advantage to a subthreshold of players that cannot be realized with equal expected value by non-colluding brute force.

Having issues with importing the package in my TS file

Here's how I'm importing the package in my smart-wallet.ts file

import * as shamir from "shamir-secret-sharing";

Error

TS2307: Cannot find module 'shamir-secret-sharing' or its corresponding type declarations.

Here are the complete logs:

ERROR in /Users/shiven/Documents/code/smart-wallet-client/src/smart-wallet.ts
./src/smart-wallet.ts 2:24-47
[tsl] ERROR in /Users/shiven/Documents/code/smart-wallet-client/src/smart-wallet.ts(2,25)
      TS2307: Cannot find module 'shamir-secret-sharing' or its corresponding type declarations.
ts-loader-default_e3b0c44298fc1c14

webpack 5.89.0 compiled with 2 errors in 1527 ms

What's causing this and how can this be resolved? Let me know if you need any additional info. Thanks!

The secrets don't seem to match the reconstructed string from the `combine()` function

I have a function that uses shamir-secret-sharing to create 3 shares of a privateKey, but when I combine the shares to reconstruct the secret, it doesn't seem to match. Here's my function:

import * as shamir from 'shamir-secret-sharing';
...
async function splitPrivateKeyIntoShards() {
    const privateKey: any = toUint8Array(walletPrivateKey);
    const [share1, share2, share3] = await shamir.split(privateKey, 3, 2);

    console.log("Share 1:", share1);
    console.log("Share 2:", share2);
    console.log("Share 3:", share3);

    const reconstructed: any = await shamir.combine([share1, share3]);
    console.log("Do the shares reconstruct the privateKey back:", btoa(reconstructed) === btoa(privateKey)); // true
}

Here are the console logs:

Share 1: Uint8Array(67) [94, 163, 107, 84, 129, 236, 112, 68, 219, 237, 90, 227, 128, 175, 0, 239, 193, 138, 103, 132, 103, 170, 79, 224, 48, 35, 195, 115, 225, 115, 240, 154, 115, 222, 178, 24, 49, 31, 167, 57, 47, 84, 188, 20, 147, 1, 251, 38, 52, 36, 162, 24, 20, 193, 94, 206, 232, 89, 67, 80, 154, 77, 111, 251, 160, 181, 150, buffer: ArrayBuffer(67), byteLength: 67, byteOffset: 0, length: 67, Symbol(Symbol.toStringTag): 'Uint8Array']

Share 2: Uint8Array(67) [248, 190, 25, 63, 112, 226, 47, 72, 1, 100, 252, 11, 208, 198, 64, 242, 195, 239, 6, 158, 159, 177, 142, 105, 200, 90, 223, 94, 4, 236, 84, 1, 102, 187, 98, 83, 144, 205, 98, 173, 28, 94, 211, 121, 238, 51, 185, 32, 249, 144, 116, 202, 146, 221, 89, 204, 205, 77, 169, 137, 210, 180, 40, 198, 47, 165, 50, buffer: ArrayBuffer(67), byteLength: 67, byteOffset: 0, length: 67, Symbol(Symbol.toStringTag): 'Uint8Array']

Share 3: Uint8Array(67) [227, 49, 254, 225, 93, 120, 110, 137, 103, 130, 231, 31, 171, 67, 213, 125, 152, 171, 244, 92, 101, 211, 138, 143, 50, 49, 240, 248, 113, 9, 20, 82, 158, 255, 40, 74, 198, 220, 208, 196, 206, 114, 187, 74, 51, 65, 119, 205, 60, 62, 211, 219, 78, 242, 20, 151, 28, 21, 230, 20, 48, 238, 240, 142, 36, 75, 114, buffer: ArrayBuffer(67), byteLength: 67, byteOffset: 0, length: 67, Symbol(Symbol.toStringTag): 'Uint8Array']

Do the shares reconstruct the privateKey back: false // should be true