Late Binding for the M-Pin protocol

The M-Pin protocol has been proposed for use in a setting which uses multiple Trusted Authorities. One way to realise M-Pin is to use “early binding”. With early binding the client secret shares issued by each authority are combined immediately after they are issued to each client, inside of the client process. Here we consider the possibilities of “late binding” whereby client secret shares are kept distinct. Conceptually with early binding all of the client secret shares are added to create a single secret, which is used to authenticate. Unless all shares are present and correct the authentication will not succeed. With late binding multiple individual secrets are issued as before, but each is used to authenticate separately. Unless all authentications succeed the overall authentication will fail. So in both cases the outcome is the same. However here we argue that late binding, at some extra cost, results in a more flexible system.

Download PDF on Late binding on the M-Pin Protocol

1 Introduction

The reader should refer to the original M-Pin paper for definitions.

A Trusted Authority (TA) can issue a client secret as $sX$, where $s$ is their master secret, and $X=H\left(ID\right)$ is the client’s identity hashed and mapped to an point on a specific elliptic curve, which we consider as an element in the group $G_1$. Using the M-Pin protocol a client can now authenticate to an M-Pin server equipped with a server secret $sQ$, where $Q$ is a fixed element in a different group $G_2$.

Now a trivial way to distribute the client secret issuance functionality is to deploy $n$ Distributed Trusted Authorities (DTA), each of which has its own master secret $s_i$. Client secrets can then be formed by simply adding all of these contributions, so $sX=s_{1}X+s_{2}X...+s_{n}X$. Then proceed to authenticate to the server using this combined secret. The server has been issued with $sQ=s_{1}Q+s_{2}Q...+s_{n}Q$. The benefit is obvious – an attacker must now capture all $n$ components in order to reconstruct a client secret. Even if only one is missing, they get nothing. And clearly the master secret $s=s_1+s_2...+s_n$ is itself similarly protected. So no more single-point-of-failure.

Observe now that an individual client secret share $s_{i}X$ is indistinguishable in form from the full client secret $sX$. It is a scalar multiplication of the same element in $G_1$. Therefore an alternative approach suggests itself. Instead of immediately adding all of the client secret shares, the client instead uses them all individually to authenticate to a server. Only if all these authentications succeed will the overall authentication be deemed a success by the server. The former approach we call “early binding”, and the latter “late binding”.

Now M-Pin also supports the concept of time permits. Here the identity used by the server to confirm authentication is formed as $X+Y$, where $Y=H\left(T|ID\right)$. Here $T$ is a representation of time, perhaps the current day. Clearly the authentication will only succeed if the client has in their possession not only the client secret $sX$, but also a “time permit” $sY$.

With classic early binding M-Pin, each DTA issues client secrets shares, server secret shares, and time permits. With late binding, the client can now instead, by arrangement with the server, “do their own thing” with secret shares. They may decide to immediately add them (early binding), or to keep them all separate (late binding). Or they may decide to use some combination of both ideas. In particular DTAs which choose to issue time permits can be handled separately from those that do not. Therefore an immediate benefit is that not all DTAs need to issue time permits.

Another possibility is that PIN extraction might only be performed on one of the shares. Or that one DTA might issue secret shares from which a PIN will be extracted, and another might issue a share to be used with a fuzzy biometric, in which case the M-Pin error detection capability might be useful. Note that by keeping these shares separate, interactions between authentication ”factors” can be removed. Also the server can now determine the exact cause of failure (bad PIN? bad biometric? wrong time permit?). In fact the possibilities are endless, and we will not attempt to enumerate them all here.

However clearly late binding requires more computation for both client and server, and an increase in bandwidth. So it should be used sparingly. Some simplifications are possible. Classic M-Pin is a 3-pass protocol, involving a client to server phase, a server issued challenge, and a client response. Since each authentication is independent, these passes can be combined so that the authentications take place in parallel, rather than serially. So the protocol remains 3-pass, although more data is transmitted in each pass. On the client and server sides more computation seems inevitable. However parallel processing may offset this.

2 Example configuration

Here we consider the simplest scenario which demonstrates the possibilities of late binding. We assume just two DTAs, one which supports time permits and one which does not, but from which a PIN will be extracted.

The first DTA with master secret share $s_1$ does not support time permits, and issues a secret $s_{1}H\left(I{D}_a\right)$ to Alice and $s_1.Q$ to the server. The second DTA with master secret share $s_2$ and which will issue time permits, issues a secret $s_{2}H\left(I{D}_a\right)$ to Alice and $s_2.Q$ to the server. In both cases $H\left(.\right)$ is a suitable hash function which hashes and maps an identity string to an element in the group $G_1$.

In the protocol as described below, $T_i$ represents the current time slot, and $s_2{H}_T\left(T_i|I{D}_a\right)$ is the personalised “time permit”, where $H_T\left(.\right)$ is another hash function. The extracted PIN number is $\alpha$.

Table 1: Late Binding M-Pin example

At first glance this configuration would be expected to double the computation and bandwidth. However a possible optimization would be for the server to calculate directly the product $g=g_1.g_2$, so $g=e\left(V_1,Q\right).e\left(U_1+y_{1}A,s_{1}Q\right).e\left(V_2,Q\right).e\left(U_2+y_{2}D,s_{2}Q\right)$, and to reject the connection if this were not equal to one. By bilinearity this can be simplified to $g=e\left(V_1+V_2,Q\right).e\left(U_1+y_{1}A,s_{1}Q\right).e\left(U_2+y_{2}D,s_{2}Q\right)$. Products of pairings can be calculated very efficiently, and the expected overhead here would only be about $10\%$. However this would introduce the possibility of false positives, where $g_1.g_2=1$, but $g_1\ne 1$ and $g_2=1∕g_1$. But this would be very unlikely to happen in a real protocol run, and it is hard to see how an attacker might exploit this possibility without reversing the pairing function, which is believed to be hard. Another downside of this approach is that it would no longer be possible for the server to distinguish between a “bad time permit” and a “bad PIN” error.

Any error $\delta$ in the entered PIN can be calculated as before by solving the discrete logarithm problem $g_1=e{\left(U_1+y_{1}A,Q\right)}^{\delta }$.