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'$?

  • 3
    Hint: the secret can be viewed as share 0. – fkraiem Jan 9 at 12:52
up vote 2 down vote accepted

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'$.

  • 1
    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 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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.