# Eric Rafaloff

My personal blog on software development and security

Home » Key Shards and Shamir’s Secret Sharing Scheme

# Key Shards and Shamir’s Secret Sharing Scheme

Consider a scenario in which you are tasked with managing the security of a bank’s vault. The vault is considered impenetrable without a key, which you are given on your first day on the job. Your goal is to securely manage the key.

Let us suppose that you decide to keep the key on you at all times, granting access to the vault on an as-needed basis. You quickly learn that such a solution doesn’t scale well in practice, as your physical presence is required whenever the vault needs to be opened. What about those vacation days you were promised? Also, perhaps more frighteningly, what if you lost the one and only key?

With your vacation days in mind, you decide to make a copy of the key and entrust it with another employee. However, you realize that this isn’t ideal either. In doubling the number of keys, you have also doubled the number of opportunities for a thief to steal the vault’s key.

Out of desperation, you destroy the duplicate and decide to split the original key in half. Now, you think, two trusted people must be physically present with each key shard to reassemble the key and unlock the vault. This means that a thief would need to steal two key shards to reassemble the original key, which is double the amount of work of stealing one key. However, you soon realize that this scheme isn’t much better than simply having one key, because if either of you were to lose a key half then the full key cannot be recovered anyway.

This problem can be solved with a series of additional keys and locks, but can quickly require a lot of keys and locks when approached this way. You decide that an ideal key management scheme must involve splitting up a key, so that the security of the key isn’t fully entrusted with one person. You also conclude that some threshold of key shards should be required for key reassembly, so that one person losing their key shard (or going on vacation) doesn’t render the entire key unrecoverable.

## How to Share a Secret

This is the type of key management scheme that Adi Shamir was thinking about in 1979 when he published How to Share a Secret. The paper concisely explains a so-called $(k,n)$ threshold scheme that can be used to efficiently split up a secret value (e.g. a cryptographic key) into $n$ shares. Then, if and only if at least $k$ of any $n$ shares are collected, it should be easy to recover the secret, $S$.

An important security goal of this scheme is that an attacker should learn absolutely nothing if they don’t have at least $k$ shares. Even $k - 1$ shares should provide no information.

## Polynomial Interpolation

Shamir’s $(k,n)$ threshold scheme is built around the concept of polynomial interpolation. If you’re not familiar with this concept, it’s actually quite simple. In fact, if you’ve ever plotted points on a graph and then drew lines or curves to connect them, you’ve already used it!

Consider a polynomial function with a degree of one, $f(x) = x+2$. If you wanted to plot this function on a graph, how many points would you need? Well, we know this is a linear function, which forms a line and therefore needs at least two points. Next let us consider a polynomial function with a degree of two, $f(x) = x^2 +2x + 1$. This is a quadratic function, and therefore requires at least three points to plot on a graph. How about a polynomial with a degree of three? At least four points. And so on and so forth.

The really neat thing about this property is that given the degree of a polynomial function and at least $degree + 1$ points, we can plot additional points for that polynomial function. We call extrapolating those additional points polynomial interpolation.

## Plotting A Secret

You may already see Shamir’s clever scheme beginning to play out here. Let us suppose that our secret, $S$, is $42$. We can turn $S$ into a point on a graph, $(0,42)$, and come up with a polynomial function with a $k-1$ degree that satisfies this point. Recall that $k$ is going to be our threshold of required shares, so if we want a threshold of three shares, we should choose a polynomial function with a degree of two.

Our polynomial function is going to take the form $f(x) = a_0+a_1x+a_2x^2+a_3x^3+...+a_{k-1}x^{k-1}$, where $a_0 = S$ and $a_1,...,a_{k-1}$ are randomly chosen positive integers. All we’re doing is constructing a polynomial function with a $k-1$ degree, where the free coefficient, $a_0$, is our secret, $S$, and the proceeding $k-1$ terms each have a randomly chosen positive coefficient. If we go back to our original example and suppose that $S = 42, k = 3, a_1,...,a_{k-1} = [3,5]$, then we get the function $f(x) = 42 + 3x + 5x^2$.

At this point we are free to generate our shares by plugging $n$ unique integers into $f(x) = 42 + 3x + 5x^2$ where $x \neq 0$ (since that’s our secret). In this example we want to distribute four shares with a threshold of three, so we randomly generate the points $(18, 1716), (27, 3768), (31, 4940), (35, 6272)$ and send one point to each of our trusted four individuals. We also inform the individuals that $k = 3$, since this is considered public information and is needed to reveal $S$.

## Revealing S

