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.
