# Shamir's Simple Sharing Scheme - preventing partial recovery of data

In SSSS, if you recreate the original secret with one of the decoder inputs being slightly damaged (e.g. one or two chars incorrect), you receive a slightly damaged version of the original secret. So if the original secret was "Abraham Lincoln", decoding using a slightly damaged input might still get you "Ab%aham Lincoln", for example.

What's the best way to encode and decode the secret, on top of SSSS, such that any variance at all in the inputs causes the decoded secret to be completely useless?

One obvious way would be to encrypt the secret before using SSSS. Are there any alternatives? In particular, any alternative that would not require each user to have a final decryption key (for decoding the secret that comes out of SSSS) as well as their SSSS decoding keys?

-
1) How would that partial damage happen? Why do you care about this scenario 2) It's often a good idea to apply secret sharing to a symmetric key, not to the data itself. – CodesInChaos Nov 25 '13 at 10:25
@user8911 Without an answer to my first question, this can't be answered well. Blindly applying my second point is not the way to go and can be broken by guessing the remaining bits. – CodesInChaos Nov 25 '13 at 10:55
@CodesInChaos I don't really have a scenario in mind. It just makes me nervous that information is retrievable even when the inputs are less than 100% accurate. – occulus Nov 25 '13 at 11:30
I do not see how a modified/damaged share in polynomial secret sharing (viewing some encoding of "Abraham Lincoln" as the constant term of a polynomial over a finite field) could lead to a result as given by your example (with non negligible probability). If you still have enough valid shares (equal to or greater than the threshold) you can apply for instance list decoding. Or are you assuming you run secret sharing on every character independently? – DrLecter Nov 25 '13 at 12:50
Obviously, they share the secret character by character: On their page they write: "PassGuardian is built on secrets.js, an open-source implementation of Shamir's sharing scheme. While secrets.js permits Galois Fields up to 20 bits in size, PassGuardian uses an 8-bit binary finite field for computations. The share format is described at the secrets.js page." – DrLecter Nov 25 '13 at 15:23

With SSS you are sharing field elements, so if the secret to be shared is larger than one field element, you are going to have to break up the secret somehow and share the parts. I am not aware of any standard method that allows you to make the sharings dependent on one another. Probably the best way is to encrypt the secret with a key and then share the key (using Shamir) and the encrypted secret (e.g using an appropriate erasure code) and store the share/fragment parts at different locations.

Note that this is not a problem of SSS. In SSS if a share is slightly corrupted it cannot be used in reconstruction.

You could also pick a field large enough for your secret.

-
It might be better to say: encrypt the secret with a key and then share the key (using Shamir) and the encrypted secret (e.g. using an appropriate erasure code) and store the (share,fragment) parts at different locations. That's basically secret sharing made short, which, then does only provide computational secrecy instead of information theoretic. – DrLecter Nov 25 '13 at 16:54
thanks for update :) – DrLecter Nov 25 '13 at 21:47

In general, you cannot encode information such that "any variance at all in the inputs causes the decoded secret to be completely useless." That's because there's a generic attack that can be used to reconstruct the secret with a high probability, given almost enough enough information to uniquely determine it, as long as the correct secret can somehow be distinguished from incorrectly reconstructed secrets.

The attack is simple: you guess the missing information, reconstruct the secret based on your guess, and repeat this for all possible (or at least all sufficiently likely) values of the missing information. Then you compare the resulting secrets and pick the one that appears to be the correct one.

For example, let's say that the secret is a password shared using a threshold secret sharing scheme (like Shamir's) using threshold $t$, and that we know $t-1$ full shares plus all but the third byte of the $t$-th share. Now, there are 256 possible values the missing byte could have, so we can just reconstruct the secret using each of those values, giving us 255 different passwords.

Now, depending on the details of the secret sharing method used, we might be able to guess which of these was the correct password just by inspection; for example, if 255 of the reconstructions looked like random noise, while only one consisted of printable characters, we might well guess that this was the correct reconstruction. However, in this case, we'd have an even more reliable way to tell the correct password from the incorrect ones — we could just try each password and see which one lets us decrypt the data or log in or do whatever the password is supposed to be used for.

The same attack can be applied to other kinds of missing or corrupted information, as long as we have some idea of what the missing information might be. For example, if each share was $n$ bytes long, and we only knew (or suspected) that some byte of some share was wrong, we could just try changing each byte of each share to each of its 255 possible alternative values, giving us $t$ × $n$ × 255 reconstructions to choose from. For typical values of $t$ and $n$, this should still be easily manageable.

-