Shamir's Secret Sharing

When I was a kid, I had the opportunity to tour the Titan II Missile Museum in Arizona. It’s the last of the 54 silos across the U.S. that hasn’t been destroyed or filled in, and instead was turned into a museum for the public to learn about the history of the Cold War and how these silos operated. In part of the tour of the museum, they show you the control room, and mock out what would have happened if the silo had ever received the command to launch. One step of the process is that two separate individuals have to insert a key into panels on opposite sides of the room and turn them at the same time, ensuring that a launch could not be completed by a single individual (unless you’re Mrs. Incredible).

There are a few situations where the stakes are so high that we don’t want to trust a single person to have the full power to make a decision or act unilaterally. Broadly, this is referred to as the Two-person rule, and has lots of uses. The nuclear launch two key setup is just a single example of that rule in action, but it is used in banking, hazardous materials handling, aircraft piloting, and more.

In cryptography, the two-person rule can be enforced using Shamir’s Secret Sharing (SSS), a mathematical algorithm that reconstructs a secret by bringing together multiple parts (Adi Shamir is a famous cryptographer known for creating SSS and being one of the three creators of the RSA public key encryption scheme). SSS even has the ability to not just split into two, but can split a secret into any number of parts and can require a different number of those parts to be present to recreate the whole. Hashicorp’s Vault, a solution for securing and storing secrets, tokens, passwords, etc., supports using SSS to unseal the Vault. By default, Vault will generate 5 keys and requires at least 3 to be provided in order to unseal the Vault. This means that if you give each of the keys to a different person, it would require 3/5ths of the group to agree to unseal the Vault. No one or even two people could do it on their own.

The general principle of SSS relies on some basic concepts in math. To define a line, you need two points, (1,2) (3,7) for example. With only one of these points, there are an infinite number of lines that pass through the single point. For a parabola, you need three points. Four points for a cubic curve and so on. For a secret split into n parts where you require k pieces to be present to recreate the secret, SSS essentially generates a polynomial of degree k - 1, and then chooses n random points on the curve to distribute as the parts.

Let’s say like Vault, you want to generate n keys (in our case 5), and require k (in our case 3) of them to be present to recreate the original secret. SSS would use the original Vault encryption key as part of the curve, and then generate a random parabola (ax^2 + bx + c). Then it will randomly pick 5 points on that curve. This is a simplification of the math, especially since it doesn’t actually use basic integers, but rather a finite field. But since that’s over my head, it’s much easier to conceptualize using the simpler algebra you might have learned in school.

I find this algorithm insanely cool. I don’t know if there are any mystery novels out there that have SSS as a basis, but you could easily have a Knives Out style drama where the genius computer millionaire dies, but secretly leaves their children each a part of the secret, and enough of them have to agree to unlock their inheritance. Or maybe a spy novel where the latitude and longitude coordinates of spots on the globe represent the coordinates of the polynomial curve and can be used to save the world.

One downside to SSS is that when contributing the parts of the secret to try to recreate the whole, there is no way to verify that a part is valid. Meaning someone could contribute fake data and either prevent the reconstruction of the original secret, or even make the reconstructed data be something else entirely. I think this plays well in my spy novel idea, where an unexpected betrayal happens and a double agent is revealed. This whole concept is a Dan Brown novel just waiting to happen.

Written by James Quigley, an SRE/DevOps Engineer, and general tech nerd. Views and opinions are my own. Check out my YouTube Channel or follow me on Twitter!