3
$\begingroup$

The popular command line utility ssss implements the classic Shamir's secret sharing scheme over the generic field $GF(2^q)$ with $8 \le q \le 1024$.

When $q>=64$, the constant coefficient ($c_0$) is not the secret but a transformed version of it, obtained by means of 40 rounds of XTEA-based permutation. As result, the secret is somewhat diffused over the entire $q$ bits.

Why is that? Which attack does it prevent? Does it help when the secret has a short bit length?

$\endgroup$
3
  • $\begingroup$ Note that, despite your notation, the exponent does not need to be prime. $\;$ $\endgroup$
    – user991
    Apr 20, 2014 at 18:07
  • $\begingroup$ I replaced p with q to avoid confusion. $\endgroup$ Apr 20, 2014 at 18:33
  • $\begingroup$ Based on your description, it serves no purpose. $\endgroup$
    – K.G.
    Apr 20, 2014 at 18:56

2 Answers 2

4
$\begingroup$

I took a brief look at the code, but I fail to see how this transformation could introduce any additional secrecy. If the randomness used to define the polynomial is good, then Shamir's secret sharing provides information theoretic secrecy (no matter how the secret actually looks like). What Ricky points out in his answer seems reasonable, i.e., to provide some means against the malleability of the secret sharing. Since Shamir's approach is linear, one can "update" the shares to "update" the secret and if you add an additional layer of diffusion to the secret before sharing such "updates" are no longer possible in a straightforward manner. Note, however, that this does not influence the secrecy of the secret but against active attacks on modifying the shares.

Another issue which I initially thought could be the case comes below.

If your secret is larger than what can be represented as an element of the used field, then computational secret sharing (CSS) can be used, but it is not implemented in ssss (it's only linked as an alternative at the bottom of the page).

Basically, with CSS it is possible to make shares in a secret sharing scheme shorter at the cost of losing the perfect secrecy guarantees provided by Shamirs approach. One only achieves computational instead of information theoretic security.

The idea is to use any IND-CPA secure symmetric encryption scheme in the following (obvious) way: Choose a random secret key $k$ of a suitable symmetric encryption scheme and encrypt the secret $s$ using $k$. Then one uses polynomial secret sharing to compute $n$ shares $s_1 ,\ldots , s_n$ of the key $k$. Note that the field $\mathbb{F}$ used for secret sharing here can be much smaller as in Shamir’s original approach, as you only need to represent the key $k$ as field element and not a potentially large secret $s$.

Note that if you use Shamir's secret sharing directly on $s$, then $s$ needs to be represented as a field element (as the constant coefficient of the polynomial) and also the shares will then be of that size. If your secret is large, then CSS is an efficient alternative.

$\endgroup$
6
  • $\begingroup$ Thanks, I didn't know about CSS. Yet, I think you response does not explain the behaviour of ssss' code. In that case, the secret is still smaller than each share. In addition to that, the transformation I see being applied is not really an encryption. It is just a fixed permutation. $\endgroup$ Apr 20, 2014 at 18:36
  • $\begingroup$ @SquareRootOfTwentyThree I updated my answer. $\endgroup$
    – DrLecter
    Apr 20, 2014 at 19:08
  • $\begingroup$ "..., then Shamir's secret sharing provides information theoretic security" against passive adversaries. $\;\;\;\;\;\;$ An active adversary can very easily and controllably affect the reconstructed secret. $\;\;\;\;$ $\endgroup$
    – user991
    Apr 20, 2014 at 19:15
  • $\begingroup$ @Ricky Demer I changed it to secrecy. I agree that pure Shamirs sharing is malleable but I only refer to hiding the secret. $\endgroup$
    – DrLecter
    Apr 20, 2014 at 19:18
  • $\begingroup$ I think "additional security" should be changed to "additional secrecy". $\;$ $\endgroup$
    – user991
    Apr 20, 2014 at 19:20
1
$\begingroup$

Note that, despite your notation, the exponent does not need to be prime.

Why is that?

They probably do that to reduce the impact of malleability on the reconstruction process.

Which attack does it prevent?

It might prevent simple malleation when the secret is not easily guessable.

Does it help when the secret has a short bit length?

Yes.

$\endgroup$
2
  • $\begingroup$ That seems reasonable! $\endgroup$
    – DrLecter
    Apr 20, 2014 at 19:24
  • $\begingroup$ You should insert the questions you're responding to as quotes into your answer. It's a bit hard to follow in its current form. $\endgroup$ Apr 20, 2014 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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