Sharing the secret: a peek under the hood of Privy’s Shamir Secret Sharing library
S
|Aug 7, 2024
Introduction
A core part of our mission at Privy is to make it easier for developers to build apps that respect their users’ data and assets, and distributed systems and cryptography are at the heart of this. Accordingly, we have put a lot of thought into the best way to securely bring cryptographic keys to mainstream users in intuitive, simple ways. A lot of our work involves threat modeling and choosing architecture. We prefer to use the best open source software libraries when they’re available (and create our own when there isn’t already a best option).
To safely manage private keys for embedded wallets, we use a cryptographic primitive called Shamir’s Secret Sharing Scheme. This post explores what it is, why it matters, and some interesting practical considerations that we’ve considered over the years.
What is Shamir’s Secret Sharing?
Shamir’s Secret Sharing Scheme (SSS) is a technique for splitting a secret value into some number (n) of shares, where some threshold (t) must work together to recover the original secret. SSS offers information-theoretic security against attackers that do not possess t of the n shares.
Some of the problems that Shamir’s Secret Sharing Scheme can solve are also a good fit for considering Threshold Signature Schemes (i.e., FROST) or Trusted Execution Environments (TEEs). We chose Shamir’s over TSS and TEE solutions because it’s a 50 year old workhorse that is well-understood, well-documented, and performs beautifully at scale (more on this here).
How Shamir’s Secret Sharing works
Let’s say you have a secret key that you want to share between different parties.
The simplest way to do so is to give them each a copy of the secret key. But if you do this, there is a risk that one of them could mishandle it, which would undermine security.
What if, instead, you wanted to share your secret key without any of the share-holders being able to recover it without the cooperation of the others?
To understand how Shamir’s Secret Sharing Scheme works, first imagine you have a one-byte secret. The same process can be repeated for each byte of a longer secret.
Step 0: Determine number of shares
First, you will need to determine how many shares (n) to derive, and what threshold (t) should be needed to recover the secret. The DNSSEC key rotation ceremony uses t=7, n=14. We abbreviate this by saying it’s 7-of-14.
Step 1: Generate shares
For every byte of your secret, you’re going to do the following:
Generate t-1 random coefficients.
Construct a polynomial such that
the constant term S is the corresponding byte of your secret, and
each coefficient corresponds to a higher order.
Evaluate the polynomial at n different x coordinates to obtain n points (x, y).
The (x, y) values you obtain from plugging the x coordinates into the polynomials are your shares. It’s okay to reuse x values here for each byte of the same share, provided each polynomial is distinct, x is never equal to 0, and x is never reused across shares.
Step 2: Recover secret
To recover your secret, for each byte, you need to recover the polynomial from the shares. You need t of the n shares in order to recover a t-1 order polynomial. The most common technique for doing this is called Lagrange interpolation. The previous linked article from ZKDocs contains the formulas and some discussion around misuse resistance.
When the threshold is lower than expected
One of the findings of our first audit from Cure53 was that one of these polynomials might have a leading coefficient of 0. For a 256-bit secret, this is expected to happen for at least one byte of your secret in about 11% of cases.
When the leading coefficient is 0, the order of the polynomial is reduced by 1.
This means that, instead of t shares needed to recover that byte of your shared secret, you can recover it with only t-1 shares. For low values of t, this reduction by 1 can negatively impact the security of your application or service.
For example: In a 2-of-2 setup, a zero coefficient in any of the polynomials used to split your secret permits any share-holder to directly recover that byte of your secret. In practical terms, the impact of this is usually small: Knowing the 7th byte of a 256-bit AES key, for example, will still require you to attack the remaining 2^248 bits (31 bytes) of the unknown key. This is 256x faster than if all of the bytes were unknown, but the exponent is still large enough to be computationally infeasible.
To mitigate this risk, we updated our shamir-secret-sharing library to always select a nonzero leading coefficient. This has the benefit of ensuring that the degree of the polynomial is always what you expect, thus preserving the threshold requirement to recover each byte of your secret.
Rejecting a top coefficient 0 does introduce a theoretical concern with repeated iterations of the protocol: since you know one value that the upper coefficient will not be, repeatedly running the algorithm for the same secret will leak some information about the last coefficient. This requires that 1 fewer than the expected threshold, t, of shares is always compromised and that the secret is reused in order to leverage the bias introduced by a non-zero upper coefficient. In the real world, this isn’t a realistic exploit scenario.
For the abundantly cautious, here are a few ideas for eliminating this theoretical risk entirely.
Protocol-level mitigations
First, if you only ever run the SSS algorithm once per secret, an attacker with too few shares cannot distinguish between sets of shares that reject a leading coefficient of 0 and another set that tolerates a leading coefficient of 0.
If you need to reiterate the protocol for a compromised set of share-holders in order to do statistical analysis, then only doing it once directly addresses this concern.
Key derivation from a shared secret
If that’s not acceptable, using SSS on a sufficiently large random value that gets fed into a Key Derivation Function, and then using the KDF output to encrypt your shares (i.e., with AES-256-GCM), then partially recovering the actual recovered secret is insufficient to reduce the security of your overall application.
The alternative (using SSS on an asymmetric private key directly, without a hashing step) could have more theoretically interesting results with certain algorithms, since there is an algebraic structure involved.
Clamping the polynomial degree
One additional option we’re considering is increasing the order of the polynomial by 1, but setting the highest coefficient to a nonzero value.
This lets all significant polynomials tolerate zero values without ever reducing the degree of the polynomial. However, this idea has not undergone peer review yet.
Our Shamir Secret Sharing Library
At Privy, we believe technical decisions are moral decisions, which is why it was important that we open sourced our shamir-secret-sharing library. If you have any feedback on our implementation, thoughts on this post, or any other questions, feel free to reach out at security@privy.io.
We encourage you to take advantage of our open-source library. It’s become the canonical JavaScript implementation, and is fully compatible with both Node and browser environments, making it versatile for various use cases. It has also been rigorously reviewed by multiple cryptography auditing firms.
By using our library, you’re choosing a tool that has been thoroughly vetted and trusted by the cryptography community. Join us in making security more accessible and dependable for everyone.
