Why is Shamir Secret Sharing not secure against active adversaries out-of-the-box?

Question

This linear secret sharing scheme allows us to share a secret between n parties, such that only an honest majority can reconstruct it.

I understand that – because I do not allow the user to certify the authenticity of the shares nor the value they reconstruct (using for instance VSS or some kind of homomorphic MAC) – they are secure only on the semi-honest case. However, in my mind that problem is more related to integrity, because that even if the adversary sends an incorrect share, the output is unpredictable, and as far as my understanding goes, indistinguishable from randomness.

If that is the case, is there any way an active adversary can learn something by deviating from the protocol i.e., information about the private inputs of the honest parties? If that is so, what would it be?

Answer 1

Here is an active attack on the privacy of out-of-the-box SSS. For this attack, we'll assume that the attacker (without a valid share) is allowed to participate (with $T-1$ friends with honest key shares), jointly use the protocol to recover a 'shared secret' (which might not be the real shared secret); we'll assume that this shared secret recovery process is done by some MPC-secure method so that the attacker learns nothing other than the final value. We also assume that everyone's $x$ coordinate is public.

First off, the attacker picks a value $x_a$ which is an $x$ coordinate which is not the $x$-coordinate shared by anyone else. If the dealer were to generate a share with that $x_a$ value, it would generate a $y$-coordinate that we'll call $y_a$; obviously, the attacker does not know this $y_a$ value.

Then, the attacker then gets a set of $T-1$ friends, and have them recover a shared secret value using their shares (and the attacker will contribute the value $(x_a, 0)$; (actually, a nonzero value for the $y$ coordinate would work, but make the explanation slightly more involved); they'll go through the SSS recovery process, and obtain a value which we'll denote as $S_0$.

If we call the real shared secret $S$, then what the attacker can do is derive a value $T_0$ (which depends on the $x$-coordinates of him and his friends), and derive the linear equation:

$$S = T_0 y_a + S_0$$

This is a linear equation in two unknowns ($S, y_a$), and $T_0 \ne 0$, and so the attacker cannot derive any information about $s$ from it. This can also be derived from the security properties of SSS; the attacker and his $T-1$ friends only have $T-1$ valid shares, and so of course they cannot recover $S$.

What the attacker then does is get together a different set of $T-1$ friends (there can be some overlap, but there must be at least one difference), and do the same thing again (with the attacker using the same $(x_a, 0)$ share. They do the same thing, deriving a 'shared secret' value $S_1$, and the attacker ends up with a second linear equation:

$$S = T_1 y_a + S_1$$

Now, if $T_0 \ne T_1$ (which is likely if the two sets of friends are distinct), the attacker has two linear equations in two unknowns; it's trivial to solve for $S$.

Answer 2

Here's one more way in which a dishonest participant can mess with Shamir's secret sharing:

Let's briefly review how secret reconstruction in Shamir's $(k,n)$ secret sharing works. Given the $x$-coordinates of $k$ participants $(x_1, x_2, \dots, x_k)$, one way to reconstruct the secret is to compute the Lagrange basis polynomials: $$\ell_j(x) = \prod_{1 \le i \le k, i \ne j} (x-x_i)\,(x_j-x_i)^{-1},$$ which have the property that $\ell_j(x_j) = 1$ and that $\ell_j(x_i) = 0$ for all $i \ne j$. The polynomial $p(x)$ that interpolates the shares $(x_i, y_i)$ can then be calculated as the linear combination: $$p(x) = \sum_{1 \le j \le k} y_j \, \ell_j(x), $$ and the secret recovered as $S = p(0)$. Equivalently, we may also first evaluate the basis polynomials at the origin to obtain the coefficient $c_j = \ell_j(0)$, and then simply reconstruct the secret as a linear combination of the shares: $$S = \sum_{1 \le j \le k} y_j\, c_j.$$

Now, assuming that the $x$-coordinates are public (or revealed during the reconstruction process, as they eventually must be), any participant $j$ can calculate their own coefficient $c_j$ in advance, before any of the $y$-coordinates are revealed.

In particular, this implies that if a single dishonest participant $j$ reveals the false $y$-coordinate $y'_j = y_j + \delta$ instead of their true coordinate $y_j$, then the reconstructed secret will end up being $s' = s + \delta \, c_j$ instead of the true secret $j$. Knowing $\delta$, this dishonest participant can then recover the true secret $s = s' - \delta \, c_j$, while all the other participants are left with just the bogus value $s'$ and no way to reconstruct $s$.

Furthermore, the dishonest participant can easily choose the difference between the true secret $s$ and the recovered secret $s'$, simply by adjusting their share by $\delta = (s' - s) \, c_j^{-1}$. If they can somehow guess what the true secret is, this even lets them choose exactly what the revealed bogus secret will be.

If there are exactly $k$ participants in the sharing process, then such manipulation will be undetectable. With more than $k$ participants, the manipulation will still work, but (unless there are multiple dishonest participants colluding together) the resulting interpolation polynomial will typically be of a degree higher than the expected $k-1$, which should ring some alarm bells.

Answer 3

In your example, let's assume the secret sharing scheme is a $(k,n)$-threshold sharing scheme with $k = \frac{n + 1}{2}$, as you say only an 'honest majority' can construct the secret.

If then $n$ protocol-following parties release their information to the group, an adversarial participant can then construct the whole secret, as they have a share, without broadcasting this share to the other parties. In this way, the adversary has the secret, but the protocol-following parties do not.

This violates the fairness property of the scheme, as adversarial behaviour has given one party an advantage -- they can compute the secret whereas no others can.

According to these slides from RHUL, the undesirable consequences of the adversary withholding his share and publishing a fake one include:

1. Preventing the honest participants from learning the correct secret
2. Failing to alert the other participants that they have not reconstructed the correct secret
3. Allowing the adversary to learn the correct secret.

Answer 4

Shamir SS is focused exactly on the problem of learning something about the secret $s$ from a subset of less than $t$ shares. Because of its construction, said subset won't leak anything at all.

The two limitations of the basic version of Shamir SS are involved with each of the parties (the dealer and the shareholders) abiding to the protocol:

1. The dealer can deal inconsistent shares during the dealing fase.
2. One/some of the shareholders send an incorrect share (not the one dealt by the dealer) during the reconstruction phase.

The problem is not secrecy, but the difficulty of proving the consistency of the values involved. As an example, suppose that $s$ is a secret key for the following protocol:

1. The dealer generates $s$ and a corresponding public key $p$.
2. $p$ is published.
3. The dealer deals shares.
4. The dealer deletes $s$.
5. A third party encrypts a message to $p$.
6. $t$ of the shareholders execute the reconstruction protocol.
7. The reconstructed secret $s*$ is used to decrypt the message produced in the step 5.

If the dealer sends random values instead of shares of $s$, the step 6 will fail. If any of the shareholders sends a wrong share, the step 6 will fail. In both cases, the original secret will be lost, and it won't be possible to decrypt the message sent in the step 5.

Imagine the protocol is used for online voting, as it is a common application of MPC. If the decryption and tallying of votes fails for such an error, repeating the process will not be an option that voters like. The idea of VSS is to ensure the consistency of the process: if the shares dealt don't "make sense" (e.g. aren't related to the public key) or one of the shareholders sends a fake share, the protocol will halt and be able to trace the fault on time.