Recently at, we wanted to even better secure the authentication to a web application that we provide to our customers.

There are several options to extend authentication:

We decided for partial passwords: You have your username and your first password, you login with that, and if that worked, you are asked about some specific letters from your second password: Please give us the third and 5th character of your second password!

See this paper called “Give Me Letters 2, 3 and 6!”: Partial Password Implementations & Attacks that describes Partial Password implementations and attacks in a detailed study.

The next question is, how to store the information about the partial password: you cannot hash it, because you will have to verify single characters. The solution is to use a secret sharing scheme, as described in Partial Passwords – How. It uses the Shamir’s Secret Sharing algorithm.

I have now implemented this idea, processing partial passwords with Shamir’s secret sharing scheme, in PHP. You can find the code licensed under the MIT at: There is an example included.

The Wikipedia article on Lagrange polynomial has been helpful as well in properly implementing the algorithm in PHP.

Authentication with Partial Passwords and processing the shared secret with PHP
Tagged on: