Shamir’s Secret Sharing

For those of you interested in cybersecurity, or perhaps if you work in the field, you’ll face the massive topic of cryptography sooner or later. I wouldn’t call myself a cryptography expert by any means. The subject is vast, fascinating, and can be quite intimidating, especially with all the math involved! I prefer to learn complex topics by breaking them down into smaller parts, which, by the way, is the essence of Shamir’s Secret Sharing. Segmenting a topic into more manageable chunks makes it easier to grasp the concepts.

During my endeavor to expand my cryptography knowledge, I decided to write this post on Shamir’s Secret Sharing. Don’t worry, you don’t need a master’s degree in cryptography to grasp the essence of this brilliant algorithm. I’ll do my best to ensure you walk away from this blog post with a good understanding of its inner workings as well as its real-world applications!

I’ve also included some Python script here which you can use along with the example in the blog, to reconstruct the secret.

Shared Secrets

Imagine you and your friends have found a treasure chest, but the key to open it is too precious to allow any one person look after it. You all agree that no single person should possess the key because it’s too risky. But what if you could split the key into pieces so that you’d need, say, three out of four pieces to unlock the chest? Now you have a system that feels less risky, more secure, and democratic. This simple example captures the essence of Shamir’s Secret Sharing (SSS), a method for securely managing sensitive information like passwords or encryption keys.

Shamir’s Secret Sharing is an algorithm developed by Adi Shamir (the ‘S’ in RSA cryptography, pictured here) in 1979. At its core, it’s a cryptographic method designed to divide a secret into multiple shares. To reconstruct the original secret, you’ll need a predefined number of these shares. In simpler terms, it breaks down a large secret into smaller ‘chunks’, and you need a specific number of those chunks to make the original secret whole again.

Real World Applications (HashiCorp Vault)

Throughout my career, particularly in the last five years, I’ve observed application development teams using secrets management tools like AWS Secrets Manager and HashiCorp Vault. These tools provide a solution for securely storing, managing, and controlling access to secrets like passwords, API keys, and cryptographic keys. These tools enable organizations to centralize sensitive information while enforcing access policies across distributed systems. But how does something like Vault maintain the integrity of its master encryption key? Here’s where Shamir’s Secret Sharing shines.

SSS isn’t just an academic concept; it’s a practical solution for everyday cybersecurity problems. Vault uses a master key to secure its contents. You can imagine how disastrous it would be if that master key ended up in the wrong hands. To mitigate single-point-of-failure risks, this master key is never stored. Instead, it’s divided into shares using (you guessed it) SSS. The Vault remains ‘sealed’ until a sufficient number of these shares are provided to ‘unseal’ it.

When the Vault server starts up, it’s in a ‘sealed’ state, meaning no operations on secrets can occur. To reach an ‘unsealed’ state where secrets can be accessed or manipulated, a certain number of shares (the threshold) must be presented to reassemble the master key. This mechanism ensures that no single person can unseal the Vault, thus boosting the overall security posture. Cool, huh?

The Unsealing Process

1. Initialization: When Vault is initialized, it uses SSS to break the master key into n number of shares. As the administrator, you specify the threshold, how many of these shares are needed to reconstruct the master key.
2. Distribution: The shares are then distributed among trusted individuals or systems. No single person or system holds the complete master key, aligning with the principle of ‘least privilege.’
3. Unsealing: To make Vault operational, the predefined threshold of shares must be re-entered, enabling the reconstruction of the master key. This is typically done by multiple operators each entering their share of the key, ensuring a multi-person rule for enhanced security.
4. Operations: After unsealing, the master key decrypts an in-memory encryption key, which is then employed for encrypting and decrypting the stored secrets.

Enhanced Security and Governance with Vault

The brilliance of this setup lies in the fact that no single individual can unseal the Vault, thereby gaining access to all stored secrets. This setup not only fortifies security but also helps organizations meet compliance mandates for multi-person control over sensitive data. It reminds me of the opening scene in ‘Wargames,’ where two military officers must simultaneously turn keys on opposite sides of the room to initiate a missile launch. I think they did something similar in Stranger Things, but I digress!

It’s worth noting that Vault supports automated unsealing through integration with Transit, or other cloud-based Key Management Services (KMS) such as AWS KMS, Azure Key Vault, and Google Cloud KMS. These services enable the offloading of key management duties to a cloud provider, thereby automating Vault’s unsealing process.. More on that here.

In an automated setup, Vault can be configured to use cloud KMS services for automatic master key decryption, eliminating the need for manual input from operators. This simplifies Vault management in dynamic and large-scale deployments, where manual intervention could be either impractical or even a security risk.

How Shamir’s Secret Sharing (SSS) Works

Let’s start by breaking down how the algorithm works. Imagine you have a secret you want to protect. For the sake of this example, let’s say the secret is the number 5. You could choose any number as the secret, but we’ll stick with 5 to keep things simple. Now, you want to share this secret among five of your friends, but you want to ensure that at least three of them have to get together to reconstruct the secret. Here’s how you’d go about it:

Initialization

First off, we’ll create what’s known as a ‘polynomial’. This is a mathematical equation designed to divide the secret into distinct shares. Let’s say our secret is the number ‘5.’ This number goes into the polynomial equation like this:

In the context of Shamir’s Secret Sharing, \(x\) is just a placeholder (or variable) that you can plug different numbers into. In this case, these \(x\) values are as simple as 1, 2, 3, etc., one for each friend you’re sharing the secret with. By entering these numbers into the polynomial equation, you generate unique ‘shares’ that you can distribute.

1. Choosing the Secret: Our secret is the number 5. This is the number we’re going to hide using the equation.
2. Choosing Random Numbers: For simplicity, we’ll go with 2 and 3 as our random numbers. Each time you initiate Shamir’s Secret Sharing, these numbers would typically be chosen at random and serve to obfuscate the secret in the shares you distribute.
3. Creating the Equation: Now, we use these numbers to make our polynomial equation. So it would look like this:

Share Distribution

Now let’s move on to generating the shares for our friends.

1. For each of your five friends, you’ll place a different number into \(x\) in the equation you created. Let’s say for Friend 1, you use \(x=1\), for Friend 2 you use \(x=2\), and so on.
2. Plug in a unique \(x\) value for each friend, resulting in distinct numbers that serve as their shares.
3. Each of the resulting numbers (points) serve as a ‘share.’ It’s a scrambled version of your secret, plus some extra numbers to make it look random.
4. You distribute one share to each friend.

For example:

• Friend 1: \(f(1)=5+2(1)+3(1)^2=5+2+3=10\)
• Friend 2: \(f(2)=5+2(2)+3(2)^2=5+4+12=21\)
• Friend 3: \(f(3)=5+2(3)+3(3)^2=5+6+27=38\)
• Friend 4: \(f(4)=5+2(4)+3(4)^2=5+8+48=61\)
• Friend 5: \(f(5)=5+2(5)+3(5)^2=5+10+75=90\)

While the individual calculations shown here for each friend are a great way to make sense of the function, it’s just a visual representation of what is happening with \(f(x)=5+2x+3x^2\). Nonetheless, I included the break down friend-by-friend like this, as it helped me demystify what can otherwise be an abstract concept.

Reconstructing the Secret

When it comes to revealing the secret, at least three of your friends need to come together with their individual shares. The ingenious aspect of Shamir’s Secret Sharing is that a minimum required number of participants is needed to reconstruct the secret, enhancing both security and integrity.

• Pooling Shares: Your friends initiate by collecting their shares. For example, Friend 1 has a share of 10, Friend 2 has a share of 21, and Friend 3 has a share of 38. These shares are like pieces of the key, and when combined, they can solve for the original equation.
• Reverse Engineering the Equation: To reveal the secret, your friends use methods like Lagrange interpolation to find the original polynomial equation. Essentially, they’re working backward through the formula. When you generate the shares, you’re plugging numbers into the polynomial; now, your friends are using those shares to uncover the original polynomial.
• Revealing the Secret: The result of these calculations will reveal the original polynomial equation, \(f(x)=5+2x+3x^2\). Once this equation is disclosed (i.e., the secret is unveiled), you’ll find that the constant term of the polynomial is 5, which in this context is the secret you’re trying to protect.

So there it is! The secret is successfully revealed when a minimum required number of three friends pool their shares together. This method thrives on the collaborative effort needed to reveal the secret.

Python Code for Reconstruction

The lightbulb really went on for me when I created this simple Python script, which reconstructs our example. So, using three of our friends’ shares; 10, 21, and 38, we can reconstruct our secret, which is 5.

This script leverages NumPy’s Polynomial class to fit a polynomial equation to the given points (shares). Once we have the coefficients of the polynomial, the first one should be our original secret (which in this case is 5). Running this code should yield an output confirming that the reconstructed secret is indeed 5. Also, try it out with another three points by changing shares = [(1, 10), (2, 21), (3, 38)].

Tip: If you decide to try a different point (share), don’t forget to update the corresponding \(x\) value.

from numpy.polynomial.polynomial import Polynomial
import numpy as np

# Shares from three friends: (x, f(x))
shares = [(1, 10), (2, 21), (3, 38)]

# Extract x and y values from shares
x_values, y_values = zip(*shares)

# Use NumPy's Polynomial.fit function to find the coefficients of the polynomial
p = Polynomial.fit(x_values, y_values, 2)

# Coefficients of the polynomial
coefficients = p.convert().coef

# The first coefficient is the secret
secret = round(coefficients[0])

print(f"The reconstructed secret is: {secret}!")

The magic lies in the underlying mathematics and computational power that Python libraries like NumPy bring to the table. If I were going to try and solve this problem with a calculator, I would essentially be doing what’s called a ‘polynomial interpolation,’ the process of finding a polynomial that goes through a given set of points. The ‘polynomial interpolation’ is all about connecting the dots, or more accurately, points, in a way that lets us rebuild the original polynomial equation.

Dealing with Complex Secrets

Our example used the number 5 as the secret for ease of understanding. However, Shamir’s Secret Sharing accommodates various types of secrets. In real-world applications, the secret could range from a complex password to an encryption key. When faced with a complex secret, it’s converted into numerical form through hash functions or other encoding methods. This enables the algorithm to work consistently, regardless of the original format of the secret.

Summary

So there you have it! A deep dive into Shamir’s Secret Sharing (SSS), unpacking how it offers both security and democracy when you’re looking to protect a secret! I hope this has been useful to you!