6
$\begingroup$

Yesterday I made a PR to a python crypto library to support key sizes larger than 16 bytes for Shamir secret sharing scheme.

Currently it supports 16 bytes, as follows:

$$ K = \{ 0, 1 \}^{128} $$ $$ S_{128}(m, n, K) = s_1, ... , s_n $$

To not change underlying function, and to support larger keys, I decided to split the key and run the function as many times as needs and concatenate the shares. 32 byte key example below using a limited 16 byte shamir split function.

$$ K = \{ 0, 1 \}^{256} = \{ 0, 1 \}^{128} | \{ 0, 1 \}^{128} = K_A | K_B $$ $$ S_{128}(m, n, K_A) = s_{A1}, ... , s_{An} $$ $$ S_{128}(m, n, K_B) = s_{B1}, ... , s_{Bn} $$ $$ s_1 = s_{A1} | s_{B1} $$

A couple people on the PR brought up that this is insecure, as you can attack each side in the case of 32 bytes, each side 16 bytes, means the key strength goes from 32 bytes (2**256) to 2 * (2 ** 128) = 2**129.

I don't believe this to be true, as there is no attack on one side that would let you know you've succeeded letting you proceed to the other side.

To take it the extreme, even if the shamir function only supported 1 byte (8 bit) key size, you would still maintain security doing the function in blocks and concatenating the resulting shares.

Let me know what you think.

Improve this question
$\endgroup$
5
  • $\begingroup$ Is there a method that one can verify the 32-byte to divide-and-conquer the secret? This is the key to this. What is the target usage of the secret? $\endgroup$
    – kelalaka
    Jan 21, 2022 at 19:24
  • $\begingroup$ Key is for symmetric enc (e.g. AES256) or for asymmetric (e.g. ed25519 private key). $\endgroup$
    – mkl
    Jan 21, 2022 at 19:30
  • $\begingroup$ The shared secret sides can be malicious? I.e. can they construct their share and brute-force the other? $\endgroup$
    – kelalaka
    Jan 21, 2022 at 19:32
  • $\begingroup$ Lets say threshold to recover key is 3 shares. If we assume adversary has 2 shares, then they'd be left trying to reconstruct the final share. I don't think the adversary would have any advantage of figuring out one block at a time. I.e. there is no checksum or hash that says block 1 success (as far as I know...). $\endgroup$
    – mkl
    Jan 21, 2022 at 19:34
  • 3
    $\begingroup$ SSS has perfect secrecy therefore having one share or n-1 doesn't help, all have the same probability to be the secret. I think they consider this, instead of 256-bit perfect secrecy you have two 128-bit perfect secrecy therefore they are not equal. In the end, the uncertainty of all bits is the same for the attacker, so not true. $\endgroup$
    – kelalaka
    Jan 21, 2022 at 19:38

1 Answer 1

Reset to default
6
$\begingroup$

I don't believe this to be true, as there is no attack on one side that would let you know you've succeeded letting you proceed to the other side.

The reason you don't believe this is true is because it is, in fact, untrue.

With a Shamir Secret Scheme, $t-1$ shares gives absolutely no information about the shared secret. That is, the only attack available to the adversary is to ignore the values of the shares (which tells him nothing) and guess the full AES-256 key directly (which, as we all know, is completely infeasible).

A couple people on the PR brought up that this is insecure, as you can attack each side in the case of 32 bytes, each side 16 bytes

These people are wrong - there is no 'attack' available on Shamir's that allows someone with $t-1$ shares to recover the secret (or, for that matter, gain any information on it) - this remains true even if we assume the attacker has infinite computational capabilities.

To take it the extreme, even if the shamir function only supported 1 byte (8 bit) key size, you would still maintain security doing the function in blocks and concatenating the resulting shares.

You could take it even more extreme than that - if each secret was only one bit (and so there are a total of 256 of them), that is, the adversary knew up front that each of them either held the value 0 or the value 1, he still wouldn't be able to get any further information about the key.

On the other hand; there is one precaution you need to take - you need to assume that the random polynomial that you generate to protect each 128 bit half is selected independantly. If (for example) they're the same except for this constant term, the above reasoning does not apply.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the answer, and yes each block gets a new polynomial coefficients. However they all use one field: github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/… $\endgroup$
    – mkl
    Jan 21, 2022 at 19:45
  • 1
    $\begingroup$ @mkl: using the same field is fine... $\endgroup$
    – poncho
    Jan 21, 2022 at 19:50
  • 2
    $\begingroup$ It's perhaps worth noting that, while using Shamir's scheme to share individual bits is indeed perfectly secure, it does waste some space since you still have to use a field with at least $n+1$ elements to generate $n$ shares. While individual bits map perfectly to elements of GF(2), that field is useless for Shamir's secret sharing since you can only generate at most one(!) share. $\endgroup$
    – Ilmari Karonen
    Jan 22, 2022 at 18:37
  • $\begingroup$ @IlmariKaronen: well, yes, I said it would be secure - I never said it would be practical... $\endgroup$
    – poncho
    Feb 23, 2022 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.