Secure Partial Password using Shamir’s Shared Secret
Partial Password is a technique of authentication in which we ask the users for only few random characters from their password. As we know, to securely store a password in the database we should transform it to a non-reversible form like a cryptography hash. It’s easy in traditional approach but quickly become non-trivial if we want to authenticate using only a part of the password. We can either hash every character separately (which has no sense, because you can brute force it in seconds on Nokia 3310) or store every possible permutation of the password but it would be space consuming. For 8-character string there are 40320 such permutations, for 16-character it’s 2092279000000 so it’s out of our consideration. Plaintext is no-go too.
Secret Sharing
Secret Sharing a method of distributing some secret to multiple keepers in such a way one keeper can not get full secret on his own. He needs to collaborate with a sufficient amount of the secret share keepers.
There are many ways of doing this. In this article you will see mathematical one but don’t worry. That method can be understand by anyone who knows high school maths.
Shamir’s Scheme (Polynomial method)
Shamir’s scheme is a secret sharing algorithm invented by Adi Shamir (co-inventor of RSA) and it’s based on a simple principle: a set of (x, y) points of size n can generate (n - 1) degree polynomial function.
To create a Shamir’s scheme from a K-character password and N characters needed to authenticate we need to generate a random polynomial w(x)(random coefficients) of degree (N - 1) and select K random points on it. Tip: P(x, w(x)) is always on polynomial.
Then we compute w(0) (or other arbitrary y-value) and store it as a secret for password verification.
We also need to embed the password in it somehow. We can add the password characters code (ASCII/UTF8) number to a y-value of every point and store them.
So basically we keep:
- List[K] of x-value for every generated point
- List[K] of value derived from y-values and password characters
- ZERO = w(0) value to confirm the polynomial
Because (x, y) -> (x, y + P_i) mutation we applied for every point gives us completely other polynomial its w(0) is also different* and we can’t easily resolve the password characters without brute-force because they are infinitely many polynomials the P(0, ZERO).
*there is probability they are the same, but it’s marginal.
To authenticate the password we ask the user for N characters and fetch corresponding points from the database. Then we can apply very similar mutation as before to resolve original points (x, y) = (x, y - P_i)
Having the (x, y) points we can solve a linear system to get the coefficients. Many matrix math libraries provide methods for that.
Using the solved coefficients, it’s now trivial to compute the w(0) and compare it with the value stored in database. If they are the same, it means the user gave us correct password.
Security
Shamir’s Secret is proven to be secure but it doesn’t imply our application will be secure too.
Partial Password gives only one advantage — it’s protects us from keyloggers until user type their password enough times to disclosure every character. Moreover if somebody knows enough characters of password, they can log in. If we implement this technique we must take care that cases. For example: don’t randomise required characters indexes until the user successfully logs in and prevent burte-force by blocking requests after few unsuccessful tries. It’s good to have security audits too.
And remember: People don’t like Partial Passwords. It’s much easier to type full password than specific characters from it. There is no sense in implementing it unless you are a bank or an institution whose clients are a target for keyloggers.
Thank you for reading.
