In SSSS, if you recreate the original secret with one of the decoder inputs bein

Question

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?

Explanation / Answer

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

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.