Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
Note that, despite your notation, the exponent does not need to be prime. $\;$ –  Ricky Demer Apr 20 at 18:07
    
I replaced p with q to avoid confusion. –  SquareRootOfTwentyThree Apr 20 at 18:33
    
Based on your description, it serves no purpose. –  K.G. Apr 20 at 18:56

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  SquareRootOfTwentyThree Apr 20 at 18:36
    
@SquareRootOfTwentyThree I updated my answer. –  DrLecter Apr 20 at 19:08
    
"..., then Shamir's secret sharing provides information theoretic security" against passive adversaries. $\;\;\;\;\;\;$ An active adversary can very easily and controllably affect the reconstructed secret. $\;\;\;\;$ –  Ricky Demer Apr 20 at 19:15
    
@Ricky Demer I changed it to secrecy. I agree that pure Shamirs sharing is malleable but I only refer to hiding the secret. –  DrLecter Apr 20 at 19:18
    
I think "additional security" should be changed to "additional secrecy". $\;$ –  Ricky Demer Apr 20 at 19:20

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.

share|improve this answer
    
That seems reasonable! –  DrLecter Apr 20 at 19:24
    
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. –  CodesInChaos Apr 20 at 21:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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