# How to forge a Shamir secret share?

On this website, we have a lot of questions and answers devoted to Shamir secret sharing. We make it clear that Shamir secret sharing does not guarantee integrity. When we want integrity, we need to use a verifiable threshold scheme. But it is never explained how a malicious secret is actually forged.

Consider an easy setup of the scheme with 2 shares and threshold $k = 2$. Assume the adversary knows the secret message $m$ and share 1 (but not share 2). The shares are evaluated at $x_1 = 1, x_2 = 2$.

How does the adversary forge a chosen secret $m'$?

• Hint: the secret can be viewed as share 0. – fkraiem Jan 9 '18 at 12:52

Mike's answer is correct; however it turns out that, for $k>2$, the attacker can do better.

Assuming that the attacker knows:

• The actual shared secret
• His correct share
• The $x$-coordinates of everyone that will be involved in the recombination

He can then modify his share to make the recombined secret any value he wants (within the finite field). If $k > 2$, he won't get enough information to recover the polynomial; however he doesn't need that.

Assuming that the attacker has share 1 (and hence he knows $y_1$), he knows the x-coordinates of everyone $x_1, x_2, ..., x_k$, the secret $S$, and wants to modify his share so that the revealed secret will be $S'$.

What he does is modify his share $$y'_1 = y_1 + (S' - S)\prod_{j=2}^{k}\frac{x_j - x_1}{x_j}$$

Here's how that works; the recombination phase of Shamir can be summarized as the equation:

$$S = \sum_{i=1}^k \ y_i \prod_{j=1, j \ne i}^{k}\frac{x_j}{x_j - x_i}$$

By including his modified share, the attacker change this to:

$$\left(y_1 + (S' - S)\prod_{j=2}^{k}\frac{x_j - x_1}{x_j}\right)\prod_{j=2}^{k}\frac{x_j}{x_j - x_1} + \sum_{i=2}^k \ y_i \prod_{j=1, j \ne i}^{k}\frac{x_j}{x_j - x_i}$$

which is

$$(S' - S)\prod_{j=2}^{k}\frac{x_j - x_1}{x_j}\prod_{j=2}^{k}\frac{x_j}{x_j - x_1} + \sum_{i=1}^k \ y_i \prod_{j=1, j \ne i}^{k}\frac{x_j}{x_j - x_i}$$

which simplifies to $S'$

For us to make it exciting, let's first define the meaning of two sample messages:

• $m :$ "yes, in case of m.a.d., do fire the missiles"
• $m' :$ "no, do not fire missiles"

Let's guess that the current president has chosen $m$ as the message, and we the adversary (and holder of share 1) want to change it to $m'$.

Recall that the polynomial is of the following form:

$$p(x) = a_1x + m$$

We know share 1. In other words we know a value $y_1$ such that :

$$y_1 = a_1 + m$$

So now we have two values. This is enough to get the original polynomial back. We now know the original polynomial, and can reconstruct the second share:

\begin{align} p(x) &= (y_1 - m) \cdot x + m \\ y_2 = p(2) &= (y_1 - m) \cdot 2 + m \end{align}

During the recombination phase of the algorithm, the secret $m$ will be constructed by computing $2y_1 - y_2 = m$. We can rewrite this equation and compute a new forged $y_1'$:

$$y_1' = \frac{m' + y_2}{2} = \frac{m' + (y_1 - m) \cdot 2 + m}{2}$$ Which simplifies to: $$y_1' = y_1 + \frac{m' - m}{2}$$

Now we have constructed a new share which will, together with the second share, combine to the new secret message $m'$.

We see that in your (my?) case we could indeed choose any new message $m'$.

• That's exactly what fkraiem's comment and mikeazo's answer stated. If everything but one share is known (regardless of total number), then that share is fixed. And since it's information-theoretic, you can find exactly one such share for every secret m you choose. And of course two different m can't be the same polynomial. Or the other way around: Reconstructing the polynomial from $x=0$ and $x=1$ isn't any different than reconstructing the polynomial from $x=1$ and $x=2$. – tylo Jan 9 '18 at 14:43

To 1, the adversary uses knowledge of his share and the fact that the secret $m$ is the sharing polynomial evaluated at $0$ to reconstruct the original polynomial and then recover the unknown share. Given the unknown share, the adversary can easily figure out a new share 1 (at $x_1=1$) such that the recovered secret will be $m'$.

To 2, the only limitation is that the $m'$ must be from the original finite field.