Shamir Secret Sharing

Not sure about year 2023, but at the time I wrote it for my previous employer there was nothing remotely usable for regular user.

Thus, BananaSplit. It doesn't allow you to specify many parameters (just the number of shards, and then requires 50%+1 to recover); aimed at printed backups (generates printable full-page QR codes, while asking to copy a decryption phrase to the pages by hand to avoid an "evil printer" attack); and takes the concept of _portable web app_ to its extreme, being a self-contained single html file which requires you to save it locally and open via file:// protocol for it to work.

Disclaimer: while being in use for years, the code had never seen a proper independent code review; there might be bugs, despite me trying to minimize their impact by design, and using only reputable (and pretty minimalistic) JS primitives. If you want to check out the sources yourself before using, of course those are available under GPL at https://github.com/paritytech/banana_split/

One of the big downsides of SSS is that it’s very raw and you have to do a lot of legwork to make it actually useable. For instance, you can sss_combine any arbitrary polynomial coefficients and get a result, you don’t know if the reconstituted data is correct until you try to use it. Implementations can vary in the finite field chosen because SSS doesn't specify one, and not all are equal and they are not interchangeable (coefficients from one don’t work in another). Another issue is that it’s susceptible to collusion. It’s rightfully criticized for its shortcomings and the argument follows the don’t roll your own crypto vein. SSS is like handing a dev XOR and telling them “now go encrypt things”.

SLIP39 solves this by formalizing a protocol for handling SSS splits built atop standards for crypto key serialization (BIP-39). SLIP defines a standard finite field (used when interpreting the polynomial coefficients), SLIP shards are unique on each generation so parties with the same underlying SSS shard can’t compare mnemonics, they’re mnemonically serialized for humans, and they have a checksum and group index metadata which makes a more sane UX possible when combining. SLIP also describes a two layer setup so you can manage trust by cordoning people off into groups to help litigate collusion.

https://francoisbest.com/horcrux

The function make_sss(secret, num_shares, p=0) makes a polynomial for sharing the given secret that requires num_shares shares to recover. P is the prime. If p is 0 then make_sss will pick a random prime large enough for the secret. Make_sss returns the prime and the polynomial. The polynomial is represented by an array of coefficients.

The function make_share(sss, i) takes a secret sharing scheme sss of the form [p, polynomial] and returns share i.

The function recover_secret(share_list, p) takes an array of num_shares shares and the prime, and return the polynomial. Each share in the share list is represented by an array that contains the share number and the share.

If you run this from the command line it will run a demo. The demo will make a random 128 bit secret, use make_sss to make a sharing system for that secret that requires 3 shares for recover, print the prime and the polynomial, then generate 3 shares (shares 1, 2, and 5), use those shares to recover the polynomial and print the recovered polynomial, and finally print the 3 shares.

This implementation is a bit different from most others I've seen. Most use Lagrange interpolating polynomials to recover the polynomial fro a set of shares. I was curious about whether it would work reasonably to instead just solve the system of linear equations for recovery the way I would have done it by hand in high school--good old fashioned straightforward Gaussian elimination.

[1] https://pastebin.com/zePiXVUj

Leonard Adleman might have something to say about that sentence.

Learning those differences by coming to Linux from Solaris was liberating; there were less limits generally. The other way around was less fun: as in this example, code that had run fine before was now subject to weird behaviors that were caused by underlying system assumptions being different. At least Solaris usually had decent documentation.

I also built a pure python lib a whole ago to use w/ an app, check it out: https://github.com/HacKanCuBa/secretshare-py It uses prime arithmetic, which limits severally the input size, but it works pretty well and fast. Not production ready BC I haven't tested it enough, but it is a good starting point.

More on the subject of the post, this is now the third near-miss company destruction I've heard about due to SSS. Hopefully some of the others will make their stories public. The snakeoil page linked above doesn't really get into "when it's secure against you".

One of the other stories I heard that was most similar to the paypal one failed for a different reason than password truncation: Since they needed the key very infrequently and most participants never (since the threshold was met by other parties) too many people forgot their passwords. A better way to use it would be to always enter all the people who were not outright unavailable and consider it a serous failure for any party to be unavailable too often.

Let

  a0 = the secret
   p = a prime number > a0
  a1 = a random integer in [1, p-1]

Here is how to generate the share for the person with ID i:

  Si = (a0 + i*a1) % p

To recover the secret given Si from person with ID i and Sj from person with ID j, do this in Python 3.8 or later:

  a0 = ((j*Si - i*Sj) * pow(j-i, -1, p)) % p

If you need to generate a share for a new person or regenerate a share for an existing person get shares from two people and recover a0 as described above. Recover a1 like this:

  a1 = ((Sj - Si) * pow(j-i, -1, p)) % p

Here’s my own explanation of SSS: https://livebook.manning.com/book/real-world-cryptography/ch...

https://github.com/karlgluck/ThresholdJS

This is a very straightforward encoding of a single 256-bit number.

¹ https://github.com/incipher/shamir