Join Log in
Score:6
avatar Crypto

Is it secure to do Shamir key split on a key in blocks and recombine?

cn flag
mkl

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.

317
0 + 0
kelalaka avatar
in flag
kelalaka
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?
0
Reply
cn flag
mkl
Key is for symmetric enc (e.g. AES256) or for asymmetric (e.g. ed25519 private key).
0
Reply
kelalaka avatar
in flag
kelalaka
The shared secret sides can be malicious? I.e. can they construct their share and brute-force the other?
0
Reply
cn flag
mkl
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...).
0
Reply
kelalaka avatar
in flag
kelalaka
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.
3
Reply
Score:6
poncho avatar Crypto
my flag
poncho

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.

0 + 0
cn flag
mkl
Thanks for the answer, and yes each block gets a new polynomial coefficients. However they all use one field: https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Protocol/SecretSharing.py#L81
0
Reply
poncho avatar
my flag
poncho
@mkl: using the same field is fine...
1
Reply
ar flag
Ilmari Karonen
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.
2
Reply
poncho avatar
my flag
poncho
@IlmariKaronen: well, yes, I said it would be secure - I never said it would be practical...
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.