willtracz.co.uk

This post is intended to introduce concepts and practically demonstrate a method. The implementation provided is not a reliable/hardened solution (i.e. there are vulnerabilities because finite fields are not used) and should not be used anywhere near a production system.

Take a look at this screenshot I took from TD Waterhouse’s login page. How can this process be secure?

Lots of people seem to believe that it can’t be done, that passwords must be being held in plain-text etc. Forunately though, forms like this can work securely by using Shamir’s Secret Sharing algorithm. How many actually are I don’t know, but in this post I’ll try to explain it.

The key observation behind the algorithm is that it takes two points to define a line, three a parabola etc. and $k$ for a polynomial of degree $k–1$. By constructing a polynomial $f\left(x\right)=a_0+a_1{x}^1+a_2{x}^2+\dots +a_{k–1}{x}^{k–1}$ where $a_0$ is the secret, it is possible to find the coefficients of the polynomial by knowing just a subset of points. This is possible using Lagrange interpolation.

For normal operation apart from the secret coefficient $a_0$, the remainding coefficents of this polynomial are generated randomly with $k$ set to the number of parts required to reconstruct the secret. Each participant is then given a number of input/output pairs from the function. Participants who then wish to reconstruct the secret must collude to obtain at least $k$ many outputs from the function. This allocation can be performed in all sorts of ways to allow various heirarchies with varying numbers of participants.

In the context of a bank and passwords though, rather than using random values for the coefficients, the password itself is used as the entropy source. This means that the polynomial is now constructed such that $a_0$ is a secret (perhaps a key for decryption), the number of characters required from your password is chosen as $n$, $k$ the length of the password, and the remaining coefficients $a_1,\dots ,a_{\mathrm{k}}$ taken as the ASCII value of the respective password character. The trick is to now understand how the bank could possibly use this structure!

The bank needs to know enough to obtain the secret, but not hold the password in the clear. To achieve this the polynomial is evaluated at the points $p_{\mathrm{i}}$ where $1\le i\le k$ i.e. $p_{\mathrm{i}}=f\left(i\right)$. However, storing these values would allow the secret to be obtained by interpolation. The simple way to avoid this is to obfuscate each value with the ASCII value of the password character, for example, by summing $q_{\mathrm{i}}=p_{\mathrm{i}}+a_{\mathrm{i}}$, and storing this set of new values instead. Using these, it is not possible for the bank (or an adversary who has obtained the stored values) to work out the secret without also requiring relevant characters from the password.

Finally to get back the secret, the bank must first obtain some characters from the password. The first step that the bank then performs is to subtract the ASCII value of the input from the relevant stored value. This gets the original output $p_{\mathrm{i}}$ from the polynomial back. Now, because the bank knows the position of the character it challenged you for ($i$) and also has the resultant value from the polynomial, they can use interpolation to re-generate the polynomial and get the secret (because it falls out when the polynomial is evaluated at zero.)

Admittedly this is a little theoretical so I have written a PHP script demonstrating the concept. The source code is on GitHub.