OK, since we're pitching our SSS implementations here in comments, I welcome everyone to check out BananaSplit, https://bs.parity.io
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/
I like how it pushes you towards safety by requiring the code to run offline and off the disk. The resulting UX is not that great (though the explanation of what to do is clear), but it's a good step towards a little bit more security.
On the contrary, I hated it. I just want to see the UI, I don't want to go offline! Give me an "I'm just playing around, I promise!" button I can click on to test it.
Interesting idea, but the restore function doesn't work for me.
Access to fetch at 'file://redacted/Banana%20split.html#/combine' from origin 'null' has been blocked by CORS policy: Cross origin requests are only supported for protocol schemes: http, data, isolated-app, chrome-extension, chrome, https, chrome-untrusted.
Would it be too much to ask for you to open an issue in Github for this?
Things I'd be interested in the most would be details about your environment: browser/version/platform and if this is reproducible in a "fresh" browser profile without any extensions added (or just a list of your extensions, if that's not too privacy-invasive for you).
Mozilla SOPS¹ also supports this, but it's not nearly as user friendly for non-technical folks. Probably one of those solutions you reviewed before creating Banana Split!
We probably shouldn't even bother recommending browser-specific offline modes; I've created an issue in the project's repo to reword that piece by the next release.
Yeah, and I failed to even find an option to open a local HTML file on mobile Firefox (for Android) just now.
That's a shame — things were definitely different in 2019 when I built the initial version; and mobile browsers were definitely a target I had in mind for the tool (especially when it comes to the recovery).
Instead of wrapping the existing tool into a mobile app, I'm thinking about standardizing the QR code format from the tool a bit more — so multiple, more task-specific recovering mobile apps would be possible. (Like, the one in your password manager detecting certain internal text formatting and importing the entries automatically and such).
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.
For those who would like to play around with Shamir secret sharing, here is a Python implementation I wrote to check out something I was curious about [1]. Note: requires at least Python 3.8.
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.
Alternative history/facts: all the letters in RSA are from Adi Shamir's unixname (rsa). Because 'asr' (Adi ShamiR) was already taken, he started using the reversed string instead ('rsa'), and used it as the command name for the first unix implementation of the RSA algorithm, which he developed all by himself.
`killall` was different on Solaris than Linux; too.
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 took down the production environment once with killall. The conversation explaining to management about why I ran something called "killall" and didn't expect it to kill all was very tense.
For the uninitiated (like me), killall in Solaris kills "all active processes not directly related to the shutdown procedure" (not those with a certain name as the Linux/psmisc killall does).
Great story! It made me super nervous all the way.
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.
Yes, I agree, HashiCorp Vault definitely serves the purpose of having a single point of failure that can go down and take your entire company down with it, just like in the story :P (c.f. Roblox)
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.
Most descriptions of and implementations of Shamir secret sharing are a bit intimidating. If however you just need a system where any two people with shares can reconstruct the secret then SSS can be very short and simple.
Let
a0 = the secret
p = a prime number > a0
a1 = a random integer in [1, p-1]
Assign each person who is to receive a share of the secret an ID in [1, p-1]. It is OK to simply assign IDs sequentially starting at 1.
Here is how to generate the share for the person with ID i:
Si = (a0 + i*a1) % p
Tell each person their ID and given them their share. When each person has received their ID and share you can delete a0 and a1.
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
Pow(x, -1, m) for integers x and m in Python >= 3.8 computes the modular inverse of x mod m.
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
You can then use a0 and a1 to issue or reissue shares as described earlier.
Not deliberately? Old key used for the backups was accidentally erased halfway through the story, shredded key was just the last cleartext copy of the new key.
BIP39 is the Bitcoin standard which defines the process to generate the human readable "recovery phrase" for a Bitcoin wallet based on the private key. It's a list of 2048 pre-defiend words. Your private key is chunked into 11bit groups (with a few bits for a checksum) and then assigned the corresponding word.
Built a CLI¹ a couple of years back that uses HashiCorp Vault's implementation of the Shamir Secret Sharing algorithm and exposes its functionality to the command-line.
I think it's more of an instance of "it works on my computer"; not testing on an environment sufficiently similar to production, and applying a change that cannot be rolled back.
This is the key. The rollback mechanisms were broken. Re-encrypting data is incredibly scary because if you lose the new key you have effectively lost your data. It is important to ensure that you have up-to-date backups of the previously encrypted data and key before you start.
A better solution may have been multi-key support. Some test records could be encrypted with the new key and the system let run for a week or so. Then all new records could start being encrypted with the new key and run for another week. Once everything looks good a background job could be started to convert all data to the new key. Then the old key can be retired (other than as needed for backups).
Although they did have the key printed in an envelope, so it sounds like that would have been an effective recovery solution once they remembered.
Eh, yes and no. With proper testing this issue should have been caught. But this is also an example of how small details in crypto can become a huge issue and domain knowledge counts for a lot. As soon as the story turned to getpass() on Solaris I already knew what it was because the 8-character limit is pretty famous if you've worked on old Unix systems.
I once had to explain to some coworkers from another team why they shouldn't 'helpfully' truncate leading and trailing spaces from my password, and why they need to handle 'special' characters, too.
They couldn't believe that anyone wants trailing spaces on their password.
Not at all. The problem was that the crypto for the same library on two different OSes was implemented differently, which lead to an error encrypting on Linux and decrypting on Solaris. Ironically, this would have been avoided if they had rolled their own.
It is an instance of "make sure you have backups when deploying to production"
Not the crypto, but rather the getpass() function, which simply reads a password from standard input without echoing it.
Since the function uses a static buffer, there is a limit on the password length, which apparently on Solaris was set to the absurdly low value of 8 (glibc uses a more reasonable value: 8192).
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/