We already discussed the concept of polynomial interpolation, and how it is the very foundation of Shamir’s $(k,n)$ threshold scheme. When any three of our four entrusted individuals want to reveal $S$, all they need to do is interpolate $f(0)$ with their unique points. To achieve this they can define their points, $(x_1,y_1),...,(x_k,y_k) = (18, 1716), (27, 3768), (31, 4940)$, and calculate a Lagrange interpolating polynomial using the following formula. If you’re more comfortable with programming than math, the pi is basically a for statement that multiplies all the results together, and the sigma a for statement that adds all of the results together.

$$P(x) = \sum_{j=1}^{k} p_j(x)$$ $$P_j(x) = y_j \prod_{\scriptstyle m=1\atop\scriptstyle m\neq j}^{k}\frac{x-x_m}{x_j-x_m}$$

When $k = 3$, we can solve this like so and get back our original polynomial function:

\begin{aligned}P(x) &= {y_1}\left({x-x_2 \over x_1-x_2}\cdot{x-x_3 \over x_1-x_3}\right) + {y_2}\left({x-x_1 \over x_2-x_1}\cdot{x-x_3 \over x_2-x_3}\right) + {y_3}\left({x-x_1 \over x_3-x_1}\cdot{x-x_2 \over x_3-x_2}\right) \\ P(x) &= {1716}\left({x-27 \over 18-27}\cdot{x-31 \over 18-31}\right) + {3768}\left({x-18 \over 27-18}\cdot{x-31 \over 27-31}\right) + {4940}\left({x-18 \over 31-18}\cdot{x-27 \over 31-27}\right) \\ P(x) &= 42 + 3x + 5x^2\end{aligned}

Since we know $S = P(0)$, revealing $S$ is simple:

\begin{aligned}P(0) &= 42 + 3(0) + 5(0)^2 \\ P(0) &= 42\end{aligned}

## Exploiting Insecure Integer Arithmetic

Although we’ve successfully applied the fundamental idea behind Shamir’s $(k,n)$ threshold scheme, we have a remaining problem that we’ve ignored up until now. Our polynomial function uses insecure integer arithmetic. Consider that for every additional point an attacker obtains on our function’s graph, the smaller number of possibilities remain for what other points can be. You can begin to see this deduction visually as you graph an increasing number of points for a polynomial function using integer arithmetic. This is counterproductive to our stated security goal that an attacker should learn absolutely nothing if they don’t have at least $k$ shares.

To demonstrate how weak the scheme is when integer arithmetic is used, consider a scenario in which an attacker has obtained two points, $(18, 1716), (27,3768)$, and knows the public information that $k = 3$. From this information they can derive the degree of $f(x)$, which is two, and plug in known $x$ and $f(x)$ values.

\begin{aligned}f(x) &= a_0 + a_1x + a_2x^2 + a_3x^3 + ... + a_{k-1}x^{k-1} \\ f(x) &= S + a_1x + a_2x^2 \\ f(18) &= 1716 = S + a_118 + a_218^2 \\ f(27) &= 3768 = S + a_127 + a_227^2\end{aligned}

An attacker can then deduce potential values of $a_1$ by simplifying $f(27) - f(18)$:

\begin{aligned}3768 - 1716 &= (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) \\ 2052 &= 9a_1 + 405a_2 \\ 9a_1 &= 2052 - 405a_2 \\ a_1 &= \frac{2052 - 405a_2}{9} \\ a_1 &= 228 - 45a_2\end{aligned}

Since we defined $a_1,...,a_{k-1}$ to be randomly chosen positive integers, there are only so many possibilities for what $a_2$ can be. With this information, an attacker can conclude $a_2 \in [1,2,3,4,5]$, since 6 would make $a_1$ negative. This turns out to be true since we defined $a_2 = 5$.

From there an attacker can begin to deduce $S$, by replacing $a_1$ in $f(18)$:

\begin{aligned}1716 &= S + a_118 + a_218^2 \\ 1716 &= S + 18\left(228 - 45a_2\right) + a_218^2 \\ 1716 - S &= 18\left(228 - 45a_2\right) + a_218^2 \\ -S &= 18\left(228 - 45a_2\right) + a_218^2 - 1716 \\ -S &= 4104 - 810a_2 + a_218^2 - 1716 \\ S &= -4104 + 810a_2 - a_218^2 + 1716 \\ S &= 810a_2 - 324a_2 -2388 \\ S &= 486a_2 - 2388\end{aligned}

With the limited set of possibilities for what $a_2$ can be, as deduced by the attacker earlier, it’s clear how easy it would be to brute force $S$ (there are only five possibilities).

In order to address this vulnerability, Shamir proposes that we use modulo arithmetic, changing $f(x)$ to $f(x) \mod p$ where $p \in \mathbb{P} : p > S, p > n$ and $\mathbb{P}$ is a set of all prime numbers.

