3
$\begingroup$

Lets say you have a order $n$ finite field which you are using to create $k$ shares for a password using Shamir Secret Sharing. Assume that the attacker gets $k-1$ shares.

Is it possible that the attacker can do brute force and find the password given that there is a way to check if a guessed password is correct or not (like using a login on a website multiple times till you get in)?

Does the order $n$ of the finite field matter in such a brute force attack? Will increasing the value of $n$ give additional security in such a scenario?

$\endgroup$

2 Answers 2

2
$\begingroup$

Let the Shamir's Secret Sharing (SSS) is constructed from the finite field $K = \mathbb F_{p^m}$, i.e. $K$ is a finite field extension with $p^m$ elements, $order(K) = p^m$.

When an attacker accesses the $k-1$ of the $k$ shares of SSS, the remaining all values from the $K$ have the same probability to be a candidate of the last share. This is due to the property of the SSS; it has a perfect secret sharing scheme ( i.e. it has perfect secrecy ). Therefore; the attacker doesn't learn anything unless they hold all shares.

The attacker, while holding the $k-1$ shares, has $p^m$ equal possible candidates for the last share. The only possibility for them is trying all of them to distinguish with the real one, nothing more.

Well, instead of paying ( or stealing) for the $k-1$ shares they can simply try all of the $p^m$ elements of the field. Because;

  • They have no advantage of having the $k-1$ shares or $1$ shares They are all the same, SSS has perfect secrecy.

Now, since the password is constructed from the shared secret, then there is a limit on a possible number of passwords; $p^m$. Assuming that a bad password hashing method is used, like just pure SHA-256, then the size of the field must be larger than $2^{93}$ since the Bitcoin miners can reach this amount of SHA-256D in a year. Therefore, it is advisable to have a field with an order larger than $2^{128}$.

One needs a better password hashing algorithm like Argon2id to limit the attacker's capabilities. For example, if you use PBKDF2 with an iteration count equal to 1M ( Argon2 has iteration, too), then you reduce the attacker's search by $\approx 2^{20}$. If you use memory-hard and thread count supporting password hashing functions like Argon2, then you reduce the parallelization capabilities of the attacker, especially in ASIC/GPU cases. Decide your risks and target security then adjust the parameters of the password hash functions. And do not forget to add a random salt to password hashing.

If the share is also used to create an encryption key, the share must be equal to or larger than the key size. The simple reason is this one cannot increase the entropy by hashing.

Is it possible that the attacker can do brute force and find the password given that there is a way to check if a guessed password is correct or not (like using a login on a website multiple times till you get in)?

Well, most of the good websites/systems protect against these attacks by limiting the password tries or having 2-factor authentication. We may, however, assume that the attacker access the DB to get the hash of the password(s). This is the usual attack model in password security. So, increase the field order.

Does the order $n$ of the finite field matter in such a brute force attack? Will increasing the value of $n$ give additional security in such a scenario?

Yes and Yes as above.

$\endgroup$
2
  • $\begingroup$ Thanks, so bigger the size of the finite field the better right? However, I see a lot of SSS implementations using GF(2^32) or GF(2^64). Isn't that a security threat ? .. But then again how often does an attacker get hold of k-1 shares :) $\endgroup$
    – Makky 56
    Dec 25, 2021 at 18:14
  • $\begingroup$ It is really depend on your security risks. What kind of implementations do you see? Real product or demonstration? As I mentioned the attacker doesn't need the $k-1$ shares since SSS has perfect secrecy. Having $k-1$ or none is equal. It would have been a better question with those link and where they are used. $\endgroup$
    – kelalaka
    Dec 25, 2021 at 18:17
2
$\begingroup$

Provided that Shamir's secret sharing is implemented correctly, the attacker gains no advantage from knowing up to $k-1$ shares, and the size of the field does not matter.

Yes, the attacker can carry out a brute force guessing attack to (possibly, given enough time) find the password. But they can do that even if the password isn't shared, and knowing up to $k-1$ shares does not make this attack any easier.

That is, with one sort of obvious caveat: knowing the size of the share(s) gives an upper bound on the length of the password, which an attacker could potentially exploit to save some time, especially if the password happens to be inadvisably short. But as long as we assume that the length of the password is public knowledge, or that the password has been padded to a fixed length before sharing it, then even this gives the attacker no information that they did not already have. And, in any case, the attacker doesn't need to actually know any shares to gain this information — all they need to know is how long the shares are.


Of course, if the password is too long to fit in a single finite field element, then it must somehow be split into pieces, and those pieces shared separately. But this does not affect the basic information-theoretic security property of Shamir's scheme, which says that knowledge of less than $k$ shares gives no information about the secret. It is not hard to see that, given a secret consisting of multiple separate finite field elements, each shared independently using Shamir's scheme with threshold $k$, knowing up to $k-1$ shares for each secret element gives no information about any of them. (It's also not hard to show that this holds even if the same public parameters, including the share $x$ coordinates, are used for sharing all of them.)

$\endgroup$
4
  • $\begingroup$ This answer should receive more attention. The point of Shamir secret-sharing is that even if you have a lot of shares, as long as you don't have the right amount, you won't learn literally anything you didn't already know before holding the shares. $\endgroup$
    – Daniel
    Dec 26, 2021 at 7:39
  • $\begingroup$ @Daniel actually, I've mentioned that, however, now I've mode it more into the eyes. $\endgroup$
    – kelalaka
    Dec 26, 2021 at 10:01
  • 1
    $\begingroup$ "Provided that Shamir's secret sharing is implemented correctly, the attacker gains no advantage from knowing up to k−1 shares, and the size of the field does not matter." Wouldn't they be able to do a brute force guess-and-check attack to find out what the final share is? $\endgroup$
    – nick012000
    Dec 26, 2021 at 11:23
  • $\begingroup$ @nick012000: Yes, but it's no more efficient than just doing a brute force guess-and-check attack to find out what the secret is directly, without needing any shares. $\endgroup$ Dec 26, 2021 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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