4
$\begingroup$

I read a Shamir secret sharing notes where it mentioned the security flaws of PSS(Proactive Security Sharing) when only one server is responsible for generating $h(x)$.

To give the question a bit context, I try to rephrase the scheme it mentioned as follows:


Consider a (n, t) Shamir secret sharing scheme with the following form

$$f(x)=a_{t-1}x^{t-1}+a_{t-2}x^{t-2}+\cdots+a_1x+s$$

To prevent an adversary from compromising $t$ servers over time, we need to periodically invoke PSS to refresh $s_i(i\in N_t)$. We ask a server to periodically generate a random function

$$h(x)=b_{t-1}x^{t-1}+b_{t-2}x^{t-2}+\cdots+b_1x$$

and calculate $h(i), i\in N_t$, it then sends $h(i)$ to i-th server and ask it to update its secret according to:

$$s'_i=s_i+h(i)$$

After every server updates its secret, PSS completes.


The notes claim that this scheme has security flaws.

Here is what it says:

However, this extension has a severe security flaw.

In cases where t > 2, it is not enough to let only one server select h(x): if the server that picks h(x) is compromised during PSS, then the adversary may know the relationship between new shares and old shares.

More precisely, the knowledge of h(x) may enable the adversary to figure out si from si', even if si has been deleted.

For example, consider a (5,3) sharing. Assume that server 1 (who selects h(x)) is compromised before PSS, and server 3 after.

The adversary knows shares s1 (s1'), s2, and s3'.

Moreover, the adversary can find out s2' from s2 (s2' = f'(2) = f(2) + h(2) = s2 + h(2)).

Then, the adversary has s1', s2', and s3', and consequently, s, even though less than 3 servers are compromised from the start of a PSS to the end of the next PSS.


My question is:

Why would the adversary know s2, given that it has only compromised server1 and server3?

$\endgroup$
3
$\begingroup$

Reading the quoted section and then looking at the notes, it seems that this is not well explained in the notes. However, my assumption is that the adversary has compromised s2 before PSS, but then lost access and therefore does not have access to s2'. If the adversary had access to s2', they wouldn't need to do the attack to get s2'.

So, the adversary has s1 and s2 from before PSS and gets s3' (and s1') after PSS. In neither case does the adversary have the required 3 shares. But, because the adversary knows h(x), it is able to compute s2' from s2. Which allows the adversary to recover s.

|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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