search

darconeous / msecret-rust

Tool for deriving various types of keys from known symmetric secrets.
Apache License 2.0
1 stars 0 forks source link

Simplified secret splitting #5

Closed taylortrimble closed 1 year ago

taylortrimble commented 1 year ago

I'm writing this out because I've always wanted to describe this. Please feel free to ignore it.

Shamir's secret sharing involves a bunch of polynomial math I don't understand; every time I go to try and understand it I wonder what the point is, because I thought of a naive implementation for secret splitting in the common way it's done for protecting a root key.

Assumptions are: you want 3 shares with a quorum of 2, or 5 shares with a quorum of 3.

Process is:

  1. Generate the root key you're trying to protect (256 bit key)
  2. Generate 3 or 5 shares (256 bit shares) labeled 0..{2,4}
  3. For each combination of quorums, hash the shares together (ordered by label) to make a quorum key a. For 3 shares you have 3C2, 3 possible quorums, 3 quorum keys b. For 5 shares you have 5C3, 10 possible quorums, 10 quorum keys
  4. Wrap the root key under each quorum key; store that wrap
  5. When you want to recover the root key, you recreate the quorum key from a quorum of shares and unwrap the root key

You store the root key wrapped 3 or 10 times, but it's super simple and it's always made me wonder why anybody bothers with Shamir.

darconeous commented 1 year ago

Hi Taylor!

You make it sound like SSS is irredeemably complicated, but compared to ECC or RSA it's really not that bad. A basic understanding of it can be had with high-school algebra. The final step of performing the calculations over a Galois field is admittedly not high-school algebra, but I don't think it is really as opaque as you are making it out to be.

Your approach would work and would be secure enough for most applications, assuming you are using a modern strong hash function. You could even do away with the labels and just sort the shares by value when calculating the "quorum" key, which would make the individual "shares" one byte shorter.

However, Shamir Secret Sharing (Especially over $GF(256)$ )has some really nice properties that you don't get with your scheme. Some of these properties aren't entirely relevant in the way that I'm using it in this project, but I'll enumerate them here nonetheless:

  1. Provably as secure as a one-time pad. You can have mathematical certainty that the only information an attacker could have about the secret if they have less than the threshold number of shares is the length of the secret. The scheme you described can only ever be as strong as the hash function.
  2. No additional state, aside from the minimum number of shares and knowledge of the scheme being employed, needs to be kept to recover the secret. Your scheme isn't really using "shares" in the traditional sense because significant additional state (3 or 10 wrapped keys) is required in order to recover the secret. You could simply distribute that state with each share, but that would increase the size of your shares considerably.
  3. Scalable. For example, with the $GF(256)$ version, you can have up to 255 shares, with any proportion of them being the threshold. The math works exactly the same.
  4. It works even if you don't know the exact threshold. If, say, the threshold is 3, supplying 4 or 5 shares doesn't change the output.

SSS allows you to do weird and interesting things. For example, you could pin one or more of the shares (less than the threshold) to specific values. This would allow you to have some of the shares be actual memorable pass-phrases that don't need to be written down. You could do something similar with your scheme, but the additional state requirements present an additional burden since they cannot be memorized.

Overall, SSS has a lot going for it. You can't do much better in terms of the provable security of the scheme or the size of the shares.

taylortrimble commented 1 year ago

I do like all those properties of Shamir. I didn't know about the provable security to the level of one-time pad before, which is cool. This finally got me to look deeper at Shamir too, and after your explanation and a reminder that I did indeed do Lagrange polynomial stuff back in high school (but not since then), it's not as complicated as I thought it might be. If I need to do something like this in the future, I could now see myself going either way with the trivial solution or with Shamir.