What are the disadvantages of using Shamir's Secret Sharing to implement a Partial Password scheme?

Question

Suppose I want to implement a partial password scheme, where the user authenticates by using two passwords: one a normal password, the other is partial, where he only needs to type the selected three characters of that password:

I have previously asked about implementing this and it is obvious that simple approaches such as hashing individual characters fail completely. Suppose we are also barred from implementing a hardware authentication module that will store the password and just gives you a correct/incorrect answer for your input.

Another potential approach is using Samir's Secret Sharing, as described in details here with regard to the idea of partial passwords.

Roughly, we are providing an ability to recover a secret password (or its hash, which is better) by providing let's say 3 out of 8 chunks of data.

Is this scheme secure against brute force by an attacker who obtains access to the database, and by secure I mean secure at least to the same degree as a database of traditional salted and hashed passwords?

Answer 1

The source you cite actually already points out the problems, although it does actually considers these as problems but as advantage. To cite:

Pros and Cons
The highlights of this solution are:
...
5. Faster to compute - verification is several multiplications of 32 bit numbers that is much much faster than computing a hash value.

The attack you are trying to prevent is that the attacker can guess correctly provided that the attacker knows the secret information stored in the database.

In your example you have a secret with 10 alphanumeric characters where the attacker needs to guess a specific 3 characters. This means 36³ guesses are needed when only upper-case characters are allowed or 72³ with also lower-case characters. Given that the check is very very fast the attacker can quickly find out these values (i.e. likely real-time) if the secret stored in the database is known.

If the attacker must choose more than 3 characters it gets harder to do in real-time but it can be easily precomputed. If 5 out of 10 characters are needed than 10*9*8*7*6/(2*3*4*5) possible "masks" for entering the characters must be precomputed with each has at most 36⁵ (or 72⁵) possible values, i.e. at most 10*9*8*7*6/(5*4*3*2)*72⁵ really fast computations must be done. Assuming that 10000 computations could be done in a second this would take the attacker a day if he has a botnet of about 600 machines - which is not unreasonable. And it could probably be optimized. With 4 out of 10 characters one would only need 6 machines for a day and with 3 out of 10 a single machine could do this in less than 1.5 hours.

Note that this estimates also assume a random secret. If it is a user chosen secret it gets much worse since the search space is smaller. But, if the user can not chose the secret then he probably needs to write the random secret somewhere - defeating your original idea why this additional secret should be given (i.e. prevent shoulder surfing and storing in password managers) in many cases.