A little reminder of how modulo works. Reading a clock is already a familiar concept, and uses hours that are $\mod 12$. As soon as the hour hand goes past twelve, it wraps back around to one. An interesting property of this system is that by simply looking at a clock, we can’t deduce how many times the hour hand has wrapped around. That is to say, if 48 hours have passed, I wouldn’t know that just from learning that it is 1:30. However, if we know that the hour hand has passed twelve 4 times, we can fully solve for the number of hours that have passed with a simple formula, $a = mq + r$, where $m$ is our modulo divisor (here $m = 12$), $q$ is our quotient (the number of times that our divisor evenly goes into the original number, here $q = 4$), and $r$ is our remainder, which is usually what calling a modulo operator gives us (here $r = 1.5$). Knowing all of these values allows us to solve for $a = 49.5$, but if we were missing the quotient, we would never be able to reconstruct our original value.

We can demonstrate how this helps the security of our scheme by applying it to our previous example and using $p = 73$. Our new polynomial function is $f'(x) = 42 + 3x + 5x^2 \mod 73$, and our new points are $(18, 37), (27, 45), (31, 49), (35, 67)$. Our entrusted individuals can once again use polynomial interpolation to recover our function, only this time working in a prime order field.

Using this new example, let’s suppose that our attacker has obtained knowledge of two of these new points, $(18, 37), (27, 45)$, and the public information $k = 3, p = 73$. This time the attacker deduces the following functions based on all of the information they have, where $\mathbb{N}$ is a set of all positive integers, and $q_x$ represents the quotient of the modulo of $f'(x)$.

\begin{aligned}f'(x) &= S + a_1x + a_2x^2 \mod 73 \\ f'(x) &= S + a_1x + a_2x^2 - 73q_x : q_x \in \mathbb{N} \\ f'(18) &= 37 = S + a_118 + a_218^2 - 73q_{18} \\ f'(27) &= 45 = S + a_127 + a_227^2 - 73q_{27}\end{aligned}

Now our attacker again attempts to deduce potential values of $a_1$, by simplifying $f'(27) - f'(18)$:

\begin{aligned}45 - 37 &= (S - S) + (27a_1 - 18a_1) + (729a_2 - 324a_2) + (-73q_{27} - (-73q_{18})) \\ 8 &= 9a_1 + 405a_2 + 73(q_{18} - q_{27}) \\ -9a_1 &= -8 + 405a_2 + 73(q_{18} - q_{27}) \\ 9a_1 &= 8 - 405a_2 - 73(q_{18} - q_{27}) \\ a_1 &= \frac{8 - 405a_2 - 73(q_{18} - q_{27})}{9} \\ a_1 &= \frac{8}{9} - 45a_2 - \frac{73}{9} (q_{18} - q_{27})\end{aligned}

From there our attacker again attempts to deduce $S$, by replacing $a_1$ in $f'(18)$:

\begin{aligned}37 &= S + 18\left(\frac{8}{9} - 45a_2 - \frac{73}{9} (q_{18} - q_{27})\right) + a_218^2 - 73q_{18} \\ -S &= 18\left(\frac{8}{9} - 45a_2 - \frac{73}{9} (q_{18} - q_{27})\right) + a_218^2 - 73q_{18} - 37 \\ S &= -18\left(\frac{8}{9} - 45a_2 - \frac{73}{9} (q_{18} - q_{27})\right) - 324a_2 + 73q_{18} + 37 \\ S &= 486a_2 + 21 + 219q_{18} - 146q_{27}\end{aligned}

This time around, our attacker has a serious problem. They are missing the values of $a_2$, $q_{18}$, and $q_{27}$. Since there are an infinite number of possible permutations for these variables, there is no additional information that can be gained.

## Application Considerations

In our example and Shamir’s original paper, we used a prime order field to perform modulo arithmetic. Other finite fields can also be used, such as a binary field, $GF(2^n)$, which is efficient when used in binary computation. Such a field also makes it easy to shard encryption keys of $2^n$ bits, which can be seen as the digital equivalent to the solution we sought in our original vault problem. Such a scheme could be deployed to a group of individuals who wish to collectively encrypt, decrypt, and/or sign messages, while also reaching a consensus.

It’s also important to note that our concerns about security may extend beyond just the scheme itself. For real world cryptography applications, there is often the threat of side channel attacks, in which an attacker attempts to extract useful information from application timing, caching, fault, and more. If this is a concern, careful considerations should be made during development, such as using constant time functions and lookups, preventing memory from paging to disk, and a bunch of other things that are beyond the scope of this blog post.

Finally, Shamir’s secret sharing scheme, while offering information theoretic security, does have a known issue. The scheme by itself does not offer what is known as verifiable secret sharing, which means that individuals are free to submit fake shares during secret reconstruction. This should be kept in mind when applying the scheme.

Name: ericr