Uh. Doesn't actually appear to be SSS

[gmaxwell]

This looks like it's just using a radix-16 RS code?

If so, then I don't think it's information theoretically secure. Classic SSS fixes the whole message in a single field element.

I think just doing an RS code over bytes/shorts results in sub-threshold shares leaking data about linear relationships between different words in the secret.

Do you have a citation for the approach that you're using?

[amper5and]

First of all, SSS is an RS code (see 1 and 2).

Second, it's important to see that each "sub-share" of the secret is independently calculated with a unique polynomial being generated for each sub-share. It's exactly like doing SSS over and over for each word of the secret. There is no need to fix the whole message in a single field element; you can look at it as fitting each word of the message into a single field element.

Finally, SSS is theoretically "information theoretically secure" as long as the polynomial selection process is equally secure; however, because there is a PRNG, it is not information theoretically secure but it is computationally secure.

[amper5and]

As for a citation for my approach, in his original paper, Shamir writes:

If the number D is long, it is advisable to break it into shorter blocks of bits (which are handled separately) in order to avoid multiprecision arithmetic operations.

(where D is the original secret)

[gmaxwell]

I've seen a other tools use a single RS code and then just output the non-systematic codewords. I'm not JS clueful in the slightest so it wasn't clear to me if thats what you were doing here.

I went and performed some blackbox tests and confirmed that after I removed your length-preservation leading-one code that all decodes are equiprobable for 16 bit data for 2-of-2, 2-of-3, and 3-of-3 with one share missing. So, ignoring RNG misbehavior, their cannot be a data leak in that case. Thats good, sorry for the firedrill there.

It's less clear with the length preservation in place, as the outputs with the correct length are no longer uniformly distributed. E.g. I appear to get a posterior entropy of only 7.789 bits if I look at the output of

var secrets = require('./secrets.js'); for (var i = 0;i<(256*256);i++) { share = "802" + ("000000" + i.toString(16)).substr(-4) res = secrets.combine( [ "801de04",share ] ) //"00" = 801de04,802a208 if(res.length==2)console.log( res ); }

But thats just from redundant codes which the encoder wouldn't have produced in any case?

[amper5and]

First of all, I would like to thank you for taking the time to investigate my code and help me make sure it's up to snuff. I am having some difficulty following what tests you performed. When you say

I went and performed some blackbox tests and confirmed that after I removed your length-preservation leading-one code

could you give a little more detail about what modifications you made to secrets.js and what the tests were? I'm not sure I understand the results of your experiment. Thanks so much.

[amper5and]

well, that went nowhere. sure wish we had some good testing of secrets.js, but alas just another stray shooter. closing.