Skip to main content

RecoveryVault Demo

The App​

This is an educational mobile app designed to provide hands-on experiments and experience with Shamir's Secret Sharing.

How to use the app​

  1. Enter “the secret” (any text) in the primary text box. This text will be processed into shares.
  2. Optimally: enable or disable Randomize Share Size. The purpose of this is described in the Share Details section.
  3. Select a Threshold such as 2
  4. Select the number of Shares such as 3
  5. Tap the Generate Shares button. Tapping the button more than once will replace the previously generated shares with new shares applying a new set of randomized coefficients.
  6. Select any combination of shares to meet the previously defined Threshold.
  7. Tap the Reconstruct Secret button to apply the selected shares to decrypt/reconstruct and display the result matching the original secret.

Shamir’s Secret Sharing (SSS)​

Adi Shamir created it and published it in 1979. It is battle-tested, never fundamentally broken, and mitigations exist for known implementation risks.

This is a threshold (t, n) scheme (Shamir called it (k, n)) where k - 1 reveals virtually no information about the secret data: where n is the number of shares/shards and k is the required threshold.

Share issuance is commonly called encrypting, while threshold recovery or secret reconstruction is referred to as decrypting.

Fault-tolerant: E.g. N=10 (parties of 1 share) and K=3, then 7 parties could fail to provide the data but you can still get your secret.

Even more interesting, the shares do not contain any part of the original secret. Thus, reducing the level of trust required for a participant holding shares.

Why is it not everywhere?​

People often say: SSS is challenging and complicated for the average person. As we will explore, the protocol itself is very straightforward. A complete protocol implementation can be found on the Shamir’s Secret Sharing Wikipedia page. However, practical implementations are far more complicated when protecting for risks and variability outside of the protocol itself. Very few commercial products exist in the market that broadly address these risks. The creators of RecoveryVault offer such a ready-to-use product available today: SecretShield.

What can I use SSS with?​

Anything that can be represented as data (bytes) such as text or files. Real-world examples include: master passwords, seed phrases, private keys, and much more.

How does it work?​

The protocol uses polynomials, in most cases, “curves” but not necessarily elliptic curves. Specifically, cryptography is not classified as elliptic-curve or RSA (even though the S in RSA is Shamir).

Super Simplified​

If two people each know a point on a graph…we can figure out the secret:

Person 1) x=2, y=9
Person 2) x=5, y=15

In algebra class, we learned that given two points, we can calculate the slope and find the y-intercept. In this case, the secret is the y-intercept, i.e., the secret is y when x = 0

graph of a slope with 2 points

Thus when x=0, the secret is: 5.

Overly Simplified​

Just as above, people are issued shares. The shares contain points on a graph. They do not contain the polynomial, nor do they contain the threshold.

Assume a secret was issued with a threshold of 3. Four (4) shares were issued and each person was issued a single share. The creator has now requested to have the shares returned…

Shares:
Person 1/Share 1 - 4E6F
Person 2/Share 2 - 6283
Person 3/Share 3 - ???? ← This share could not be obtained.
Person 4/Share 4- CCED

In this case, we will use the share # as the ‘X’ coordinate and the values as the ‘Y’ coordinates. For this example, each ‘Y’ coordinate is one byte, so 4E6F is 2 ‘Y’ coordinates: (1, 4E) & (1, 6F) that we will plot on two (2) separate graphs. We will repeat this for each share.

Graph of the first point (below):
graph of first bytes

Graph of the second point (below):
graph of second bytes

Similar to the 2 point example to solve for the slope, we can use a Lagrange interpolation to find the polynomial equations for these curves.

As mentioned, above was an “oversimplification” - that is because regular polynomials could be subject to brute force attacks. Instead, we use cyclic polynomials.

graph of first bytes solved
Graph 1 (above) solves to be: y =x^3 + 4x^2 + x + 72

graph of seconds bytes solved
Graph 2 (above) solves to be: y =x^3 + 4x^2 + x + 105

We can now solve for the secret - when x = 0, y = 72, 105 ASCII = “Hi”

Why overly simplified?​

Applying regular polynomials with some algebra could produce a limited set of potential solutions. Therefore, it opens the door to brute-force attacks. The good news is that there is a mitigation/solution to this risk: cyclic polynomials.

Cyclic Polynomials​

Cyclic Polynomials are polynomials with mod(ulus) applied or rather part of the equations. A modulus is a division operation that ignores the quotient and captures only the remainder. For example, 17 mod 5 = 2.

Here is an example cyclic polynomial: f(x) = (x^3 + 4x^2 + x + 1028) mod 1723

graph of a cyclic polynomial

In this case, the secret would be 1028

When it comes to using cyclic polynomials securely for SSS, there are a few additional critical practices for the modulus. The divisor must be greater than ‘>’:

  • the secret
  • the coefficients (used internally for generating the shares)
  • the number of shares

The divisor must be a prime number.

Finally, the larger the prime number for the division, the lower the probability of finding/guessing the secret.

Secret = 1028

Share Details:​

As previously described, a share typically consists of an ‘X’ for its share number and its ‘Y’ points. If a point is in bytes, then a two-byte secret such as “Hi” would be represented as 3 bytes. While the share does not give away any of the secret’s contents, it could provide clues as to the size of the secret. This could be a problem if a malicious actor knows they want to comprise a secret that is known to be a specific number of bytes such as a 32-byte private key.

RecoveryVault offers a “Share Size Randomizing” toggle. When enabled, the secret is packed with additional random-sized data before generating the shares. The result is obfuscating the share size to not divulge the actual size of the secret.

Other considerations:​

  1. Never issue a ‘0’ share. We always issue shares id’s greater than zero (>0). A ‘0’ share would divulge the secret.
  2. When shares are issued, we don’t inform the shareholders as to the number of shares, the threshold, who is holding the shares, the polynomials used, etc. At most, their shares only represent the share # and points on the graph. Additional information could risk collusion, social engineering, or other compromises of the secret.
  3. Fault-tolerance is built in, but only if extra shares are issued and extra shares are known to have not been lost. If too many shareholders lose their shares a recovery may be impossible.

There are a variety of other considerations, which is the topic of a separate article.

Beyond​

Interested in using Shamir Secret Sharing? As described above, while the protocol is straightforward, practical implementation is very tricky. Don’t fear: the creators of this RecoveryVault Demo have SecretShield ready for use.